matroid

Aharoni-Berger conjecture ★★★

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 » 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).$