×

An extremal problem for non-separable matroids. (English) Zbl 0215.33603

Théorie des matroïdes, Rencontre Franco-Britannique 1970, Lect. Notes Math. 211, 31-49 (1971).
Summary: Let \(E\) be a finite set, \(\mathcal E\subseteq \mathcal P(E)\) a matroid on \(E\). \(\mathcal E\) is non-separable if every pair of elements of \(E\) are in a common circuit (minimal member of \(\mathcal P(E)\backslash \mathcal E)\). The following two theorems are proved:
1. Every nonseparable matroid of rank \(r\) and cardinality \(n\) must have at least \(r(n-r)+1\) bases (maximal members of \(\mathcal E)\). There is for each \(r\) and \(n\), a unique matroid with precisely this many bases.
2. If \(\mathcal E\) is a nonseparable matroid of rank \(r\) on \(n\) elements containing more than \(r(n-r)+1\) bases, then \(\mathcal E\) must contain at least \(2(r-1)(n-r-1)+1+r\) bases if \(2r\leq n\) and \((2r-1)(n-r-1)+2\) bases if \(2r\geq n\).
For the entire collection see Zbl 0214.00201.

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices

Citations:

Zbl 0214.00201
Full Text: DOI