# Accessible Applications of Graph Ramsey Theory

I am giving a short lecture series on graph Ramsey theory to a group of gifted high school seniors. The brief outline is to start with the "six people at a dinner party" question, transition into the proof that $R(m,n)$ exists in general, and establish rough lower and upper bounds (by the probabilistic method and recursion, respectively).

I would like to end with a few applications of this seemingly esoteric theory. The statement should be relatively easy to apprehend. The proof need not be simple, but the role of graph Ramsey theory should at least be evident.

Two examples spring to my mind. Schur's theorem states that any finite-coloring of the integers has a color class in which $x + y = z$. The Ramsey theoretic proof simply requires coloring an appropriate graph and finding a monochromatic triangle. Another is the general Happy Ending problem, which asserts that a sufficiently large collection of points in general position admits a convex polygon of any fixed size. I need to brush up on it myself, but the proof I seem to recall requires coloring triples of points, which may already be stretching the imagination a bit.

• The standard reference for applications is combinatorics.org/ojs/index.php/eljc/article/view/DS13/pdf, Ramsey Theory Applications, by Vera Rosta, in the Electronic Journal of Combinatorics, Dynamic Survey, DS13: Dec 7, 2004. As you may imagine, many of these applications are not elementary, but they give you an idea of the reach of the theory. Commented Jun 3, 2013 at 22:43
• An application I particularly find interesting is in finding lower bounds for the running time of the resolution method in propositional logic. It is a co-NP complete problem to decide whether a given formula is a tautology. The paper The complexity of proving that a graph is Ramsey, by Massimo Lauria, Pavel Pudlák, Vojtěch Rödl, and Neil Thapen, arxiv.org/abs/1303.3166 shows that the resolution method requires an exponential amount of time in general, by showing that this happens in particular for formulas stating certain graphs are Ramsey. Commented Jun 3, 2013 at 22:48
• I just asked a practical question that, as I found out later, is related to Ramsey theory: cs.stackexchange.com/questions/12275/… Commented Jun 6, 2013 at 9:19
• @ErelSegalHalevi Nice! This reminds me of the Sandor Szalai story told here. Commented Jun 6, 2013 at 15:58

Although many years later, here is another nice application of Ramsey theory to Games and Equilibrium in economics (by Eran Shmaya, Eilon Solan and Nicolas Vieille, from 2003). They use Ramsey theory to prove that prove that every two-player nonzero-sum deterministic stopping game with uniformly bounded payoffs admits an $$\epsilon$$-equilibrium, for every $$\epsilon > 0$$. It appeared in the journal Games and Economic Behavior. (I am giving a lecture on KPT tomorrow, and I know there is one person in the audience who is really doing economics; I decided to do a search for connections...)