Extermal Combinatorics II: Some Geometry and Number Theory

Extremal 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’ A} be?

If A={1,2,…,n} |A+A|=2n-1. Suppose the elements of A are and . Note that   . So we identified 2n-1 distinct elements in A+A. This is the Cauchy-Davenport theorem.  

Problem II: Given a set A of n positive real numbers, how small can be the set A A={a a’: a,a’ 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 A|) be? 

This problem was asked by Erdös, and in hindsight it is a very good problem. Erdös conjectured that the maximum behaves like , and this is open.  We will see below a wonderful proof by Elekes that the maximum is (up to a multiplicative constant) at least . The exponent 5/4 was improved twice(!!) by Jozsef Solymosi and there is a very nice post about his most recent ingenious proof for a lower bound max (|A+A|, |A A|)  in Izabella Laba’s blog. 

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 where  is a point  is a line and .

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.

Pushing Behrend Around

Erdos and Turan asked in 1936: What is the largest subset of {1,2,…,n} without a 3-term arithmetic progression?

In 1946 Behrend found an example with 

Now, sixty years later, Michael Elkin pushed the the factor from the denominator to the enumerator, and found a set with   !

Here is a description of Behrend’s construction and its improvment as told by Michael himself:

“The construction of Behrend employs the observation that a sphere in any dimension is convexly independent, and thus cannot contain three vectors  such that one of them is the arithmetic average of the two other. The new construction replaces the sphere by a thin annulus. Intuitively, one can produce larger progression-free sets because an annulus of non-zero width contains more integer points than a sphere of the same radius does. However,

From Helly to Cayley IV: Probability

I decided to split long part III into two parts. This (truly) last part of this series deals with probabilistic problems and with combinatorial questions regarding higher Laplacians. 

21. Higher Laplacians and their meanings

Our high dimensional extension to Cayley’s theorem reads:

The right hand side of our formula corresponds to the eigenvalues of a higher Laplacian of a complete d-dimensional complex with n vertices. In several general cases there are nice expressions for these eigenvalues - for matroidal complexes, for shifted complexes, for complete skeleta of the cubes and in other cases. There are also nice general high-dimensional matrix-tree theorems.

If is the space of k cycles and we identify it via a certain inner product with the space of k-cocycles, then we can talk about the Laplacian defined by latex where is the boundary operator from to and is the coboundary operator from to . 

Spectra of graphs’ Laplacians are very important, for understanding random walks on graphs, for expansion properties and they are also related to many graph parameters like the diameter. The recent series of posts on Luca Trevisan’s blog give a detailed description of these connections (See also this post on James Lee’s blog.) What about higher Laplacians? (Those do not correspond to connectivity but to higher homology groups.) 

What is the analog of the random walk interpretation of the spectral gap?

What is the analog of the relation between the spectral gap and expansion properties?

What is the analog of the diameter?   

22. Probabilistic questions

 Consider the class G of all d-dimensional simplicial complexes on n labelled vertices with d-faces and a complete (d-1)-skeleton. Is there a substantial probability, for d>1,  that a random complex in G with the property that every (d-1)-face is contained in a d-face (no isolated (d-1)-faces) is Q-acyclic? This is not the case for graphs (d=1). The probability for a graph with n vertices and n-1 edges to be a tree tends to 0 even if it has no isolated vertices. This question has a similar flavour to results regarding singularity of random matrices with 0,1 entries.

Here are other natural probabilistic questions that go back to my old paper.

Inside G consider  

A) The class of collapsible complexes

B) The class of contractible complexes

Helly, Cayley, Hypertrees, and Weighted Enumeration III

This is the third and last part of the journey from a Helly type conjecture of Katchalski and Perles to a Cayley’s type formula for “hypertrees”.  (On second thought I decided to divide it into two devoting the second to probabilistic questions.) This part will include several diversions, open problems, and speculations.  

11. How to make it work - the matrix tree theorem

Our high dimensional extension to Cayley’s theorem reads:

where the sum is over all d-dimensional simplicial complexes K on n labelled vertices, with a complete (d-1)-dimensional skeleton, and which are Q-acyclic, namely all their (reduced) homology groups with rational coefficients vanish.  

Looking at the various proofs of Cayley’s formula (there are many many many beautiful proofs), the proof that I know to apply is the one based on the matrix tree theorem.

Consider the signed incidence matrix A’ between all (d+1)-subsets and all d-subsets of {1,2,…,n} that represents the boundary operator of simplicial homology. The rank of this matrix is , 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 Cauchy-Binet Formula.

The eigenvalues of  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 is indeed .

The many square determinants correspond to d-dimensional simplicial complexes K on our labelled set of vertices, which satisfy 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.

Emily Peters presents the matrix-tree theorem. From “The Sarong Theorem Archive” - an electronic archive of images of people proving theorems while wearing sarongs.

 

12. An even simpler use of Cauchy-Binet worth knowing

