Open Problem Garden

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.

Keywords: empty triangle; general position; ramsey theory

Posted by mdevos
updated August 27th, 2010

4 comments

ramsey theory

Geometry

Erdös-Szekeres conjecture ★★★

Author(s): Erdos; Szekeres

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.

Keywords: combinatorial geometry; Convex Polygons; ramsey theory

Posted by mdevos
updated April 14th, 2009

1 comment

combinatorial geometry

Logic

Termination of the sixth Goodstein Sequence ★

Author(s): Graham

Question How many steps does it take the sixth Goodstein sequence to terminate?

Keywords: Goodstein Sequence

Posted by mdevos
updated September 17th, 2010

5 comments

Goodstein Sequence

Combinatorics » Ramsey Theory

Edge-antipodal colorings of cubes ★★

Author(s): Norine

We let $Q_d$ denote the $d$ -dimensional cube graph. A map $\phi : E(Q_d) \rightarrow \{0,1\}$ is called edge-antipodal if $\phi(e) \neq \phi(e')$ whenever $e,e'$ are antipodal edges.

Conjecture If $d \ge 2$ and $\phi : E(Q_d) \rightarrow \{0,1\}$ is edge-antipodal, then there exist a pair of antipodal vertices $v,v' \in V(Q_d)$ which are joined by a monochromatic path.