4
$\begingroup$

I am trying to understand the proof of Theorem 2 given here. (Page 5) The theorem states that $\forall k\exists$ a triangle free graph $G$ with $\chi(G)>k$. The proof constructs such a $G$ as $G=A_kA_{k-1}\cdots A_0(G_0)$, where $A_0(G_0)$ is defined as the amalgamation of the graph $G_0$(which is a previously constructed triangle free $(k+1)$-partite graph having partite sets $V_0,\cdots V_k$, with the property that if it is $k$-colored with each partite set monochromatic then there is a monochromatic edge) on $V_0$.

What is not clear to me is why $G$ will contain a copy of $G_0$ with each class monochromatic. By a previous proposition $A_0(G_0)$ contains a copy of $G_0$ with $V_0$ monochromatic, say red. Now $A_1A_0(G_0)$ contains a copy of $A_0(G_0)$ with its second partite set monochromatic say blue. This does not mean that $V_1$ of $G_0$ is blue.

I would be grateful if someone could resolve my confusion. Thanks for reading through this post.

  • 0
    Yes, I have seen that proof. I am however interested in the above proof for another reason: The same technique is used in constructing a graph not containing a $K_4$ which always contain a monochromatic $K_3$ when the edges are $2$-colored.2012-12-06

1 Answers 1

2

It seems that it should be possible to employ Proposition 1 inductively to prove the desired result. Take the case of $A_1(A_0(G_0))$.

Let $G_0$ be the $(k + 1)$-partite graph with parts $V_0$, $V_1$, $\ldots\,$, $V_k$ such that if $G_0$ is $k$-colored with each $V_i$ monochromatic then there exists an edge in $G_0$ whose endpoints have the same color.

It's important to note that if $G_0$ is $(k + 1)$-partite, then the amalgamation $A_i(G_0)$ is also $(k + 1)$-partite. This is not made explicit in the notes linked to above (see my and Brian M. Scott's comments below).

The amalgamation method was introduced by Nesetril and Rödl. I believe that this paper is where it first appeared. The definition of the amalgamation of a graph $G$ over another graph $H$ that is given in the "Preliminaries" section of that paper makes clear that if $G$ is $(k + 1)$-partite, then the amalgamation is also $(k + 1)$-partite.

Proof: Color $A_1(A_0(G_0))$ with $k$ colors. By Proposition 1, there exists a set $B \subseteq W_1$ (where $B$ has the same size as the first class of $A_0(G_0)$) such that $(A_0(G_0))_B$ has monochromatic 1st class. Now restrict the $k$-coloring to $(A_0(G_0))_B$. The key observation is that every copy of $G_0$ in $(A_0(G_0))_B$ has its 1st class $V_1$ monochromatic. Now, by applying Proposition 1 to $(A_0(G_0))_B$, there exists a copy of $G_0$ that also has monochromatic 0th class $V_0$.

One can apply the same reasoning inductively to $A_k(A_{k-1}( \cdots A_0(G_0)\cdots ))$ to find a copy of $G_0$ with each class monochromatic. By definition of $G_0$, there must be a monochromatic edge.

  • 0
    @Shahab It seems that if $G$ is $r$-partite, then the amalgamation should indeed also be $r$-partite--see my updated answer for details.2012-12-07