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

triangles.

** 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.