Skip to content

Oberwolfach: what happens in combinatorics

Tháng Một 8, 2014

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 V and three parameters k, t, \lambda, a design is a collection F of subsets of size k of V such that every t-tuple of points in V appears in exactly \lambda  sets. A famous  example is finite projective plane, where t=2 and \lambda =1 (through every two points there are exactly one line).  It is easy to see that the size of F 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 M be a big matrix whose rows are indexed by the k-subsets of V and the columns are indexed by the t-subsets, and the entry in the intersection of a k-set A and a t-set B equals 1 if A contains B and 0 otherwise.  One needs to find a collection of n= |F| 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 N \times M matrix, when can we find a collection of n \ll N rows whose mean equal the mean of all rows ? Thinking probabilistically, what is the chance of a random set of n rows does the job ?  With a bit handwaving, one can think of  a set of rows obtained by selecting each row with probability p = n/N. Let v_i be row i (as a vector in R^M) and assume that the mean is 0. Then we are talking about estimating the probability that the sum of  x_i v_i  equals 0, where \xi_i, 1 \le i \le N, are iid indicator random variables with mean p. 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 v_i.  At the end, this gives an asymptotic value  for the number of designs if \lambda is sufficiently large (something of order |V|^t , 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 R^d and let f_i be the number of subsets of i independent vectors. It is conjecture that the sequence f_i is log-concave,namely f_i^2 \ge f_{i-1} f_{i+1} . 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 G be an n \times n grid. Seen as a graph, G 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 1/3 as n 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 M_n be a large square matrix of size n whose entries are independent random bits (taking values \pm 1 with probability 1/2. Prove that with probability tending to 1, M_n has at least 2 real eigenvalues. (The truth must be approximately c\sqrt n where c ^2 = 2/\pi; 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 0, \pm 1 matrices where P(1)= P(-1) =1/6.)

(4) Finally, a de-proof (well I am not sure this is a legitimate word, but pretty suggestive).   Given a set of n 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 L. The surprising thing is that one can do better by adding more points to the set. Let L' be the new optimum (subject to all possible extensions). There are many examples where L/L' >1. It is conjectured that L/L' < 2/ \sqrt 3;  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.)


From → Không phân loại

Gửi bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập: Logo

Bạn đang bình luận bằng tài khoản Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

%d bloggers like this: