Partite constructions 2 – Ramsey DocCourse Prague 2016

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: Partite consturctions 2 (of 3)

Lecturer: Jaroslav Nešetril

Date: Tuesday October 25, 2016.

Main Topics: There are graphs with large chromatic number but no small cycles, Tutte’s construction, Edge-Ramsey for graphs (using partite construction)

Definitions: No New definitions.

Part 1 – Part 2 – Part 3


Introduction

In lecture 1 [up soon], we motivated the so-called “Partite construction” used in structural Ramsey theory. Today we will look at two examples of this construction: a proof of the Erdos-Hajnal theorem that there are hypergraphs with large chromatic number but no small cycles, and the edge Ramsey property for graphs.

We will start by looking at a related construction due to Tutte from 1947. This will have a similar recursive flavour to the partite construction, without any extra structure to worry about.

Tutte’s construction

Theorem (Tutte, 1947): Let 2 \leq k, n \in \mathbb{N} . There is a graph G=(V, E) such that

  • \chi(G) > k ,
  • G doesn’t contain cycles of length \leq 5 ,
  • \vert V \vert > n .

Proof. The proof will go by recursively constructing a sequence of supergraphs G_2 \leq G_3 \leq \ldots \leq G_k . None of these will contain a cycle of length \leq 5 , \chi(G) > k and \vert V_k \vert \geq \vert V_2 \vert > n .

Fix 2 \leq n \in \mathbb{N} .

Construction of G_2 . Let G_2 be a cycle of length 2n+1 . This has chromatic number >2 .

Construction of G_3 . We will explicitly construct G_3 for clarity, then we will give the general form of G_{k+1} . We will make use of the pigeonhole number for m points and k colours, P(m,k) = k(m-1)+1 . (In this case we have an explicit number, but in further applications this will be replaced by a Ramsey number.)

Let r(3) := 3(2n) + 1 = P(2n+1, 3) . Let V_3 = \left(\{1\} \times r(3)\right) \cup \left(\{0\}\times \binom{r(3)}{2n+1}(2n+1) \right) . (The important part here is that V_3 has lots of room on the 0 -th level, the exact number is not so important.)

The vertices \{1\} \times r(3) will be an independent set. For each (2n+1) -tuple \{(1,v_1), \ldots, (1, v_{2n+1})\} in \{1\} \times r(3) place a copy (V_2^\prime, E_2^\prime) of G_2 above it on the 0 th level, and put add the E_3 edges \{(1,v_i), (v_i^\prime)\} for each i \leq 2n+1 . These added edges go from the 0 th level to the 1 st level. All the added copies of G_2 on the 0 th level will be disjoint (we made sure there was enough room on the 0 th level).

[PICTURE]

Claim. \chi(G_3) > 3 .

Suppose that we have a 3 -colouring \rho of the vertices of G_3 , and we will find an edge where both endpoints have the same colour. In particular we have a vertex colouring of the 1 st level. This level has P(2n+1, 3) many points, so there is a set B of cardinality 2n+1 on level 1 that is monochromatic. Now above B on the 0 th level we added a copy G^\prime_2 of G_2 . It is also 3 -coloured by \rho , but every vertex in G^\prime_2 has an edge to a vertex in B . So really, if \rho is a good colouring, then the vertices of G^\prime_2 are 2 -coloured. Since \chi(G_2) = 3 , there must be an edge here where both endpoints have the same colour.

[PICTURE]

Claim. G_3 doesn’t contain cycles of length \leq 5 .

It is easy to see that the smallest cycles possibly added are of length 6 . (The full argument is below in the G_{k+1} case.)

