Home » Subject » Combinatorics » Matrices

The additive basis conjecture

Importance: High ✭✭✭
Author(s): Jaeger, Francois
Linial, Nathan
Payan, Charles
Tarsi, Michael
Subject: Combinatorics
» Matrices
Keywords: additive basis
matrix
Recomm. for undergrads: no
Posted by: mdevos
on: March 8th, 2007
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.

Definition: Let $ V $ be a finite dimensional vector space over the field $ {\mathbb Z}_p $. We call a multiset $ B $ with elements in $ V $ an additive basis if for every $ v \in V $, there is a subset of $ B $ which sums to $ v $.

It is worth noting that this conjecture would also imply that every $ 2c(3) $-edge-connected graph has a nowhere-zero 3-flow, thus resolving The weak 3-flow conjecture.

add new comment