1
$\begingroup$

I'm trying to find the smallest $n_c$ for which the problem of proving a complete graph with $n$ vertices with edges colored with $c$ colors has a monochromatic triangle could be simplified to a problem of proving the same for a smaller graph of $m_{c-1} < n$ vertices and $c-1$ colors using the Pigeonhole principle. $n$ should be a function of $c$.

This is similar to how the problem of proving that in a graph with 17 vertices where the edges are colored with 3 colors we could find a triangle can be simplified to proving that in a complete graph with 6 vertices and 2 colors there is a monochromatic triangle. Appreciate any help you could provide!

$\endgroup$
2
  • $\begingroup$ Using such methods stops giving tight bounds quickly. This is confirmed by the partial results on various Ramsey numbers. $\endgroup$
    – Zach Hunter
    Jan 6, 2019 at 19:22
  • $\begingroup$ my answer at: math.stackexchange.com/questions/935143/… shows all $K_6$ actually have 2 monchromatic triangles in 2 colors, only 3 colorings of higher $K_n$ that force both to break, need be considered. $\endgroup$
    – user645636
    Mar 7, 2019 at 19:45

0

Reset to default

You must log in to answer this question.