This process might add 6 -cycles. Let there be an edge between v and w in G_2 . Find disjoint copies of G_2 with corresponding elements (0, v^\prime), (0,w^\prime), (0, v^{\prime\prime}), (0,w^{\prime\prime}) . Assume that each of (0, v^\prime) and (0, v^{\prime\prime}) have an edge to some (1,v_1) and each of (0, w^\prime) and (0, w^{\prime\prime}) have an edge some to (1,w_1) . This gives the 6 -cycle: (0, v^\prime)-(0,w^\prime)-(1,w_1)-(0,w^{\prime\prime})-(0, v^{\prime\prime})-(1,v_1)-(0, v^\prime) .

[PICTURE]

(The assumption that there is a common v_1 and w_1 is purely for notational convenience. We really should have started by looking at all possible pairs (v_1, w_1) and looked to see if they have corresponding connected lifts. A priori, this need not happen, but that means that we aren’t even adding cycles of length 6 .)

Construction of G_{k+1} . Assume we have constructed G_k = (V_k, E_k) as above. Let f(k) = g(n,k) = \vert V_k \vert .

Let r(k+1) := P(f(k), k+1) . Let V_{k+1} = \left(\{1\} \times r(k+1)\right) \cup \left(\{0\}\times \binom{r(k)}{f(k)}(f(k)) \right) .

The vertices \{1\} \times r(k+1) will be an independent set. For each f(k) -tuple \{(1,w_v): v \in V_k \} in \{1\} \times r(k+1) place a copy (V_k^\prime, E_k^\prime) of G_k above it on the 0 th level, and put add the E_{k+1} edges \{(1,w_v), v\} for each v \in V^\prime_k . These added edges go from the 0 th level to the 1 st level. All the added copies of G_k on the 0 th level will be disjoint (we made sure there was enough room on the 0 th level).

Claim. \chi(G_{k+1}) > k+1 .

The proof is by induction on k . Suppose \chi(G_k) > k .

Suppose that we have a k+1 -colouring \rho of the vertices of G_{k+1} , and we will find an edge where both endpoints have the same colour. In particular we have a vertex colouring of the 1 st level of G_{k+1} . This level has P(\vert V_k \vert=f(k), k+1) many points, so there is a set B of cardinality f(k) on level 1 that is monochromatic. Now above B on the 0 th level we added a copy G^\prime_k of G_{k} . It is also k+1 -coloured by \rho , but every vertex in G^\prime_k has an edge to a vertex in B . So really, if \rho is a good colouring, then the vertices of G^\prime_k are k -coloured. Since \chi(G_k) > k , there must be an edge here where both endpoints have the same colour.

Claim. G_{k+1} doesn’t contain cycles of length \leq 5 .

This is a proof by induction on k . Suppose that G_k doesn’t contain cycles of length \leq 5 .

This is an elaborated version of the corresponding claim for G_3 that “it is easy to see”. Since the 1 st level of G_{k+1} is an independent set, and the only edges in the 0th level are disjoint copies of G_k with “paired” vertices, any path that starts and ends in the first level must have length at least three, and it cannot be a triangle. (Start at v in level 1 , go up a level to a vertex v^\prime \in G_k^\prime , go across to w^\prime in the same copy, go down a level to w \neq v .)

Therefore any cycle in G_{k+1} must be of length at least 6 .

Exercise. Choose one depending on your tastes. These are very computational.

  1. Compute the closed form for the function r(k) (which is actually also a function of n ).
  2. For what n is it true that G_3 has a 6 -cycle? What is the appropriate Ramsey theorem?

Mike’s comment. This reminds me of the classic proof that R(3,3) = 6 . The same construction (using pigeonhole on the edges) gives a lazy recursive bound for R(3,3, \ldots, 3) := R_k(3) .

