Notes of Nati Linial’s Lille lecture nr 2

1. Proof of Bregman’s theorem, continued

A proof of Bregman’s theorem can be found in Alon and Spencer’s book. Although I taught it several times, for a long time, I felt I did not understand that proof. Once, Zur Luria reformulated that proof, and I understood it, since we could treat the generalization. On the other hand, I consider I still do not understand lower bounds, i.e. Van der Waerden’s conjecture.

Theorem 1 (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}

The permanent equals the number of generalized diagonals. Define a random variable {X_i} on that set by

\displaystyle  \begin{array}{rcl}  X_i = j \Leftrightarrow \textrm{the generalized diagonal picks } a_{ij}=1. \end{array}

Given {X_1,\ldots,X_{i-1}}, {X_i} can take at most {N_i} different values, where {N_i} is the number of unshadowed spots in the {i}-th row. Therefore

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

Next we permute coordinates, {N_i} becomes a variable over the set of permutations, and we estimate the expectation of {N_i(\sigma)}. After permutation, the {i}-row becomes an other row, uniformly. Therefore {\mathop{\mathbb P}(N_i =t)=\frac{1}{r_i}}.

2. Tournaments

Imre Leader defined higher dimensional tournaments. With my student A. Morgenstern, we defined acyclic higher dimensional tournaments. I will not give this definition today, this section is merely a teaser.

Definition 2 A tournament is an orientation of all edges of a complete graph. A tournament is acyclic if there are no oriented cycles.

Here is an easy

Theorem 3 Every tournament on {n} vertices contains an acyclic sub-tournament on {\log_2 n} vertices. This is sharp up to a factor of {2}: There exist tournaments on {n} vertices which do not contain any acyclic sub-tournament on {\log_2 n} vertices.

Proof: Probabilistic method.

One can represent a tournament by a {n\times \frac{n(n-1)}{2}}-matrix of signs {A}. A cycle is a set of columns.

{T} is acyclic {\Leftrightarrow} {AX=0}, {X\geq 0} {\Rightarrow X=0}.

Definition 4 A 2-tournament is an orientation of all 2-faces of a complete simplex.

Again, one can represent a tournament by a {\frac{n(n-1)}{2}\times\frac{n(n-1)(n-2)}{6}}-matrix of signs {A}.

2.1. Hyperplane arrangements

Let {H_{ij}=\{x_i=x_j\}} be the diagonal hyperplanes in {{\mathbb R}^n}. We are interested in the complement. There is a 1-1 correspondence between the cells of this arrangement and acyclic 1-tournaments. The complex picture is even more interesting: it is connected, but the fundamental group is the pure braid group of topologists.

Definition 5 In {{\mathbb R}^{\frac{n(n-1)}{2}}}, consider hyperplanes {H_{ijk}=\{x_i +x_j=x_k\}}.

Proposition 6 Cells of the complement are in 1-1 correspondence with acyclic {2}-tournaments.

Question. What is the fundamental group in the complex picture ?

3. Expanders

Although universal, expanders are intimately connected to theoretical computer science. In the 1970’s, L. Valiant tried to prove lower bounds in computational complexity based on the non-existence of expanders….

A simplicial complex on vertex set {V} is a family of subsets which is stable under taking subsets. There are several competing definitions of expansion for simplicial complexes. They tend to generalize the spectral characterization of expansion for regular graphs. I consider this characterization as a low dimensional miracle which need not reproduce in higher dimension. I think sparsity offers a better trail. Expansion is equivalent to sparsity: If many edges point outwards arbitrary subsets, then few edges point inwards, since

\displaystyle  \begin{array}{rcl}  e(S,\bar{S})+2e(S)=d|S| \end{array}

in a {d}-regular graph. So, for regular graphs, expansion is a sparsity property: few internal edges.

3.1. Regularity

What is a regular simplicial complex ?

We must settle this question before addressing the next one: What does a typical regular simplicial complex look like ?

Attempt for a

Definition 7 Regularity: All links are the same.

Question. For which graphs {H} do there exist arbitrarily large {2}-dimensional complexes with {H} as links ?

Definition 8 A {d}-Steiner triple system is a collection of triples such that every pair is covered exactly {d} times.

Question. What does a typical {d}-Steiner triple system look like ?

For a long time, I thought that Steiner triple systems were uninteresting. I am changing my mind.


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
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: Logo

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s