On the asymptotic proportion of connected matroids

DOI10.1016/J.EJC.2011.01.016MaRDI QIDQ2275477zbMATH OpenOpenAlexFDO

Authors Dillon Mayhew, Mike Newman, D. J. A. Welsh, Geoff Whittle

Publication date 9 August 2011

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2011.01.016

zbMATH Keywords

asymptotic behaviormatroid connectivityrepresentable matroids

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Combinatorial aspects of matroids and geometric lattices (05B35) Random graphs (graph-theoretic aspects) (05C80)

Review text

Random graphs and their properties are well studied, but very little is known about the asymptotic behavior of classes of matroids. The proportion of graphs on \(n\) vertices with non-trivial automorphism group tends to zero as \(n\) tends to infinity and this is true for labeled as well as unlabeled graphs. The authors conjecture that asymptotically almost every matroid has trivial automorphism group, is arbitrarily highly connected and is not representable over any field. A proof is provided for the fact that the proportion of \(n\)-labeled matroids that are connected is asymptotically at least \(1/2\). The proof even of this most likely not best possible bound is highly non-trivial and suggests that the conjectures formulated in the paper are challenging.

Recommendations

• On properties of almost all matroids
• On Random Representable Matroids
• On the number of bases of almost all matroids
• Asymptotics of symmetry in matroids
• The highly connected matroids in minor-closed classes

Cites work

• A Catalogue of Combinatorial Geometries
• A unique factorization theorem for matroids
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 3666823 (Why is no real title available?)
• scientific article; zbMATH DE number 1070707 (Why is no real title available?)
• scientific article; zbMATH DE number 863496 (Why is no real title available?)
• scientific article; zbMATH DE number 3368629 (Why is no real title available?)
• On Random Representable Matroids
• On the number of zero-patterns of a sequence of polynomials
• Small Submatroids in Random Matroids
• THRESHOLD FUNCTIONS FOR SOME PROPERTIES OF RANDOM SUBSETS OF PROJECTIVE SPACES

Cited in

(62)

• How many delta-matroids are there?
• Asymptotics of symmetry in matroids
• On the number of bases of almost all matroids
• On properties of almost all matroids
• The Tutte polynomial of some matroids
• Delta-matroids as subsystems of sequences of Higgs lifts
• Complexity of packing common bases in matroids
• Hypergraph characterization of split matroids
• A combinatorial formula for Kazhdan-Lusztig polynomials of sparse paving matroids
• Matroids are not Ehrhart positive
• A method to construct all the paving matroids over a finite set
• Counting matroids in minor-closed classes
• Coxeter submodular functions and deformations of Coxeter permutahedra
• The highly connected matroids in minor-closed classes
• Matroids from hypersimplex splits
• The Merino-Welsh conjecture holds for series-parallel graphs
• Matroid relaxations and Kazhdan-Lusztig non-degeneracy
• Separable and equatable hypergraphs
• Matroid Theory for Algebraic Geometers
• On the number of matroids
• Positroids and non-crossing partitions
• On Random Representable Matroids
• On the structure of the \(h\)-vector of a paving matroid
• Doubly exponentially many ingleton matroids
• An entropy argument for counting matroids
• On the number of matroids compared to the number of sparse paving matroids
• Enumerating matroids of fixed rank
• List coloring of two matroids through reduction to partition matroids
• Balance in random signed intersection graphs
• The matroid secretary problem for minor-closed classes and random matroids
• Inclusion of forbidden minors in random representable matroids
• Secret sharing schemes for ports of matroids of rank 3.
• The number of partial Steiner systems and d-partitions
• Ehrhart theory of paving and panhandle matroids
• The Merino-Welsh conjecture for split matroids
• Equivariant Kazhdan-Lusztig theory of paving matroids
• Almost every matroid has an \(M(K_4)\)- or a \(\mathcal{W}^3\)-minor
• Weighted exchange distance of basis pairs
• Exchange Distance of Basis Pairs in Split Matroids
• Some inequalities for the Tutte polynomial
• Matchings in matroids over abelian groups
• Valuative invariants for large classes of matroids
• On the proportion of metric matroids whose Jacobians have nontrivial \(p\)-torsion
• Dominic Welsh: his work and influence
• Minors of matroids represented by sparse random matrices over finite fields
• Face enumeration for split matroid polytopes
• Solvable and nilpotent matroids: realizability and irreducible decomposition of their associated varieties
• The polytope of all matroids
• Optimizing extension techniques for discovering non-algebraic matroids
• Hilbert-Poincaré series of matroid Chow rings and intersection cohomology
• The algebraic matroid of the Heron variety
• Categorical valuative invariants of polyhedra and matroids
• Quantum automorphisms of matroids
• Price of anarchy in paving matroid congestion games
• On complete classes of valuated matroids
• The structure of symbolic powers of matroids
• Ehrhart bounds for panhandle and paving matroids through enumeration of chain forests
• Paving matroids: defining equations and associated varieties
• The inverse Z-polynomial of a matroid
• Enumerating the faces of split matroid polytopes
• Towards the proximity conjecture on group-labeled matroids
• Evolution of random representable matroids: minors, circuits, connectivity and the critical number

This page was built for publication: On the asymptotic proportion of connected matroids

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