Notes of Noga Alon’s lecture

The following 3 posts are notes from a day organized by Julia Wolf and Bernadette Charron-Bost at Ecole Polytechnique, july 4th, 2012, web page.

The speakers were Noga Alon, Prasad Tetali and Jacob Fox.

On graphs, integers and communication

1. Induced matchings

Graphs are finite. An induced matching is a set of disjoint edges so that no other edge has both its endpoints covered by the matching.

Question: How dense can a graph be, if its set of edges is a disjoint union of large pairwise disjoint induced matchings ?

Theorem 1 (Rusza-Szemeredi 1978) If each matching is of size ${cn}$, the number of matchings is at most ${o(n)}$. Here ${o(n)\leq O(n/(\log^* n)^{1/5})}$.

Fox 2011 has improved this to ${O(n/\log \log\cdots\log n)}$ with ${O(\log(1/c))}$ times iterated logarithm.

1.1. ${3}$-term arithmetic progressions

Rusza-Szemeredi 1978 implies

Theorem 2 (Roth 1954) ${X}$ subset of ${{\mathbb Z}_n:={\mathbb Z}/n{\mathbb Z}}$, no ${3}$-term arithmetic progressions implies ${|X|=o(n)}$.

Proof: Let ${A}$ and ${B}$ be copies of ${{\mathbb Z}_n}$, form bipartite graph. For ${a\in{\mathbb Z}_n}$, let ${M_a}$ be the matching if all edges ${(a+x,a+2x)}$ with ${x\in X}$.

1. These matchings are pairwise disjoint.

2. If ${X}$ contains no ${3}$-term arithmetic progressions, then each ${M_a}$ is an induced matching.

Theorem 3 (Behrend 1946) There is a subset ${X}$ in ${{\mathbb Z}_n}$ with no ${3}$-term arithmetic progressions, of size

$\displaystyle \begin{array}{rcl} |X| \geq \frac{n}{e^{O(\sqrt{\log n})}}=n^{1-o(1)}. \end{array}$

Therefore, there is a graph with ${n^{2-o(1)}}$ edges consisting of ${\Omega(n)}$ pairwise disjoint matchings, each of size ${n^{1-o(1)}}$.

By connecting all endpoints of each ${M_a}$ to a new point ${a'}$, we get a graph with ${O(n)}$ vertices and ${n^{2-o(1)}}$ edges, in which every edge lies in a unique triangle. To destroy all triangles in this graph, one must delete ${\epsilon n^2}$ edges, and the graph contains only

$\displaystyle \begin{array}{rcl} \exp(\Omega(\log(1/\epsilon)))n^3 \end{array}$

triangles.

1.2. Graph property testing

Objective (Goldreich-Goldwasser-Ron 1996): Distinguish between graphs that satisfy a property from those which are ${\epsilon}$-far from satisfying it, by inspecting the induced subgraph on a random sample of only ${f(\epsilon)}$ vertices.

${\epsilon}$-far means that at least ${\epsilon n^2}$ edges must be deleted to get a graph satisfying the property.

A graph property is said to be easily testable if ${f}$ is a polynomial.

Example: Being ${H}$-free is testable.

From Behrend’s construction, it follows that being triangle free is not easily testable.

Theorem 4 (Alon) ${H}$-freedom is easily testable ${\Leftrightarrow}$ ${H}$ is bipartite.

Open question: Characterize all the easily testable graph properties.

There is no good conjecture. Here is a sample result.

Theorem 5 (Goldreich-Goldwasser-Ron 1996) ${k}$-colorability is easily testable.

Alon-Shapira 2006, Alon-Fox (2012): Being induced ${H}$-free is easily testable ${\Leftrightarrow}$ ${H}$ is a path of length 1, 2, 3 or its complement (with one possible exception).

1.3. Nearly complete graphs

Back to our initial question about induced matchings.

Trivial: Assume each matching contains ${>n/3}$ edges. Then there can be at most one matching.

Easy: Assume each matching contains ${>(\frac{1}{4}+\epsilon)n}$ edges. Then there can be at most ${C(\epsilon)}$ matchings. (This is sharp, below ${(\frac{1}{4}-\epsilon)n}$, there can be much more matchings).

So it seems

Conjecture (Meshulam): ${\Omega(n^2)}$ edges and ${n^\epsilon}$ matchings.

This is far from being true, as the following theorem shows.

Theorem 6 (Alon, Moitra-Sudakov 2012) There exists a graph with

$\displaystyle (1-o(1))\begin{pmatrix} n \\ 2 \end{pmatrix}$

edges which is a union of ${(1-o(1))n}$ disjoint induced matchings.

For all ${\epsilon>0}$, one can cover a complete graph with ${C(\epsilon)}$ graphs, each of which is a union of ${O(n^{1+\epsilon})}$ disjoint induced matchings.

Based on ideas of Fox and Loh (2011), following Behrend.

1.4. Shared communication channels

Now we indicate an application of previous considerations.

A shared channel has ${n}$ sources ${s_i}$ and ${n}$ destinations ${t_j}$. ${s_i}$ has a message ${m_{ij}}$ to send to ${t_j}$. This is implemented by constructing several networks ${G_p}$. Only one source transmits at each round. This means that each message respresents an induced matching.

So the objective is to cover the complete bipartite graph with a small number ${r}$ of induced matchings. We need at least ${n}$ and at most ${n^2}$ induced matchings.

Birk-Linial-Meshulam 1993: For ${r}$ graphs, number of required induced matchings is ${O(n^2 / (\log n)^{r-1})}$.

Our results improve this.

1.5. Open problems

Get sharper bounds on number of disjoint induced matchings of a given size ${t}$. This may improve known bounds on sets without 3-arithmetic progressions, on testability of graph properties and on shared communication channels.

1.6. Questions from the audience

In the definition of ${\epsilon}$-far, if ${\epsilon n^2}$ is change to ${\epsilon\log n}$ are anything small, does this makes a big change ? Answer: yes. With such a changen one needs substantially larger samples.

Do all the best examples come from sets of integers without 3-arithmetic progressions ? Answer: yes. But we do not understand much.