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.

Keywords: additive basis; matrix

Posted by mdevos
updated March 8th, 2007
add new comment
Combinatorics » Matrices

A nowhere-zero point in a linear mapping ★★★

Author(s): Jaeger

Conjecture   If $ {\mathbb F} $ is a finite field with at least 4 elements and $ A $ is an invertible $ n \times n $ matrix with entries in $ {\mathbb F} $, then there are column vectors $ x,y \in {\mathbb F}^n $ which have no coordinates equal to zero such that $ Ax=y $.

Keywords: invertible; nowhere-zero flow

Posted by mdevos
updated March 8th, 2007
add new comment