Homework 8

1. Let \(R_n(3)\) denotes the minimal number of vertices of a complete graph, such that any coloring of its edges in \(n\) colors has a monochromatic triangle (recall, that from the class we know that \(R_2(3)=6\), and from the tutorial we know that \(R_3(3) \leq 17\)). Prove the following bound: \(R_n(3) \leq n(R_{n-1}-1) + 2\). Hint: use the Pigeonhole principle.

   Solution

   Set \(N = n(R_{n-1}-1) + 2\). Consider a graph with \(N\) vertices.

   Fix one vertex \(A\). Then there are \(N-1 = n(R_{n-1}-1) + 1\) vertices.

   Then at least \(R_{n-1}\) edges of same color (called color 1) outgoing \(A\). Denote those vertices: \(A_1, A_2, \dots, A_{R_{n-1}}\).

   Then consider the complete graph of \(A_1, \dots, A_{R_{n-1}}\).

   If there exists one of edges in this graph is color 1, for example: \(A_2, A_3\), then we have a color 1 triangle \(AA_2A_3\), which is a 3-clique.

   If there isn't any edge in this graph is color 1, the vertices \(A_1, \dots, A_{R_{n-1}}\) can form a monochromatic triangle with color 2, ..., color \(n-1\).

   Thus such \(N\) can ensure we will find the graph of \(R_n(3)\).

   Thus \(R_n(3) \leq n(R_{n-1}-1) + 2\).

2. Let \(n \in N\). Consider all possible equivalence relations with exactly \(n\) equivalence classes on the set
   ​\(\{1, \dots, R_n(3) - 1\}.\)
   Show that there is at least one equivalence class \(I\) that has elements \(x, y \in I\) such that \(x + y\) is also an element of \(I\) (here it is possible that \(x = y\)).
   Hint: assign a color to each equivalence class. Color an edge between elements \(a, b \in \{1, \dots, R_n(3)\}\) according to the equivalence class of \(|a - b|\).

   Proof

   We assign \(C_1, \dots, C_n\) (color) to each equivalence class.
   Two elements a, b have relation iff they are colored by same color, iff \(|a-b| \in I\).

   Note that \(|a-b| \in \{1, \dots, R_n(3)-1\}\).
   Note the elements belong to \(\{1, \dots, R_n(3)\}\). Then we have \(R_n(3)\) vertices.
   By theorem we can find a monochromatic graph and there exists a color \(C_{m}\), such that has a 3-clique.
   Thus let's call the vertices be \(i, j, k\) and \(i<j<k\).
   We know \(j-i, k-i, k-j \in I\). Note that \((j-i)+(k-j) = k-i \in I\).
   Thus this equivalence relation satisfied.

3. Color the edges of the complete graph \(K_5\) in two colors. Show that for any possible coloring, there is a monochromatic path consisting of 4 vertices and 3 edges. Hint: use the Pigeonhole principle.

   Proof

   Let's take any vertex. By pigeonhole principle. \(\exists\) vertex \(v\) such that at least 3 edges outgoing V with same color
   or every vertex has exactly 2 edges outgoing V with same color.
   Let's the vertices of \(K_{5}\) be \(\{v,a,b,c,d\}\) in order.

   ​