Oberwolfach: what happens in combinatorics
I am at Oberwolfach for the combinatorics meeting this week. Scheduled once every 3 years, this is considered one of most prominent meetings in the field.
The first two days features quite a few interesting talks, proofs, questions, and news.
(1) Ron Peled talked about counting number of designs. Given a set and three parameters , a design is a collection of subsets of size of such that every -tuple of points in appears in exactly sets. A famous example is finite projective plane, where and (through every two points there are exactly one line). It is easy to see that the size of is determined by the given parameters.
The parameters need to satisfy certain necessary conditions (coming from double counting); however, these conditions are not always sufficient. The existence of designs with a given parameter set can be formalized in matrix language as follows. Let be a big matrix whose rows are indexed by the -subsets of and the columns are indexed by the -subsets, and the entry in the intersection of a -set and a -set B equals 1 if contains and otherwise. One needs to find a collection of rows whose mean equal the mean of all rows. (These rows will form a design.)
Now we can think of a general problem. Given a big matrix, when can we find a collection of rows whose mean equal the mean of all rows ? Thinking probabilistically, what is the chance of a random set of rows does the job ? With a bit handwaving, one can think of a set of rows obtained by selecting each row with probability . Let be row (as a vector in ) and assume that the mean is 0. Then we are talking about estimating the probability that the sum of equals 0, where , , are iid indicator random variables with mean . Under normal circumstances, the sum satisfies the central limit theorem. To estimate the chance that it is zero, one needs a sort of local central limit theorem. As Ron showed, this can be done using Fourier analysis, given certain assumptions on the . At the end, this gives an asymptotic value for the number of designs if is sufficiently large (something of order , if I remember well).
(2) June Huh talked about log concavity of certain sequences arising from matroid theory. The simplest one is the following. Given a finite set of vectors in and let be the number of subsets of independent vectors. It is conjecture that the sequence is log-concave,namely . Huh found a nice technique to embed this problem into a more general problem in algebraic geometry, from which the log-concavity appeared through an Alexanderov-Fenchel type inequality, proving the conjecture. Since he did not want to scare us away, June hid most details from algebraic geometry, but it appeared that the method is general enough to handle other problems (such as log-concavity of coefficients of a chromatic polynomial). In particular, it can handle cases when the matroid in question is representable over a field. (However, as Huh pointed out, there are many matroid not of this form.)
(3) There was a problem section. The problem I like most is the following (it is an old problem from statistical physics, presented by Ron Peled). Let be an grid. Seen as a graph, is bi-partitie and thus 2-colorable. Let us be generous and color it by three colors, say Red, Blue, Black. Of course, there is a huge number of possible colorings. Let us choose one coloring uniformly randomly and look at the color of the opposite corners of the grid. Is this true that the probability that these points have the same color tends to as tends to infinity ?
Naively thinking, one must say “of course”. The two points in question are far from each other, so the colors they receive must be more or less independent. However, this intuition can be misleading and in fact false in higher dimensions. There is an impressive literature about the long-range correlation on problems of this type.
Another problem that I like (incidentally posted by myself :-)) is the following: Let be a large square matrix of size whose entries are independent random bits (taking values with probability . Prove that with probability tending to 1, has at least 2 real eigenvalues. (The truth must be approximately where ; this was proved for random Gaussian matrices by combining results of Edeman et. al. and Forrester et. al.; Terry and I could extend the result for random variables matching the first four moments of Gaussian, in particular, we can handle matrices where .)
(4) Finally, a de-proof (well I am not sure this is a legitimate word, but pretty suggestive). Given a set of points on the plane, one would like to connect these points by segments with minimum total length (minimum spanning tree). This problem is easy to solve algorithmically, and assume that the optimal total length is . The surprising thing is that one can do better by adding more points to the set. Let be the new optimum (subject to all possible extensions). There are many examples where . It is conjectured that ; commonly referred to as the Eucledian Steiner tree conjecture. The problem perhaps came from Bell Labs, motivated by applications in telephone networks. More than 20 years ago, Du and Hwang claimed to prove the conjecture (it was big enough to be reported by New York Times). However, recently Ivanov and Tuzhilin found a gap in the proof and the problem has become open again.
(To be continue.)