Open Problem Garden

The stubborn list partition problem ★★

Author(s): Cameron; Eschen; Hoang; Sritharan

Problem Does there exist a polynomial time algorithm which takes as input a graph $G$ and for every vertex $v \in V(G)$ a subset $\ell(v)$ of $\{1,2,3,4\}$ , and decides if there exists a partition of $V(G)$ into $\{A_1,A_2,A_3,A_4\}$ so that $v \in A_i$ only if $i \in \ell(v)$ and so that $A_1,A_2$ are independent, $A_4$ is a clique, and there are no edges between $A_1$ and $A_3$ ?

Keywords: list partition; polynomial algorithm

Posted by mdevos
updated May 18th, 2010

1 comment

Graph Theory » Topological G.T. » Planar graphs

What is the largest graph of positive curvature? ★

Author(s): DeVos; Mohar

Problem What is the largest connected planar graph of minimum degree 3 which has everywhere positive combinatorial curvature, but is not a prism or antiprism?

Keywords: curvature; planar graph

Posted by mdevos
updated August 30th, 2011

2 comments

Number Theory » Combinatorial N.T.

Few subsequence sums in Z_n x Z_n ★★

Author(s): Bollobas; Leader

Conjecture For every $0 \le t \le n-1$ , the sequence in ${\mathbb Z}_n^2$ consisting of $n-1$ copes of $(1,0)$ and $t$ copies of $(0,1)$ has the fewest number of distinct subsequence sums over all zero-free sequences from ${\mathbb Z}_n^2$ of length $n-1+t$ .

Keywords: subsequence sum; zero sum

Posted by mdevos
updated March 10th, 2007

add new comment

Number Theory » Combinatorial N.T.

Olson's Conjecture ★★

Author(s): Olson

Conjecture If $a_1,a_2,\ldots,a_{2n-1}$ is a sequence of elements from a multiplicative group of order $n$ , then there exist $1 \le j_1 < j_2 \ldots < j_n \le 2n-1$ so that $\prod_{i=1}^n a_{j_i} = 1$ .

Keywords: zero sum

Posted by mdevos
updated March 10th, 2007

add new comment

Graph Theory » Basic G.T. » Minors

Jorgensen's Conjecture ★★★

Author(s): Jorgensen

Conjecture Every 6-connected graph without a $K_6$ minor is apex (planar plus one vertex).

Keywords: connectivity; minor

Posted by mdevos
updated March 10th, 2007

add new comment

Graph Theory » Basic G.T. » Minors

Highly connected graphs with no K_n minor ★★★

Author(s): Thomas

Problem Is it true for all $n \ge 0$ , that every sufficiently large $n$ -connected graph without a $K_n$ minor has a set of $n-5$ vertices whose deletion results in a planar graph?

Keywords: connectivity; minor

Posted by mdevos
updated March 10th, 2007

add new comment

Combinatorics » Matrices

The Alon-Tarsi basis conjecture ★★

Author(s): Alon; Linial; Meshulam

Conjecture If $B_1,B_2,\ldots B_p$ are invertible $n \times n$ matrices with entries in ${\mathbb Z}_p$ for a prime $p$ , then there is a $n \times (p-1)n$ submatrix $A$ of $[B_1 B_2 \ldots B_p]$ so that $A$ is an AT-base.

Keywords: additive basis; matrix

Posted by mdevos
updated March 8th, 2007

add new comment

Combinatorics » Matrices

The permanent conjecture ★★

Author(s): Kahn

Conjecture If $A$ is an invertible $n \times n$ matrix, then there is an $n \times n$ submatrix $B$ of $[A A]$ so that $perm(B)$ is nonzero.

Keywords: invertible; matrix; permanent

Posted by mdevos
updated March 8th, 2007

add new comment

Combinatorics » Matrices

The additive basis conjecture ★★★

Author(s): Jaeger; Linial; Payan; Tarsi

Conjecture For every prime $p$ , there is a constant $c(p)$ (possibly $c(p)=p$ ) so that the union (as multisets) of any $c(p)$ bases of the vector space $({\mathbb Z}_p)^n$ contains an additive basis.