The following notes are from the Ramsey DocCourse in Prague 2016. The notes are taken by me and I have edited them. In the process I may have introduced some errors; email me or comment below and I will happily fix them.
Title: Bootcamp (3 of 6)
Lecturer: Jaroslav Nešetřil
Date: Friday September 23, 2016.
Main Topics: Point Ramsey for graphs, hypergraphs.
Definitions: Ramsey property for finite structures, Ramsey Class, point-Ramsey, edge-Ramsey, hypergraphs, Chromatic number, Ordering Property.
Definitions and Examples
Structural classes, substructures and embeddings
Throughout the course we will make use of classes of finite structures, such as the class of all finite graphs or the class of all finite arithmetic progressions on . We will also need to describe what we mean by “substructure” in the class . For example in , a substructure of a graph is an induced subgraph. Equivalently, we could instead describe what an “embedding” is in the class . For example, in embeddings are increasing affine maps which means that the substructures are subsets that are also arithmetic progressions. Either way, it will usually be clear from context what we mean by substructure or embedding.
We will present more examples in a moment after introducing a key combinatorial property.
Structural Ramsey property
We say that a class has the (structural) -Ramsey property, for a structure if
such that .
This arrow notation means that for every partition there is a and an such that .
If a class is -Ramsey for all then we say that it is a Ramsey class.
Intuition and mneumonics
To make this easier to process we usually refer to as small, as medium, and as large. It is interesting to look at this property even when is a single point, which corresponds to vertex partitions. (These are in fact the classical Ramsey theorems.) This is called the point-Ramsey property.
The case in where is an edge is also interesting and corresponds to edge partitions.
- The first two classes are Ramsey classes, which is equivalent to the classical Ramsey theorem.
- Finite sets where a substructure is a subset.
- The class of finite linear orders where an embedding is a monotone injection.
- The class of finite arithmetic progressions on . Van der Waerden’s Theorem is equivalent to saying that has the point-Ramsey property.
- The class of finite subsets of together with maps where whenever with . Schur’s Theorem is equivalent to saying that has the point-Ramsey property.
- The class of all finite distributive lattices where a substructure is a sublattice. Hilbert’s Theorem is equivalent to saying that this class has the point-Ramsey property. (See Bootcamp 4 for a precise statement of Hilbert’s Theorem and a proof.)
Exercise: Prove that has no other Ramsey objects.
Van der Waerden has a very nice writeup of his thought process in trying to prove his theorem. It is contained in the Mathematical Coloring Book.
Hypergraphs of the form
We now introduce a special class of hypergraphs constructed from finite structures. These hypergraphs are well suited to capture Ramsey properties as chromatic numbers.
Definition: Let . Define the hypergraph , where
- , and
- if and only if where .
The Ramsey property for is closely related to its chromatic number.
Observation: if and only if .
It is tempting to try to find witnesses to the Ramsey property by using witnesses to the chromatic number. In practice this is difficult, as the next example shows.
Example. Let , be an edge, be a triangle and be . So is 3-uniform and (see here).
This hypergraph also has the peculiar property that if then . This is because if two triangles share two sides, then they must also share the third side.
Other graphs that have been studied
The following graphs can be expressed as graphs, but many cannot be described by finitely many forbidden subgraphs.
- Line graphs, (which can actually be described by nine forbidden subgraphs),
- Interval graphs,
- Kneser graphs,
- Johnson graphs,
- Shift graphs. Vertex set . Two vertices of the shift graph are connected by an edge if . This has no triangles (exercise) but its chromatic number is since “it is coming from “. (See Theorem 5.6 on page 14 of these notes for example.)
Point-Ramsey for some classes of graphs
Let be one of the following classes of finite graphs:
- All graphs,
- all triangle-free graphs,
- all -free graphs,
- all graphs not containing any finite set of forbidden -connected (i.e. no cut points) subgraphs.
The first proof of this was given by Folkman, and then was simplified later. We first state a lemma that will produce a hypergraph with large chromatic number and doesn’t contain short cycles. This type of hypergraph will be used in many arguments. The proof of its existence will be shown in a different lecture and is a hard, probabilistic proof due to Erdos-Hajnal in 1966. This exaplains why Folkman’s original proof was so difficult.
Lemma: Let . There is a hypergraph such that
- it is -uniform, and ,
- has girth at least . That is, it doesn’t contain cycles of length less than .
Note that since any two hyperedges can intersect in at most one point. This lemma also gives another construction for the following corollary.
Proof of theorem. Assume for now that is the class of all finite graphs. The arguments for the others are similar and we will comment on the differences at the end.
Let and let . Use . To show point Ramsey, we will use the chromatic number equivalence given above.
Let be a hypergraph from the lemma. We create a graph on the vertex set by putting a copy of on each hyperedge in . This is well defined since there are no 2-cycles in .
Observe that . Since has high chromatic number, we must have the desired Ramsey property.
Proof for -free. This will be a special case of the next case.
Proof for forbidden -connected graphs. As before, except use .
We claim that contains no graph from . Suppose that is a subgraph of . Consider the induced subhypergraph of where contains all hyperedges from that contain an element of .
Since and has no cycles of length , the subhypergraph must be a tree. Since has no cutpoints, it must be contained completely within one hyperedge of . This contradicts the fact that contained to copies of .
We now introduce a Ramsey property for structures that heuristically fits between point-Ramsey and edge-Ramsey.
- Point-Ramsey. Holds for many classes.
- Ordering property.
- Edge-Ramsey. Holds for some classes.
The ordering property will be stronger than point-Ramsey, but weaker than edge-Ramsey.
Exercise. Find a that witnesses the ordering property for , with the given linear ordering .
- with the single edge and .
- with the single edge and .
- with the single edge and .
- with the edges and .
In the next lecture we will see why the classes of graphs we studied earlier all have the ordering property.