Open Problem Garden

Conjecture Suppose $k$ runners having distinct constant speeds start at a common point and run laps on a circular track with circumference 1. Then for any given runner, there is a time at which that runner is distance at least $\frac{1}{k}$ (along the track) away from every other runner.

Keywords: diophantine approximation; view obstruction

Posted by mdevos
updated June 24th, 2007

add new comment

Number Theory » Combinatorial N.T.

Sets with distinct subset sums ★★★

Author(s): Erdos

Say that a set $S \subseteq {\mathbb Z}$ has distinct subset sums if distinct subsets of $S$ have distinct sums.

Conjecture There exists a fixed constant $c$ so that $|S| \le \log_2(n) + c$ whenever $S \subseteq \{1,2,\ldots,n\}$ has distinct subset sums.

Keywords: subset sum

Posted by mdevos
updated April 7th, 2011

1 comment

subset sum

Graph Theory » Coloring » Homomorphisms

Mapping planar graphs to odd cycles ★★★

Author(s): Jaeger

Conjecture Every planar graph of girth $\ge 4k$ has a homomorphism to $C_{2k+1}$ .

Keywords: girth; homomorphism; planar graph

Posted by mdevos
updated June 24th, 2007

add new comment

girth

Graph Theory » Topological G.T. » Coloring

5-local-tensions ★★

Author(s): DeVos

Conjecture There exists a fixed constant $c$ (probably $c=4$ suffices) so that every embedded (loopless) graph with edge-width $\ge c$ has a 5-local-tension.