Recent Activity

Theoretical Comp. Sci. » Complexity » Derandomization

Unconditional derandomization of Arthur-Merlin games ★★★

Author(s): Shaltiel; Umans

Problem Prove unconditionally that $\mathcal{AM}$ $\subseteq$ $\Sigma_2$ .

Keywords: Arthur-Merlin; Hitting Sets; unconditional

Posted by ormeir
updated July 16th, 2007

add new comment

Theoretical Comp. Sci. » Complexity

Subset-sums equality (pigeonhole version) ★★★

Author(s):

Problem Let $a_1,a_2,\ldots,a_n$ be natural numbers with $\sum_{i=1}^n a_i < 2^n - 1$ . It follows from the pigeon-hole principle that there exist distinct subsets $I,J \subseteq \{1,\ldots,n\}$ with $\sum_{i \in I} a_i = \sum_{j \in J} a_j$ . Is it possible to find such a pair $I,J$ in polynomial time?

Keywords: polynomial algorithm; search problem

Posted by mdevos
updated July 16th, 2007

10 comments

Graph Theory » Coloring » Homomorphisms

Weak pentagon problem ★★

Author(s): Samal

Conjecture If $G$ is a cubic graph not containing a triangle, then it is possible to color the edges of $G$ by five colors, so that the complement of every color class is a bipartite graph.

Keywords: Clebsch graph; cut-continuous mapping; edge-coloring; homomorphism; pentagon

Posted by Robert Samal
updated July 13th, 2007

add new comment

Number Theory

Lonely runner conjecture ★★★

Author(s): Cusick; Wills

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

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

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.

Keywords: coloring; surface; tension

Posted by mdevos
updated June 22nd, 2007

add new comment

Combinatorics » Ramsey Theory

Concavity of van der Waerden numbers ★★

Author(s): Landman

For $k$ and $\ell$ positive integers, the (mixed) van der Waerden number $w(k,\ell)$ is the least positive integer $n$ such that every (red-blue)-coloring of $[1,n]$ admits either a $k$ -term red arithmetic progression or an $\ell$ -term blue arithmetic progression.

Conjecture For all $k$ and $\ell$ with $k \geq \ell$ , $w(k,\ell) \geq w(k+1,\ell-1)$ .

Keywords: arithmetic progression; van der Waerden

Posted by Bruce Landman
updated June 21st, 2007

add new comment

Graph Theory » Coloring » Vertex coloring

Circular coloring triangle-free subcubic planar graphs ★★

Author(s): Ghebleh; Zhu

Problem Does every triangle-free planar graph of maximum degree three have circular chromatic number at most $\frac{20}{7}$ ?

Keywords: circular coloring; planar graph; triangle free

Posted by mdevos
updated June 20th, 2007

add new comment

Graph Theory » Coloring » Edge coloring

List colorings of edge-critical graphs ★★

Author(s): Mohar

Conjecture Suppose that $G$ is a $\Delta$ -edge-critical graph. Suppose that for each edge $e$ of $G$ , there is a list $L(e)$ of $\Delta$ colors. Then $G$ is $L$ -edge-colorable unless all lists are equal to each other.

Keywords: edge-coloring; list coloring

Posted by Robert Samal
updated June 12th, 2007

add new comment

Combinatorics » Matroid Theory

Aharoni-Berger conjecture ★★★

Author(s): Aharoni; Berger

Conjecture If $M_1,\ldots,M_k$ are matroids on $E$ and $\sum_{i=1}^k rk_{M_i}(X_i) \ge \ell (k-1)$ for every partition $\{X_1,\ldots,X_k\}$ of $E$ , then there exists $X \subseteq E$ with $|X| = \ell$ which is independent in every $M_i$ .

Keywords: independent set; matroid; partition

Posted by mdevos
updated June 11th, 2007

add new comment

Combinatorics » Ramsey Theory

The large sets conjecture ★★★

Author(s): Brown; Graham; Landman

Conjecture If $A$ is 2-large, then $A$ is large.

Keywords: 2-large sets; large sets

Posted by vjungic
updated June 10th, 2007

add new comment

Graph Theory » Algebraic G.T.

Ramsey properties of Cayley graphs ★★★

Author(s): Alon

Conjecture There exists a fixed constant $c$ so that every abelian group $G$ has a subset $S \subseteq G$ with $-S = S$ so that the Cayley graph ${\mathit Cayley}(G,S)$ has no clique or independent set of size $> c \log |G|$ .

