ramsey theory

Multicolour Erdős--Hajnal Conjecture ★★★

Conjecture For every fixed $k\geq2$ and fixed colouring $\chi$ of $E(K_k)$ with $m$ colours, there exists $\varepsilon>0$ such that every colouring of the edges of $K_n$ contains either $k$ vertices whose edges are coloured according to $\chi$ or $n^\varepsilon$ vertices whose edges are coloured with at most $m-1$ colours.

Keywords: ramsey theory

Posted by Jon Noel
updated October 10th, 2019

add new comment

Geometry

Geometric Hales-Jewett Theorem ★★

Author(s): Por; Wood

Conjecture For all integers $k\geq1$ and $\ell\geq3$ , there is an integer $f(k,\ell)$ such that for every set $P$ of at least $f(k,\ell)$ points in the plane, if each point in $P$ is assigned one of $k$ colours, then:

$P$

$\ell$

$P$

Keywords: Hales-Jewett Theorem; ramsey theory

Posted by David Wood
updated March 26th, 2014

add new comment

Graph Theory

Exact colorings of graphs ★★

Author(s): Erickson

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

Keywords: graph coloring; ramsey theory

Posted by Martin Erickson
updated June 29th, 2010

add new comment

Geometry

Monochromatic empty triangles ★★★

Author(s):

If $X \subseteq {\mathbb R}^2$ is a finite set of points which is 2-colored, an empty triangle is a set $T \subseteq X$ with $|T|=3$ so that the convex hull of $T$ is disjoint from $X \setminus T$ . We say that $T$ is monochromatic if all points in $T$ are the same color.

Conjecture There exists a fixed constant $c$ with the following property. If $X \subseteq {\mathbb R}^2$ is a set of $n$ points in general position which is 2-colored, then it has $\ge cn^2$ monochromatic empty triangles.