This is a collection of papers that APPLY Ramsey Theory TO TCS. I define ‘Ramsey Theory’

to be any theorem that (roughly) says that if some structure is big enough, order emerges.

Survey's

Some Nonstandard Ramsey Like Applications by Nesetril

Applications of Ramsey Theory by Roberts

Ramsey Theory Applications by Vera Rosta

Boolean Complexity and Ramsey Theorems by Pudlak

Applications to Logic

On a problem in Formal Logic by Ramsey

Bounds for Hodes-Specker Theorem by Pudlak

A Proof of Beigel's Cardinality Conjecture by Kummer

Generalized Quantifiers and Pebble Games on Finite Structures by Kolaitis and Vaananen

XML with data values: typechecking revisited by Alon, Milo, Neven, Suciu, Vianu

An Existential Fragment of Second Order Logic by Rosen

The Complexity of Temporal Constraint Satisfaction Problems by Manuel Bodirsky

Ramsey Theory Is Needed for Solving Definability Probs of Gen Quantifiers by Luosto

Proving Program Termination} by Cook, Podelski, Rybachenko

Proving programs terminate using well-orerings, Ramsey Theory, and Matrices by Gasarch

The dynamic description complexity of k-clique by Thomas Zeume

Applications to Concrete Complexity

Should Tables be Sorted by Yao

Two Lower Bounds for Branching Programs by ABHKP

Multi-Party Protocols by Chandra, Furst, Lipton Exposition by Gasarch

Improvment to CFL paper by Linial and Shraibman

Applications of Ramsey's Theorem to Decision Tree Complexity by Moran,Snir,Manber

Decision trees and downward closure by Imagliazzo and Naor

Meanders and their applications in Lower Bound arguments by Alon and Maass

Lower Bounds to the Complexity of Symme Boolean Functions by Babai, Pudlak, Rodl, Szemeredi

Subquadratic Simulations of Balanced Formulae by Branching Programs by Cai and Lipton

Repeated Communication and Ramsey Graphs by Alon and Orlitsky

Superlinear lower bounds for bounded-width branching programs

Lower Bounds for Approx. by Low Degree Polynomials over Zm by Alon and Beigel

An Application of Hindman's Theorem to a Problem in Communication Complexity by Pudlak

A note on the Multiparty Communication Complexity and the Hales-Jewitt Theorem by Shraibman

A limit to the power of multiple nucleation in self-assembly by Aaron Sterling

Applications to Complexity Classes

The Node-Deletion Problem for Hereditary Properties is NP-Complete by J.Lewis and M.Yannakakis

On Proving that a Graph Has No Large Clique: A Connection with Ramsey Theory by Lipton

Sperner's Lemma nad Robust Machines by Crecenzi and Silvestri

Time Bounded Frequency Computations by Hinrichs and Wechsung

Parameterized Complexity of Finding Subgraphs with Hereditary Properties by Khot and Raman

Testing of large graphs by Alon, Fischer, Krivelevich, Szegedy

Testing of Matrix Properties by Fischer, Newman

On the Strength of Comparisons in Property Testing by Fischer

Counting Quantifiers by Straubing

Simple Analysis of Graph Tests for Linearity and PCP by Hastad and Wigderson

Satisfiability Allows No Nontrivial Sparsification Unless the Polynomial-Time Hierarchy Collapses by Holger Dell and Dieter van Melkebeek

Applications to Parallelism

On Parallel Searching by Snir

One, Two, Three, … infinity: Lower Bounds for Parallel Computation by Fich, Der Heide, Wigderson

Lower Bounds for Parallel Random-Access Machines by Fich, Der Heide, Radge, Wigderson

The Complexity of Parallel Sorting by Der Heide ad Wigderson

The Parallel Complexity of Element Distinction by Ragde, Steiger, Szemeredi, and Wigderson

Optimal Separations Between Concurrent-Write Parallel Machines by Boppana

What can be Computed Locally? by Naor and Stockmeyer

Transforming Comparison Model Lower Bounds to the PRAM by Breslauer, Czumaj, Dubhashi, Meyer auf de Heide

Schafer's theorem for graphs by Bodirsky and Pinsker

Applications to Algorithms and Misc

Matrix Multiplication via Arithmetic Progressions by Coppersmith and Winograd

Ramsey Numbers and an Approx. Algorithm for the Vertex Cover Problem by Monien and Speckenmeyer

Approx. Maximum Indepedent Sets by Excluding Subgraphs by Boppana and Halldorsson

A Ramsey-type Theorem for Metric Spaces and its Applications for Metrical Task Systems and Related Problems by Bartal, Bollobas, Mendel

On the Diagonal Queens Domination Problem by Cockayne and Hedetniemi

Finding, Minimizing, and Counting Weighted Subgraphs by Virginia Vassilevska and Ryan Williams

Applications to Computational Geometry

A Visibility Representation for Graphs in Three Dimensions by Bose, Everett, Fekete, Houle, Lubiw,Meijer, Romanik, Rote, Shermer, Whitesides

Universal 3-Dimensional Visibility Representation for Graphs by Alt, Godau, Whitesides