Partite constructions 2 – Ramsey DocCourse Prague 2016 – Mike Pawliuk

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.

Compute the closed form for the function $r(k)$ (which is actually also a function of $n$ ).
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:

We will have a vertex colouring, not an edge colouring.
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.

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

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

Introduction

Tutte’s construction

Edge-Ramsey for graphs

Erdos-Hajnal

Share this:

Related

Leave a comment Cancel reply