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.
Let us start with Noga Alon.
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 , the number of matchings is at most . Here .
Fox 2011 has improved this to with times iterated logarithm.
1.1. -term arithmetic progressions
Rusza-Szemeredi 1978 implies
Theorem 2 (Roth 1954) subset of , no -term arithmetic progressions implies .
Proof: Let and be copies of , form bipartite graph. For , let be the matching if all edges with .
1. These matchings are pairwise disjoint.
2. If contains no -term arithmetic progressions, then each is an induced matching.
Theorem 3 (Behrend 1946) There is a subset in with no -term arithmetic progressions, of size
Therefore, there is a graph with edges consisting of pairwise disjoint matchings, each of size .
By connecting all endpoints of each to a new point , we get a graph with vertices and edges, in which every edge lies in a unique triangle. To destroy all triangles in this graph, one must delete edges, and the graph contains only
1.2. Graph property testing
Objective (Goldreich-Goldwasser-Ron 1996): Distinguish between graphs that satisfy a property from those which are -far from satisfying it, by inspecting the induced subgraph on a random sample of only vertices.
-far means that at least edges must be deleted to get a graph satisfying the property.
A graph property is said to be easily testable if is a polynomial.
Example: Being -free is testable.
From Behrend’s construction, it follows that being triangle free is not easily testable.
Theorem 4 (Alon) -freedom is easily testable 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) -colorability is easily testable.
Alon-Shapira 2006, Alon-Fox (2012): Being induced -free is easily testable 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 edges. Then there can be at most one matching.
Easy: Assume each matching contains edges. Then there can be at most matchings. (This is sharp, below , there can be much more matchings).
So it seems
Conjecture (Meshulam): edges and matchings.
This is far from being true, as the following theorem shows.
Theorem 6 (Alon, Moitra-Sudakov 2012) There exists a graph with
edges which is a union of disjoint induced matchings.
For all , one can cover a complete graph with graphs, each of which is a union of 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 sources and destinations . has a message to send to . This is implemented by constructing several networks . 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 of induced matchings. We need at least and at most induced matchings.
Birk-Linial-Meshulam 1993: For graphs, number of required induced matchings is .
Our results improve this.
1.5. Open problems
Get sharper bounds on number of disjoint induced matchings of a given size . 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 -far, if is change to 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.