Keywords: Cayley graph; Ramsey number

Posted by mdevos
updated June 10th, 2007

add new comment

Combinatorics » Matroid Theory

Bases of many weights ★★★

Author(s): Schrijver; Seymour

Let $G$ be an (additive) abelian group, and for every $S \subseteq G$ let ${\mathit stab}(S) = \{ g \in G : g + S = S \}$ .

Conjecture Let $M$ be a matroid on $E$ , let $w : E \rightarrow G$ be a map, put $S = \{ \sum_{b \in B} w(b) : B \mbox{ is a base} \}$ and $H = {\mathit stab}(S)$ . Then $|S| \ge |H| \left( 1 - rk(M) + \sum_{Q \in G/H} rk(w^{-1}(Q)) \right).$

Keywords: matroid; sumset; zero sum

Posted by mdevos
updated June 10th, 2007

add new comment

Number Theory » Additive N.T.

The Erdos-Turan conjecture on additive bases ★★★★

Author(s): Erdos; Turan

Let $B \subseteq {\mathbb N}$ . The representation function $r_B : {\mathbb N} \rightarrow {\mathbb N}$ for $B$ is given by the rule $r_B(k) = \#\{ (i,j) \in B \times B : i + j = k \}$ . We call $B$ an additive basis if $r_B$ is never $0$ .

Conjecture If $B$ is an additive basis, then $r_B$ is unbounded.

Keywords: additive basis; representation function

Posted by mdevos
updated June 8th, 2007

add new comment

Combinatorics » Matroid Theory

Rota's unimodal conjecture ★★★

Author(s): Rota

Let $M$ be a matroid of rank $r$ , and for $0 \le i \le r$ let $w_i$ be the number of closed sets of rank $i$ .

Conjecture $w_0,w_1,\ldots,w_r$ is unimodal.

Conjecture $w_0,w_1,\ldots,w_r$ is log-concave.

Keywords: flat; log-concave; matroid

Posted by mdevos
updated June 8th, 2007

add new comment

Geometry

A conjecture on iterated circumcentres ★★

Author(s): Goddyn

Conjecture Let $p_1,p_2,p_3,\ldots$ be a sequence of points in ${\mathbb R}^d$ with the property that for every $i \ge d+2$ , the points $p_{i-1}, p_{i-2}, \ldots p_{i-d-1}$ are distinct, lie on a unique sphere, and further, $p_i$ is the center of this sphere. If this sequence is periodic, must its period be $2d+4$ ?

Keywords: periodic; plane geometry; sequence

Posted by mdevos
updated June 8th, 2007

add new comment

Graph Theory » Infinite Graphs

Unions of triangle free graphs ★★★

Author(s): Erdos; Hajnal

Problem Does there exist a graph with no subgraph isomorphic to $K_4$ which cannot be expressed as a union of $\aleph_0$ triangle free graphs?

Keywords: forbidden subgraph; infinite graph; triangle free

Posted by mdevos
updated June 4th, 2007

add new comment

Graph Theory » Directed Graphs

The Two Color Conjecture ★★

Author(s): Neumann-Lara

Conjecture If $G$ is an orientation of a simple planar graph, then there is a partition of $V(G)$ into $\{X_1,X_2\}$ so that the graph induced by $X_i$ is acyclic for $i=1,2$ .

Keywords: acyclic; digraph; planar

Posted by mdevos
updated May 31st, 2007

1 comment

Graph Theory » Algebraic G.T.

Half-integral flow polynomial values ★★

Author(s): Mohar

Let $\Phi(G,x)$ be the flow polynomial of a graph $G$ . So for every positive integer $k$ , the value $\Phi(G,k)$ equals the number of nowhere-zero $k$ -flows in $G$ .

Conjecture $\Phi(G,5.5) > 0$ for every 2-edge-connected graph $G$ .

Keywords: nowhere-zero flow

Posted by mohar
updated May 31st, 2007

add new comment

Number Theory » Combinatorial N.T.

Gao's theorem for nonabelian groups ★★

Author(s): DeVos

For every finite multiplicative group $G$ , let $s(G)$ ( $s'(G)$ ) denote the smallest integer $m$ so that every sequence of $m$ elements of $G$ has a subsequence of length $>0$ (length $|G|$ ) which has product equal to 1 in some order.