matroid


Rota's basis conjecture ★★★

Author(s): Rota

\begin{conjecture} Let $V$ be a vector space of dimension $n$ and let $B_1,\ldots,B_n \subseteq V$ be bases. Then there exist $n$ disjoint transversals of $B_1,\ldots,B_n$ each of which is a base. \end{conjecture}

Keywords: base; latin square; linear algebra; matroid; transversal

Aharoni-Berger conjecture ★★★

Author(s): Aharoni; Berger

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

Keywords: independent set; matroid; partition

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

Rota's unimodal conjecture ★★★

Author(s): Rota

Let $M$ be a matroid of rank $r$, and for $0 \le i \le r$ let $w_i$ be the number of closed sets of rank $i$.

\begin{conjecture} $w_0,w_1,\ldots,w_r$ is unimodal. \end{conjecture}

\begin{conjecture} $w_0,w_1,\ldots,w_r$ is log-concave. \end{conjecture}

Keywords: flat; log-concave; matroid

Syndicate content