Open Problem Garden

Big Line or Big Clique in Planar Point Sets ★★

Let $S$ be a set of points in the plane. Two points $v$ and $w$ in $S$ are visible with respect to $S$ if the line segment between $v$ and $w$ contains no other point in $S$ .

Conjecture For all integers $k,\ell\geq2$ there is an integer $n$ such that every set of at least $n$ points in the plane contains at least $\ell$ collinear points or $k$ pairwise visible points.

Keywords: Discrete Geometry; Geometric Ramsey Theory

Posted by David Wood
updated September 25th, 2012

1 comment

Pebbling a cartesian product ★★★

Author(s): Graham

We let $p(G)$ denote the pebbling number of a graph $G$ .

Conjecture $p(G_1 \Box G_2) \le p(G_1) p(G_2)$ .

Keywords: pebbling; zero sum

Posted by mdevos
updated September 24th, 2007

add new comment

Problem Two players start at a distance of 2 on an (undirected) line (so, neither player knows the direction of the other) and both move at a maximum speed of 1. What is the infimum expected meeting time $R$ (first time when the players occupy the same point) which can be achieved assuming the two players must adopt the same strategy?