9
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Andrés E. Caicedo
    Commented Jun 3, 2013 at 22:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – Andrés E. Caicedo
    Commented Jun 3, 2013 at 22:48
  • 2
    $\begingroup$ I just asked a practical question that, as I found out later, is related to Ramsey theory: cs.stackexchange.com/questions/12275/… $\endgroup$
    – Erel Segal-Halevi
    Commented Jun 6, 2013 at 9:19
  • 1
    $\begingroup$ @ErelSegalHalevi Nice! This reminds me of the Sandor Szalai story told here. $\endgroup$
    – Andrés E. Caicedo
    Commented Jun 6, 2013 at 15:58

2 Answers 2

Reset to default
5
+50
$\begingroup$

If you’re willing to mention the infinite Ramsey theorem, you can use it to give a very slick proof that every infinite sequence of (distinct) real numbers has an infinite (strictly) monotonic subsequence. (Or you could state and prove the finite version of this, but it’s less interesting.)

$\endgroup$
0
$\begingroup$

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

Here is the link:

http://www.math.tau.ac.il/~eilons/ramsey7.pdf

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .