ramsey theory


Geometric Hales-Jewett Theorem ★★

Author(s): Por; Wood

\begin{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: \begin{itemize} \item $P$ contains $\ell$ collinear points, or \item $P$ contains a monochromatic line (that is, a maximal set of collinear points receiving the same colour) \end{itemize} \end{conjecture}

Keywords: Hales-Jewett Theorem; ramsey theory

Exact colorings of graphs ★★

Author(s): Erickson

\begin{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$. \end{conjecture}

Keywords: graph coloring; ramsey theory

Monochromatic empty triangles ★★★

Author(s):

If $X \subseteq {\mathbb R}^2$ is a finite set of points which is 2-colored, an \emph{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 \emph{monochromatic} if all points in $T$ are the same color.

\begin{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. \end{conjecture}

Keywords: empty triangle; general position; ramsey theory

Erdös-Szekeres conjecture ★★★

Author(s): Erdos; Szekeres

\begin{conjecture} Every set of $2^{n-2} + 1$ points in the plane in general position contains a subset of $n$ points which form a convex $n$-gon. \end{conjecture}

Keywords: combinatorial geometry; Convex Polygons; ramsey theory

Syndicate content