Consider the 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 paper by Turan. (I am not aware of a similar formula for the fourth power of the size of the homology groups for hypertrees.) Much is known about the determinant and related properties of random 0-1 matrices and the analogy between torsion in the homology groups of random complexes and determinants of random matrices looks like a good analogy.

13. Torsion

One consequence of the formula compared to the total number of available simplicial complexes is that the torsion group is typically huge. (For d>1, the expected value of 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.)

How should we think about torsion in homology? It seems that thinking about the size of the torsion as a behaving like the determinant of a random matrix, may give a good intuition for many cases.

14. Extending other proofs for Cayley’s theorem?     

Cayley’s counting trees theorem has many wonderful proofs.  Can any other proof extend to the case of Q-acyclic simplicial complexes? For example, one proof relies on the exponential theorem that relates the exponential generating functions for connected and general graphs with a certain property P. (Followed by the Lagrange inversion formula.) Is there an analog of the exponential formula when connectivity is replaced by higher homology? Is there any analog of Prüfer sequences? I am not aware of any other proof that works.

15. Weights to the rescue of other conjectures? 

Can we use subtle weights to save other promising but false enumerative conjectures? The farthest reaching fantasy in this direction

Euler’s Formula, Fibonacci, the Bayer-Billera Theorem, and Fine’s CD-index

 

Bill Gessley proving Euler’s formula (at UMKC)

 

In the earlier post about Billerafest I mentioned the theorem of Bayer and Billera on flag numbers of polytopes. Let me say a little more about it.

1. Euler

Euler’s theorem asserts that for a 3-polytope P

V-E+F=2.  

The extension to d-dimensions asserts that for every d-polytope

The Euler Relation: 

There were several incomplete proofs of Euler’s theorem in the late 19th century, but the first complete proof came via Poincare’s work in algebraic topology and the Euler-Poincare theorem. Later, simple geometric proofs were found and the gap in certain 19th theory proofs which relied on an unproved assumption of shellability was completed when Bruggesser and Mani proved in 1970 that the boundary of every d-polytope is shellable.

 

2. Fibonacci

 

Let’s move now to flag numbers. Consider a d-polytopes P. for a set {-1,0,1,2,…,d-1,d}, { } , , define the flag number as the number of chains of faces , where .  We will assume from now on that S contains both ‘-1′, and ‘d’. (Adding or deleting these entries from S does not change the value of the flag number.) Let  be the dth Fibonacci number. (, , , , etc.)  Bayer and Billera proved:

Theorem: the affine dimension of flag numbers of d-polytopes is

There are many linear relations among the flag numbers that are implied by Euler’s theorem. For example: . This follows from the fact that every 1-polytope has 2 vertices. (This is Euler’s formula for dimension 1.) Another example: . This follows from the fact that a polygon has the same number of vertices as edges which is Euler’s formula for d=2. Here are two, more complicated, examples: and . Let’s understand the first of the two: Fix a flag of faces

Helly’s Theorem, “Hypertrees”, and Strange Enumeration II: The Formula

In the first part of this post we discussed an appealing conjecture regaring an extension of Cayley’s counting trees formula. The number of d-dimensional “hypertrees” should somehow add up  to  . But it was not clear to us which complexes we want to count and how. This counting problem started from a Helly type conjecture proposed by Katchalski and Perles.
For d=2 n=6 the situation was confusing. We had 46608 complexes that were collapsible. Namely, for these complexes it is possible to delete all triangles one at a time by removing in each step a triangle T and an edge E which is contained only in T. Once all triangles are removed we are left with a spanning tree on our 6 vertices. (Five out of the 15 edges survive).  In addition, there were 12 simplicial complexes representing 6-vertex triangulations of the real projective plane. 
We will continue the discussion in this part, show how the conjecture can be saved and at what cost. We will also discuss the solution of the Perles-Katchalski conjecture -  a Helly’s type conjecture that we started with.   In the third part we will explain the proof and mention further related results and problems, discuss higher Laplacians and their spectrum, and mention a few related probabilistic problems.  
 
 

 We ended part one with the question “What can we do?”

8. How to make the conjecture work

With such a nice conjecture we should not take no for an answer. To make the conjecture work we need to count each of the twelve 6-vertex triangulations of the real projective plane, four times. Four is the square of the number of elements in . This is the difference in higher dimensions, a Q-acyclic complex need not be Z-acyclic. Homology groups can have non trivial torsion.  In our case can be a non trivial finite group.
Here is the theorem:   

where the sum is over all d-dimensional simplicial complexes K on n labelled vertices, with a complete (d-1)-dimensional skeleton, and which are Q-acyclic, namely all their (reduced) homology groups with rational coefficients vanish.  
Looking at the various proofs of Cayley’s formula (there are many many many beautiful proofs and more), which one (or more) would you expect to extend to the high dimensional case? We will answer this question in part III. Can you guess?

