Projective geometries in dense matroids

DOI10.1016/J.JCTB.2008.03.003MaRDI QIDQ2519009zbMATH OpenOpenAlexFDO

Authors Jim Geelen, Kasper Kabell

Publication date 21 January 2009

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2008.03.003

zbMATH Keywords

growth ratematroidsprojective geometries

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Finite affine and projective planes (geometric aspects) (51E15)

Review text

If \(M\) is a matroid, let \(\varepsilon(M)\) denote its number of \textit{points}. The main result of the paper under review is the following theorem: {\parindent=6mm \begin{itemize} \item{}Let \(\mathcal M\) be a minor--closed class of matroid. Then either \begin{itemize} \item[(1)]\(\varepsilon(M) \leq r(M){}^{c}{}_{\mathcal M}\) for each \(M\in \mathcal M\), \item[(2)]there is a prime--power \(q\) such that \(\varepsilon(M)\leq c_{\mathcal M} q^{r(M)}\) for each \(M\in \mathcal M\), and \(\mathcal M\) contains all \({\mathrm GF}(q)\)--representble matroids, or \item[(3)]\(\mathcal M\) contains arbitrarily long lines. \end{itemize} \item{}Where \(c_{\mathcal M}\) is an integer constant depending on \(\mathcal M\). \end{itemize}} This result, is motivated by the following conjecture [\textit{J. P. S. Kung}, Extremal matroid theory. N. Robertson, Graph structure theory. Proceedings of the AMS-IMS-SIAM joint summer research conference on graph minors held June 22 to July 5, 1991 at the University of Washington, Seattle, WA (USA). Providence, RI: American Mathematical Society. Contemp. Math. 147, 21-61 (1993; Zbl 0791.05018)] which reads as follows. {\parindent=6mm \begin{itemize} \item{}Conjecture (\textit{Kung's Growth rate Conjecture}) Let \(\mathcal M\) be a minor--closed class of matroid. Then either \begin{itemize} \item[(1)]\(\varepsilon(M) \leq {c_{\mathcal M}} r(M)\) for each \(M\in \mathcal M\), \item[(2)]\(\varepsilon(M) \leq {c_{\mathcal M}} r(M)^2\) for each \(M\in \mathcal M\) and \(\mathcal M\) contains all graphic matroids, \item[(3)]there is a prime--power \(q\) such that \(\varepsilon(M)\leq \frac{q^{r(M)-1}}{q - 1}\) for each \(M\in \mathcal M\) with sufficiently high rank, and \(\mathcal M\) contains all \({\mathrm GF}(q)\)--representble matroids, or \item[(4)]\(\mathcal M\) contains arbitrarily long lines. \end{itemize} \end{itemize}}

Recommendations

• Matroids Denser than a Projective Geometry
• Projective geometries in exponentially dense matroids. I.
• Projective geometries in exponentially dense matroids. II.
• Matroid representation of projective spaces
• The structure of matroids with a spanning clique or projective geometry
• Projective orientations of matroids
• On geometries of the projective matrix space
• Hispanic Heritage Month
• Geometries of the projective matrix space
• scientific article; zbMATH DE number 3984008

Cites work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 475579 (Why is no real title available?)
• scientific article; zbMATH DE number 1182844 (Why is no real title available?)
• scientific article; zbMATH DE number 3257050 (Why is no real title available?)
• scientific article; zbMATH DE number 3078149 (Why is no real title available?)
• On the density of families of sets

Cited in

(19)

• Growth rates of minor-closed classes of matroids
• On perturbations of highly connected dyadic matroids
• Dense binary \(\mathrm{PG}(t-1,2)\)-free matroids have critical number \(t-1\) or \(t\)
• The templates for some classes of quaternary matroids
• A density Hales-Jewett theorem for matroids
• Representability of matroids with a large projective geometry minor
• The highly connected matroids in minor-closed classes
• Projective geometries in exponentially dense matroids. I.
• Projective geometries in exponentially dense matroids. II.
• The structure of matroids with a spanning clique or projective geometry
• Templates for binary matroids
• scientific article; zbMATH DE number 4106868 (Why is no real title available?)
• scientific article; zbMATH DE number 1182844 (Why is no real title available?)
• Matroids Denser than a Projective Geometry
• The densest matroids in minor-closed classes with exponential growth rate
• The number of points in a matroid with no \(n\)-point line as a minor
• Matroids arising from nested sequences of flats in projective and affine geometries
• Minors of matroids represented by sparse random matrices over finite fields
• Some open problems on excluding a uniform matroid

This page was built for publication: Projective geometries in dense matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2519009)