For example, R(3,3,3) \leq 1+ P(R(3,3),3) = 1+P(6,3) = 1+ 3(5)+1 = 17 . Assume this has an edge colouring using red, blue and yellow. Start with any vertex v_0 . It has 16 neighbours, so by the pigeonhole principle, it has 6 edges of the same colour (wlog yellow), on the vertices v_1, \ldots, v_6 . Now none of those vertices can have a yellow edge between them (or we’ll hae a yellow triangle with v_0 . So the induced graph on v_1, \ldots, v_6 contains only red and blue edges. Since R(3,3)=6 , it must have either a red edge or a blue edge.

This gives the bound R_{k+1}(3) \leq 1+ P(R_k(3),k+1) = 1+(R_k(3)-1)(k+1) + 1 = O(kR_k(3)) . The closed form is R_{k+1}(3) \leq O(k!) .

There are many known constructions of graphs with large chromatic number but no small cycles. New constructions are always welcomed by the community. One such corollary is the existence of critical k -chromatic graphs (ones where no matter which vertex you remove the chromatic number will drop).

Corollary. Assume the existence of graphs with arbitrarily large chromatic number and girth. For all n there is a critical k -chromatic graph with at least n vertices.

Proof. Fix n,k \geq 3 . Let G be a graph with \chi(G)=k and no cycles of length \leq n . Any collection V_0 of n vertices induces a forest, so its chromatic number will be \leq 2 .

Now let H be a minimal subgraph of G with chromatic number k . By the above observation, H must have at least n+1 vertices.

Edge-Ramsey for graphs

In Bootcamp 6 we saw an argument for why the class of graphs has the Ramsey property when you colour edges. This proof went through a product embedding theorem and used “the product argument”.

Here we will present an alternate proof using a partite construction. It will rely on the edge-Ramsey property for bipartite graphs which will be proved using the Hales-Jewett theorem (see Bootcamp 6).

Theorem (Bipartite Lemma). The class \mathcal{B} of bipartite graphs has the edge-Ramsey property. That is, for every k \in \mathbb{N} , for every B \in \mathcal{B} , there is a C \in \mathcal{B} such that C \longrightarrow (B)_k^\text{edge} .

Proof. Fix k . Let B \in \mathcal{B} be a bipartite graph with independent sets S and T . Without loss of generality, B has no isolated points.

Let \mathcal{A} = E(B) be the alphabet. Let N = \text{HJ}(\mathcal{A}, k) be the Hales-Jewett number for alphabet \mathcal{A} and k colours.

Let C be the graph whose vertices are all functions f: \{1,2, \ldots, N\} \longrightarrow S and g: \{1,2, \ldots, N\} \longrightarrow T . Put an edge between two vertices f,g iff \{f(i),g(i)\} \in E(B) for all i \leq N .

Fix a k -colouring \chi of E(C) . Every edge in E(C) comes from two functions, say f,g , which in turn give a sequence of N edges in E(B) , i.e. a word in \mathcal{A}^N . Conversely, every word in \mathcal{A}^N corresponds to an edge in E(C) . So \chi gives a k -colouring of \mathcal{A}^N .

Let \mathcal{W}_{w(x)} = \{w(e) : e \in \mathcal{A}=E(B)\} be a monochromatic combinatorial line, where w(x) has variables in coordinates \emptyset \neq M \subseteq \{1, \ldots, N\} . Let F = \{1, \ldots, N\} \setminus M . (M is the “moving part” and F is the “fixed part”.)

For an edge e \in E(B) , let \pi_S(e) = vertex of e in S and \pi_T(e) = vertex of e in T .

Now we construct our B^\prime \cong B , a subgraph of C . For e \in E(B) , the element w(e) \in \mathcal{W}_{w(x)} gives us a function from \{1,2, \ldots, N\} to S (by using \pi_S on each edge) and a function \{1,2, \ldots, N\} to T (by using \pi_T on each edge). This is the vertex set of B^\prime .

Note that B^\prime has edges that precisely correspond to the edges of B . By Hales-Jewett, this is monochromatic. (Exercise. Convince yourself that B^\prime \cong B .)

Andrés’ Observation. This feels similar to the construction in Bootcamp 6 to show that every graph can be embeded into a product of K_n . There we took the collection of all graph homomorphisms.

We are now ready to prove the full version of edge-Ramsey for graphs using a partite construction.

Theorem. The class \mathcal{G} of all graphs has the edge-Ramsey property. That is, for every k \in \mathbb{N} , for every G \in \mathcal{G} , there is a C \in \mathcal{G} such that C \longrightarrow (G)_k^\text{edge} .

Proof using a partite construction. Fix k . Let G=(V,E) and let \vert V \vert = n .

The proof will go by constructing finitely many “pictures” P_0, P_1, \ldots each of which will contain many copies of the previous picture (and P_0 will contain many copies of G ). We will give more intuition after constructing P_0 .

Construction of P_0 . Let R = R(n,k) be the Ramsey number for pairs, for K_n and k colours. (You can think of this as being “large enough” if you want.)

Let P_0 be the disjoint union of the independent sets X_i for i \leq R , where each has \binom{R}{n} vertices (you can think of each as being “wide enough” if you want). We will call these the R levels. For every n -element subset of I \subset R , add a disjoint transversal copy of G in the sets \bigcup_{i \in I} X_i .

We will now make “pictures” P_1, \ldots, P_\binom{R}{2} each of which will stabilize the (future) colour of the edges between two different X_i^0 . Our Ramsey witness will be the final picture. Once all pairs are stabilized, we will use our choice of large enough R to find a monochromatic copy of G . The order in which we stabilize doesn’t matter.

Construction of P_1 . Let B_0 be the induced (bipartite) subgraph of P_0 from X_1 and X_2 . (It looks like a lot of isolated points and possibly one edge.) Use the Bipartite lemma to find a C_1 such that C_1 \longrightarrow (B_0)_k^\text{edge} .

Now (freely) amalgamate copies of P_0 along its B_0 onto every copy of B_0 in C_1 . Call this amalgamation P_1 .

(We can think of the copies of P_0 as sharing common (very wide) i th levels (for each 1\leq i \leq R ). Since these are free amalgamations, distinct copies of P_0 can only share vertices in the first or second level of C_1 .)

Construction of P_{k+1} from P_k . Suppose we have already constructed P_0, P_1, \ldots, P_k . Suppose we wish to stabilize the (future) colour of the edges between level i and j (and haven’t done so already). Let B_k be the induced (bipartite) subgraph of P_k using levels i and j . Use the Bipartite lemma to find a C_{k+1} such that C_{k+1} \longrightarrow (B_k)_k^\text{edge} .

Now (freely) amalgamate copies of P_k along its B_k onto every copy of B_k in C_{k+1} . Call this amalgamation P_{k+1} .

Claim. Let C be the final graph P_\binom{R}{2} . We claim C \longrightarrow (G)_k^\text{edge} .

Proof of claim. Fix an k -colouring \chi of the edges of C . We go in reverse ordering of the construction. (For ease of notation, label the final index N = \binom{R}{2} .

The edge colouring \chi is also an edge colouring of C_N . It has a monochromatic copy B_{N-1}^\prime \cong B_{N-1} . This copy corresponds to a copy of P_{N-1}^\prime \cong P_{N-1} . (So we have stablized the edge colouring on the N th pair of levels of P_{N-1}^\prime . It will remain stabilized as we proceed.)

The edge colouring \chi is also an edge colouring of the copy of C_{N-1} in P_{N-1}^\prime . It has a monochromatic copy B_{N-2}^\prime \cong B_{N-2} . This copy corresponds to a copy of P_{N-2}^\prime \cong P_{N-2} .

Continue on until we have a P_0^\prime \cong P_0 . This one will have all of its pairs of levels stabilized. Thus this induces a colouring \chi_\text{pairs} on the pairs of elements of \{1, \ldots, R\} . By our choice of R (the number of levels of P_0 ), there is a set I \subset \{1, \ldots, R\} , with \vert I \vert = n = \vert V(G) \vert , whose pairs are \chi_\text{pairs} -monochromatic. The copy of G that exists on \bigcup_{i \in I} X_i^\prime will be \chi_\text{pairs} -monochromatic and hence \chi -monochromatic, as desired.

Exercise. In this proof we used the property that n -partite graphs can be freely amalgamated. Show that this is not essential.

Erdos-Hajnal

We first look at a theorem which is not Ramsey on the surface, but which illustrates the partite construction. There will be two notable differences from the previous proof:

  1. We will have a vertex colouring, not an edge colouring.
  2. We will not amalgamate P_k along every copy of B_k in C_{k+1} , instead C_{k+1} will come with a distinguished set of B_k that we will amalgamte along. (In fact, C_{k+1} will be a hypergraph and we will amalgamate a copy of P_k to each hyperedge.)

Theorem (Erdos-Hajnal, 196?): Let 2 \leq n,k,l \in \mathbb{N} . There is a hypergraph (X, \mathcal{M}) such that

  • it is n -uniform,
  • \chi(X, \mathcal{M}) > k ,
  • (X, \mathcal{M}) has girth at least l . That is, it doesn’t contain cycles of length \leq l .

Proof. This will be a proof by induction on l (the girth).

The l=2 case is essentially just K_k (suitably adapted to be a n -uniform hypergraph). So assume l \geq 3 .

We can always deal with k=2 by taking a large tree (suitably adapted to be a n -uniform hypergraph). So assume k \geq 3 .

Induction hypothesis. Assume the theorem for all 2 \leq k,n \in \mathbb{N} and l-1 .

Again, we construct a sequence of finitely many “pictures” P_0, P_1, \ldots each of which will contain many copies of the previous picture (and P_0 will contain many disjoint hyperedges).

Construction of P_0 . Let R = P(p, k) = (p-1)k+1 be the pigeonhole number for n objects and k colours.

Let P_0 be the disjoint union of the independent sets X_i for i \leq R , where each has \binom{R}{n} vertices (you can think of each as being “wide enough” if you want). We will call these the R levels. For every n -element subset of I \subset R , add a disjoint transversal hyperedge across the sets \bigcup_{i \in I} X_i .

The plan. We will now make “pictures” P_1, \ldots, P_R each of which will stabilize the (future) colour of the vertices on level 1 \leq i \leq R . Our desired graph will be the final picture. Once all the levels are stabilized, we will use our choice of large enough R to find a monochromatic hyperedge (assuming we only used k colours). This will show that the chromatic number is > k . We will construct the pictures in such a way that we don’t add cycles of length l .

At each stage j we will need an auxillary hypergraph C_j which will tell us where to amalgamate the previous picture. It can get confusing since we are dealing with hypergraphs and auxillary hypergraphs; we will always use the word “auxillary” when referring to these hypergraphs or their hyperedges. Hopefully this negates some of the confusion.

Construction of P_1 . Let B_1 be the induced subgraph of P_0 from level 1. (It’s just a large independent set.) Let n_1 = \vert B_1 \vert . Use the inductive hypothesis to find an auxillary hypergraph C_1 that is n_1 -uniform, has no cycles of length \leq l-1 , and has chromatic number >k .

Now (freely) amalgamate copies of P_0 along B_1 onto every auxillary hyperedge in C_1 . Call this P_1 . The only hyperedges in P_1 are the ones coming from the various P_0 . The auxillary hyperedges in C_1 are only used to decide where to put copies of P_0 .

(We can think of the copies of P_0 as sharing common (very wide) i th levels (for each 1\leq i \leq R ). Since these are free amalgamations, distinct copies of P_0 can only share vertices in the first level of P_1 .)

Exercise. To help you visualize this hypergraph. Show that P_1 doesn’t have any paths of length 3 . Show that P_1 doesn’t have any cycles.

This is a very special situation. For later pictures we will add long paths and long cycles.

Construction of P_{j+1} from P_j . Suppose we have already constructed P_0, P_1, \ldots, P_j . We wish to stabilize the (future) colour of level j . Let B_j be the induced (independent) subgraph of P_j using levels j . Let n_j = \vert B_j \vert . Use the inductive hypothesis to find an auxillary hypergraph C_j that is n_j -uniform, has no cycles of length \leq l-1 , and has chromatic number >k .

Now (freely) amalgamate copies of P_j along B_j onto every auxillary hyperedge in C_j . Call this P_{j+1} . Again, the only hyperedges in P_{j+1} come from its copies of P_j ; the auxillary hypergraph C_j is only used to tell us where to amalgamate.

Claim 1. Let C be the final hypergraph P_R . We claim \chi(C)>k .

Proof of claim 1. Fix an k -colouring \rho of the vertices of C . We go in reverse ordering of the construction.

The vertex colouring \rho is also a vertex colouring of C_{R-1} . It has a monochromatic (auxillary) hyperedge, since \chi(C_{R-1})>k . This monochromatic (auxillary) hyperedge corresponds to a copy of P_{R-1} (whose R th level is monochromatic).

The vertex colouring \rho is also a vertex colouring of the copy of C_{R-2} in P_{R-1} . It has a monochromatic (auxillary) hyperedge, since \chi(C_{R-2})>k . This monochromatic (auxillary) hyperedge corresponds to a copy of P_{R-2} (whose R-1 st level is monochromatic).

Continue on until we have stabilized all the level 1 \leq j \leq R . Thus this induces a k -colouring \rho_\text{levels} on the levels \{1, \ldots, R\} . By our choice of R , there is a set I \subset \{1, \ldots, R\} , with \vert I \vert = n , whose vertices are all \rho_\text{levels} -monochromatic. The hyperedge that exists on the levels given by I will be \rho_\text{levels} -monochromatic and hence \rho -monochromatic, as desired.

So \chi(C)>k .

Claim 2. C does not have any cycles of length \leq l .

Proof of claim 2. This proof is by (direct) induction on the pictures P_0, P_1, \ldots, P_j, \ldots, P_R . Recall that we assumed the auxillary hypergraphs C_j had no cycles of length \leq l-1 , and we assumed 2 \leq l .

Case: j=0 . Clearly P_0 has no cycles as all its hyperedges are disjoint.

Case: j=1 . The case of P_1 was an exercise above, but to expand: two hyperedges can only intersect in an auxillary hyperedge from C_1 . More specifically, this can only happen on the intersection of two auxillary hyperedges A_1, A_2 \in E(C_1) . Such an intersection has only one point, since C_1 doesn’t have any 2 cycles. With this, and since (at this stage) two hyperedges can only intersect on level 1 , we can only have paths of length at most 2 . In particular we cannot have any cycles.

Case: j to j+1 . Suppose we know that P_j does not have any cycles of length \leq l . We’ll show the same for P_{j+1} .

The idea here is to look at the projection \pi of the hyperedges E \in E(P_{j+1}) into the auxillary hyperedges of C_j . This projection \pi(E) returns all auxillary hyperedges in C_j that E intersects (there may be many).

Let E_1, \ldots, E_N be a cycle of hyperedges in P_{j+1} . Two hyperedges intersect because either (1) they are coming from a common copy of P_j , or (2) they come from the intersection of two auxillary hyperedges (at a single point on level j+1 ).

By the inductive hypothesis, if the entire cycle comes from a common copy of P_j then the cycle must have length N > l .

If the cycle uses many different copies of P_j , then it must use at least l auxillary hyperedges to “wrap around” and form a cycle. A little staring will convince you that we will need at least twice as many hyperedges as auxillary hyperedges to form such a cycle (i.e. N \geq 2l > l ).

Unlike in the case of Tutte’s construction, there is no cheating and “doubling back” to make a 6 -cycle. This is prevented by the fact that auxillary hyperedges intersect in at most one point. If you do “double back” through the same intersection point, then you will form a smaller cycle (which is forbidden).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s