9,816 reputation
13124207
bio website gilkalai.wordpress.com
location Jerusalem
age 59
visits member for 5 years, 10 months
seen 22 mins ago
Professor of Mathematics at the Hebrew University of Jerusalem and at Yale University

Aug
25
comment Important formulas in Combinatorics
Dear Aryeh, I guess that if one can present nicely an important result in a novel way as a formula, this should be ok, but I worry this will be too inclusive.. Certainly the Sauer-Shelah-Vapnik-Chervonenkis lemma is very fundamental.gilkalai.wordpress.com/2008/09/28/…
Aug
25
comment Important formulas in Combinatorics
Thanks Aryeh, There are three conditions for an answer, it needs to be combinatorics (widely interpreted), it needs to be important, and it needs to be (already) in a form of a formula.
Aug
24
comment Important formulas in Combinatorics
There are several areas of combinatorics that are not yet represented. (Of course it is very natural that enumerative combinatorics has so many wonderful formulas.) Also if you have suggestions to choose from you can always mention them in a comment.
Aug
23
comment Important formulas in Combinatorics
Dear Incnis, Yes it is! Zaslavsky's formula is a very important formula in enumerative combinatorics, as well as geometric combinatorics, and the basis for important developments in topological combinatorics.
Aug
20
comment Important formulas in Combinatorics
Upi are correct!
Aug
19
comment Important formulas in Combinatorics
Here is a post about it (in a simpler form) gilkalai.wordpress.com/2012/01/18/…
Aug
19
comment Important formulas in Combinatorics
In short, Asaf, my answer is YES!
Aug
19
comment Important formulas in Combinatorics
I would represent the matrix tree theorem as: $$\kappa (G) = det (L^-(G)(L^-(G))^{tr}).$$ Here $\kappa (G)$ is the number of spanning trees and $L^-(G)$ is the reduced Laplacian. (The Laplacian with one row deleted). Referring to the determinant rather than eigenvalues is relevant to the proof of the theorem.
Aug
18
comment Important formulas in Combinatorics
Dear Darij, This is a formula in combinatorics even in a very strict sense since it applies to Eulerian (d-1)-dimensional simplicial complexes, namely to complexes so that links of faces have the same Euler combinatorics as a sphere of the same dimension. Moreover relations between face numbers of polytopes, and even of complexes described by topological conditions are regarded part of combinatorics.
Aug
18
comment Important formulas in Combinatorics
Dear Asaf, as I see it, we want important formulas representing major progress in combinatorics; so infinitary combinatorics applies as well. As I see it: it need to be a formula, it need to be stated explicitly, and it need to be related to important research advances. Maybe we should avoid classic famous very well-known formulas, so I would regard $2^\lambda >\lambda$ as too basic to be included.
Aug
17
comment Important formulas in Combinatorics
I would adopt it as a formula in combinatorics any day!
Aug
17
comment Important formulas in Combinatorics
This is certainly a great formula!
May
5
comment Logic in mathematics and philosophy
No, make that the end of the 18th century.
Apr
30
comment Models for graphs representing real-life networks
Dear Rupei, Thanks a lot
Apr
28
comment Models for graphs representing real-life networks
It is a nice answer, Joe, Thanks!
Apr
28
comment Models for graphs representing real-life networks
I am interested (at this point) in the graphs themselves.
Apr
12
comment Intersecting Family of Triangulations
Dear Bruno, thanks very nice!
Apr
5
comment Enumeration of $0-1$ matrices with determinant $1$
Regarding det (A) behaving uniformly below the value $n^{n/2}$ there is a heuristic which slightly corrects it (but it looks that it will not make a difference regarding the $2^{n^2-O(n\log n)}$ estimate. The heuristic is that mod a prime the determinant of A behaves like that of a random matrix modulo p. This gives some guess regarding ,e.g., $prob (det (A)=2) /Prob (det (A)=1).
Apr
5
comment Enumeration of $0-1$ matrices with determinant $1$
There are several heuristic arguments for the asymptotic of f(n) which unfortunately gives different answers. Probably I would vote against the idea that upper unitriangular matrices gives most contribution. There are pretty good results and even better conjectures for the number of matrices with determinant 0. This occurse (conjecturaly) mainly if a row (column) is zero or two rows (columns) agree which gives 2^n^2 / n^2 2^n. This suggests that f(n) is also at most 2^n^2/c^n. It is reasonable to believe that det (A) is pretty close to being uniform below n^n/2 which justifies Noam's guess.
Feb
19
comment The amplituhedron minus the physics
I meant that the matrix representing the projection is totally positive (all minors are positive). It is enough that all maximal minors are positive.