Helly’s Theorem, “Hypertrees”, and Strange Enumeration I

1. Helly’s theorem and Cayley’s formula

Helly’s theorem asserts: For a family of n convex sets in , n > d, if every d+1 sets in the family have a point in common then all members in the family have a point in common.

Cayley’s formula asserts: The number of  trees on n labelled vertices is .

In this post (in two parts) we will see how an extension of Helly’s theorem has led to high dimensional analogs of Cayley’s theorem. 

  

left: Helly’s theorem demonstrated in the Stanford Encyclopedia of Philosophy (!), right: a tree 

2. Background

This post is based on my lecture at Marburg. The conference there was a celebration of new doctoral theses

A Small Debt Regarding Turan’s Problem

Turan’s problem asks for the minimum number of triangles on n vertices so that every 4 vertices span a triangle. (Or equivalently, for the maximum number of triangles on n vertices without a “tetrahedron”, namely without having four triangles on four vertices.)  When we discussed Turan’s problem, we stated a lemma without giving the proof. Here is the proof.

Lemma: A three uniform hypergraph G on n vertices, so that every four vertices span a triangle satisfies:

.

Here, K is the simplicial complex on the n vertices which has all possible edges and, in addition, the triangles in G. F can be any field of coefficients, below we assume that F=Z/2. (But very little changes are required for the general case.)

Proof:  A little background: The space of 1-dimensional cycles of the complete graph with n vertices is of dimension . Start with the star T where vertex ‘1′ is adjacent to all other vertices. every edge e={i,j} not in T, determines a cycle c(e) supported by the triangle {1,i} {1,j} and {i,j}. It is easy to see that all these cycles are linearly independent in the space of cycles of the complete graph and span this space.

Now to the proof itself. Let G be a hypergraph with the property that every 4 vertices span a triangle and let K be the 2-dimensional simplicial complex obtained by adding the triangles in G to the complete graph. is still spanned by the cycles c(e) for all edges e={i,j} . Let H be a maximal set of edges e so that all the corresponding c(e) are linearly independent in . It suffices to prove:

Claim: H is a forest.

Powers of Euler Products and Han’s Marked Hook Formula

I heard from Dan Romik and Richard Stanley about a very exciting development in enumerative combinatorics. It is quite amazing how new uncharted sections of the gold mine of tableaux, hooks, partitions, and permutations are repeatedly being discovered. Guo-Niu HAN proved the following:

Here, the first sum runs over all partitions of n, is the number of standard young tableaux corresponding to , and the second sum runs over all hook lengths of the Ferrers diagram corresponding to . Of course, this formula reminds us of the classical result , and of the hook formula for the value of itself. 

Han’s result is one of many exciting other applications of a recent remarkable formula for Euler’s product raised to an arbitrary complex power , via an expansion based on tableaux. This later formula was first discovered by Nekrasov and Okounkov in the context of Seiberg-Witten theory, and was later rediscovered by Han himself who provided another proof, and presented many remarkable applications. It also gives new proofs and new perspectives to several classical formulas regarding powers of Euler products going back to Euler himself, Jacobi, Ramanujan, and more recently, Macdonald, Kostant and many others.

Added July 11, long overdue: Dan showed me the actual general Nekrasov-Okounkov’s formula, hints regarding Han’s proof, and how the marked hook formula is derived. The general formula for powers of Euler products goes like this: The proof relies on a formula of Macdonald for the case that and is an odd integer. Macdonald found a beautiful expansion in this case of the form  , where   referred to as “t-coding” meaning that the sum of all is 0 modulo t, and . Anyway, once the “hook expansion” is derived using Macdonald’s formula for the spaciel case of squares of odd integers it extends automatically to all . The marked hook formula is derived by looking at the coefficients of .

There is a nice anekdote related to Ian Macdonald. At a conference

Nati’s Influence

   

 

When do we say that one event causes another? Causality is a topic of great interest in statistics, physics, philosophy, law, economics, and many other places. Now, if causality is not complicated enough, we can ask what is the influence one event has on another one.  Michael Ben-Or and Nati Linial wrote a paper in 1985 where they studied the notion of influence in the context of collective coin flipping. The title of the post refers also to Nati’s influence on my work since he got me and Jeff Kahn interested in a conjecture from this paper.  

Influence 

The word “influence” (dating back, according to Merriam-Webster dictionary, to the 14th century) is close to the word “fluid”.  The original definition of influence is: “an ethereal fluid held to flow from the stars and to affect the actions of humans.” The modern meaning (according to Wictionary) is: ”The power to affect, control or manipulate something or someone.”

 

Ben-Or and Linial’s definition of influence

Collective coin flipping refers to a situation where n processors or agents wish to agree on a common random bit. Ben-Or and Linial considered very general protocols to reach a single random bit, and also studied the simple case where the collective random bit is described by a Boolean function 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′.