ramsey theory

Multicolour Erdős--Hajnal Conjecture ★★★

Author(s): Erdos; Hajnal

Conjecture   For every fixed and fixed colouring of with colours, there exists such that every colouring of the edges of contains either vertices whose edges are coloured according to or vertices whose edges are coloured with at most colours.

Keywords: ramsey theory

Geometric Hales-Jewett Theorem ★★

Author(s): Por; Wood

Conjecture   For all integers and , there is an integer such that for every set of at least points in the plane, if each point in is assigned one of colours, then:
\item contains collinear points, or \item contains a monochromatic line (that is, a maximal set of collinear points receiving the same colour)

Keywords: Hales-Jewett Theorem; ramsey theory

Exact colorings of graphs ★★

Author(s): Erickson

Conjecture   For , let be the statement that given any exact -coloring of the edges of a complete countably infinite graph (that is, a coloring with colors all of which must be used at least once), there exists an exactly -colored countably infinite complete subgraph. Then is true if and only if , , or .

Keywords: graph coloring; ramsey theory

Monochromatic empty triangles ★★★

Author(s):

If is a finite set of points which is 2-colored, an empty triangle is a set with so that the convex hull of is disjoint from . We say that is monochromatic if all points in are the same color.

Conjecture   There exists a fixed constant with the following property. If is a set of points in general position which is 2-colored, then it has monochromatic empty triangles.

Keywords: empty triangle; general position; ramsey theory

Erdös-Szekeres conjecture ★★★

Author(s): Erdos; Szekeres

Conjecture   Every set of points in the plane in general position contains a subset of points which form a convex -gon.