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 be a 0/1 matrix with 1’s on the -th row, then
The permanent equals the number of generalized diagonals. Define a random variable on that set by
Given , can take at most different values, where is the number of unshadowed spots in the -th row. Therefore
Next we permute coordinates, becomes a variable over the set of permutations, and we estimate the expectation of . After permutation, the -row becomes an other row, uniformly. Therefore .
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 vertices contains an acyclic sub-tournament on vertices. This is sharp up to a factor of : There exist tournaments on vertices which do not contain any acyclic sub-tournament on vertices.
Proof: Probabilistic method.
One can represent a tournament by a -matrix of signs . A cycle is a set of columns.
is acyclic , .
Definition 4 A 2-tournament is an orientation of all 2-faces of a complete simplex.
Again, one can represent a tournament by a -matrix of signs .
2.1. Hyperplane arrangements
Let be the diagonal hyperplanes in . 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 , consider hyperplanes .
Proposition 6 Cells of the complement are in 1-1 correspondence with acyclic -tournaments.
Question. What is the fundamental group in the complex picture ?
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 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
in a -regular graph. So, for regular graphs, expansion is a sparsity property: few internal edges.
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 do there exist arbitrarily large -dimensional complexes with as links ?
Definition 8 A -Steiner triple system is a collection of triples such that every pair is covered exactly times.
Question. What does a typical -Steiner triple system look like ?
For a long time, I thought that Steiner triple systems were uninteresting. I am changing my mind.