Extermal Combinatorics II: Some Geometry and Number Theory
July 17, 2008Extremal problems in additive number theory
Our first lecture dealt with extremal problems for families of sets. In this lecture we will consider extremal problems for sets of real numbers, and for geometric configurations in planar Euclidean geometry.
Problem I: Given a set A of n real numbers, how small can the set A+A={a+a’: a,a’ 
If A={1,2,…,n} |A+A|=2n-1. Suppose the elements of A are 
Problem II: Given a set A of n positive real numbers, how small can be the set A 
You may protest (again, like in the first lecture,) that I regard problem II a different problem. You can move from problem II to problem I by taking the logarithm of all elements in A, or you can simply use the same proof with the sum replaced by a product. The proof relies only on very basic monotonicity properties of these operations.
OK, lets have another problem II.
Problem II: Given a set A of n real numbers, how small can the quantity max (|A+A|, |A 
This problem was asked by Erdös, and in hindsight it is a very good problem. Erdös conjectured that the maximum behaves like 
Extremal problems in plane geometry
Problem III: Given n points in the plane what is the maximum number of pairs among them at distance ‘1′
Problem IV: Given s points and t lines in the plane what is the maximum number of incidences between them.
An incidence is a pair 
Problem V: Given a graph G with v vertices and e edges what is the minimum number of crossings in a planar drawing of G.
The second of my extremal combinatorics lectures was devoted to the surprising connections that were found between the above problems. There is also a very nice post about this material on Terry Tao’s blog. To show you something new I will describe a few problems in higher dimensions at the end.
, and just like in the ordinary matrix tree theorem you delete rows to be left with linearly independent rows. Here you delete all rows corresponding to sets containing ‘n’ and you are left with a matrix A. Now we compute the determinant of 
directly, and compare the result to a computation based on the 
are the eigenvalues of the d-th Laplacian of the complete d-dimensional simplicial complex with n vertices. It is easy to inspect what they are and the determinant of 
.
and 
. Now if K has non-vanishing d-th homology, the determinant is zero. If K is a Q-acyclic simplicial complex (i.e., its (reduced) homology groups with rational coefficients are trivial) then it has a non zero determinant. So far, it is like trees, but next comes a surprise. The contribution of K is the square of the number of elements in 
, the (d-1)th homology group of K. This torsion group is finite, but for d >1 it need not be trivial.
matrix A, whose columns are all +1 -1 vectors of length n. Computing 
, via Cauchy-Binet Formula (or by other easy methods) asserts that the expected value 
for all 
+1/-1 matrices behaves roughly like 
. This was observed by Turan and Szekeres who also found a formula for the sum of the fourth powers of all 0-1 n by n matrices. See a leter 
for Q-acyclic complexes counted by the formula, is asymptotically larger than 
; I am not aware of explicit examples with such a huge torsion group.)
of n bits, one contributed by every agent. If all agents act appropriately the collective bit will be ‘1′ with probability 1/2. The purpose of collective coin flipping is to create a random bit R which is immune as much as possible against attempts of one or more agents to bias it towards ‘1′ or ‘0′. 
conjecture
has a k-dimensional face which is either a simplex or combinatorially isomorphic to a k-dimsnional cube.
, is it true that 
?
bounded from above by some absolute constant? 
of subsets of 
such that every two sets in 
