Notes of Nati Linial’s Lille lecture nr 1

Geometry and combinatorics

The theory of expander graphs gives us an idea of the impact combinatorics may have on the rest of mathematics in the future.

Most existing combinatorics deals with one-dimensional objects. Understanding higher dimensional situations is important. In particular, random simplicial complexes.

1. Permutations

In a hike, the most dangerous moment is the very beginning: you might take the wrong trail. So let us spend some time at the starting point of combinatorics, permutations.

A permutation matrix is nothing but an {n\times n}-array of 0’s and 1’s, with exactly one 1 in each row or column.

This suggests the following {d}-dimensional generalization: Consider {[n]^{d+1}}-arrays of 0’s and 1’s, with exactly one 1 in each row (all directions).

How many such things are there ? For {d=2}, this is related to counting latin squares. A latin square is an {n\times n}-array of integers in {[n]} such that every {k\in[n]} appears exactly once in each row or column. View a latin square as a topographical map: entry {a_{ij}} equals the height at which the nonzero entry of the {n\times n\times n} array sits.

In van Lint and Wilson’s book, one finds the following asymptotic formula for the number of latin squares.

\displaystyle  \begin{array}{rcl}  |S_n^2|=((1+o(1))\frac{n}{e^2})^{n^2}. \end{array}

This was an illumination to me. It suggests the following asymptotic formula for the number of generalized permutations.

Conjecture:

\displaystyle  \begin{array}{rcl}  |S_n^d|=((1+o(1))\frac{n}{e^d})^{n^d}. \end{array}

We can merely prove an upper bound.

Theorem 1 (Linial-Zur Luria)

\displaystyle  \begin{array}{rcl}  |S_n^d|\leq((1+o(1))\frac{n}{e^d})^{n^d}. \end{array}

This follows from the theory of the permanent

2. Permanent

Definition 2 The permanent of a square matrix is the sum of all terms of the determinants, without signs.

It is important, though naive looking. If {A} is the incidence graph of a bipartite graph {G}, {Per(A)} is the number of perfect matchings of {G}.

There are two major questions concerning bounds on permanents.

2.1. Van der Waerden’s conjecture

Van der Waerden conjectured in the 1920’s and Faligman, Egorychev proved in the 1970 the following lower bound.

Definition 3 An {n\times n} matrix is doubly stochastic if it is nonnegative and all rows and columns add up to 1.

Easy observation: If {A} is doubly stochastic, its permanent is {>0}. By compactness, there is a positive minimum. Van der Waerden conjecti

Theorem 4 (Faligman, Egorychev) If {A} doubly stochastic, then

\displaystyle  \begin{array}{rcl}  Per(A)\geq \frac{n!}{n^n}. \end{array}

2.2. Minc’s conjecture

In the 60’s, Minc conjectured and later Bregman proved the following upper bound.

Theorem 5 (Bregman) If {A} be a 0/1 matrix with {r_i} 1’s on the {i}-th row, then

\displaystyle  \begin{array}{rcl}  Per(A)\leq \prod(r_i!)^{1/r_i}. \end{array}

Our upper bound on the number of latin squares ({d=2}) is a simple consequence of these two theorems.

Consider boxes, say {k\times n\times n} arrays of integers, and try to extend them into latin cubes. The next layer is a permutation matrix, with 1’s forbidden if 1 is already used in the same shaft in the box. The number of next layers is the permanent of the matrix {B} obtained from {A} by removing….

2.3. Difficulties in higher dimensions

The above connection between permanent and perfect matchings does not generalize. There exists a {4\times 4 \times 4}-array of 0/1 such that every line has exactly two 1’s but the array does not contains a 2-dimensional permutation. Therefore I suspect that a different proof of the lower bound on the number of latin squares needs to be found.

Here is an other fact which gets difficult in higher dimensions. Doubly stochastic matrices form a convex polytope {\Omega_n}, whose vertices are described by the Birkhoff-von Neumann theorem.

Theorem 6 (Birkhoff-von Neumann) The vertices of {\Omega_n} are permutation matrices.

Triply, {d+1}-ly stochastic {[n]^{d+1}}-arrays are defined in a similar way, but they have much more vertices.

3. Proof of Bregman’s theorem

Next I explain how we could generalise Bregman’s theorem. We were influenced by Schrijver and Radhakrishnan.

3.1. Entropy

My main point is to illustrate the method of entropy. Entropy measures how much information one gets by sampling a random source. Given a probability distribution {p} on some {N}-point set,

\displaystyle  \begin{array}{rcl}  H(p)=-\sum p_i \log p_i. \end{array}

Then {0\leq H\leq \log(N)}. The entropy of a random variable is the entropy of its distribution.

Let {X} be a vector valued random variable. The following (easy) chain rule is essential.

\displaystyle  \begin{array}{rcl}  H(X)=H(X_1)+H(X_2|X_1)+\cdots+H(X_n|X_1,\ldots,X_{n-1}. \end{array}

3.2. Generalized diagonals

In a 0/1 matrix, a generalized diagonal is a sequence of entries, one from every row and colum. {Per(A)} is the number of generalized diagonals.

We must count elements in a large set {\Omega}. If {X} is a uniform random variable in {\Omega}, {|\Omega|=2^{H(X)}}. Here {\Omega} is the set of all generalized diagonals in {A}.

Let us draw generalized diagonals uniformly, yielding {X}. Let

\displaystyle  \begin{array}{rcl}  X_i = j \Leftrightarrow \textrm{ we selected } a_ij=1. \end{array}

Then

\displaystyle  \begin{array}{rcl}  H(X_i|X_1,\ldots,X_{i-1})\leq \log N_i, \end{array}

where {N_i} is the number of viable 1’s in the {i}-th row, or, equivalently, the number of 1’s on the {i}-th row which are not below an other 1 (“in the shadow”). Let us average the inequality

\displaystyle  \begin{array}{rcl}  H(X)\leq \sum \log N_i \end{array}

over all possible arrangements {\sigma} of the rows. Recall {N_i(\sigma)} is the number of non shaded 1’s in row {i} relative to ordering {\sigma}. In other words, it is the rank of our “special runner” in a random ordering of the {r_i} runners. Therefore, the expectation

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}(\log(N_i(\sigma)))=\frac{1}{r_i}(\log 1+\log 2 +\cdots+\log(r_i)), \end{array}

and this proves Bregman’s theorem.

In higher dimensions, it goes more or less the same.

Advertisements

About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See http://www.math.ens.fr/metric2011/
This entry was posted in Course and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s