Schrijver, Alexander


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 \}$.

\begin{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).$$ \end{conjecture}

Keywords: matroid; sumset; zero sum

Syndicate content