×

zbMATH — the first resource for mathematics

On the asymptotic proportion of connected matroids. (English) Zbl 1244.05047
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.

MSC:
05B35 Combinatorial aspects of matroids and geometric lattices
05A16 Asymptotic enumeration
05C80 Random graphs (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Babai, L., Automorphism groups, isomorphism, reconstruction, (), 1447-1540 · Zbl 0846.05042
[2] Blackburn, J.E.; Crapo, H.H.; Higgs, D.A.; Blackburn, J.E.; Crapo, H.H.; Higgs, D.A., A catalogue of combinatorial geometries, Math. comp., Math. comp., 27, 121, 155-166, (1973), (addendum), loose microfiche suppl. A12-G12 · Zbl 0274.05020
[3] T. Brylawski, D. Kelly, Matroids and Combinatorial Geometries, Carolina Lecture Series, University of North Carolina, Department of Mathematics, Chapel Hill, NC, 1980.
[4] Crapo, H.; Schmitt, W., A unique factorization theorem for matroids, J. combin. theory ser. A, 112, 2, 222-249, (2005) · Zbl 1076.05020
[5] Kelly, D.G.; Oxley, J.G., Threshold functions for some properties of random subsets of projective spaces, Quart. J. math. Oxford ser. (2), 33, 132, 463-469, (1982) · Zbl 0504.05023
[6] Kelly, D.G.; Oxley, J.G., On random representable matroids, Stud. appl. math., 71, 3, 181-205, (1984) · Zbl 0596.05017
[7] Kordecki, W., Small submatroids in random matroids, Combin. probab. comput., 5, 3, 257-266, (1996) · Zbl 0874.05047
[8] Kordecki, W., Random matroids, Dissertationes math. (rozprawy mat.), 367, 56, (1997) · Zbl 0934.05034
[9] Oxley, J.G., Matroid theory, (1992), Oxford University Press New York · Zbl 0784.05002
[10] Rónyai, L.; Babai, L.; Ganapathy, K.M., On the number of zero-patterns of a sequence of polynomials, J. amer. math. soc., 14, 3, 717-735, (2001), (electronic) · Zbl 0978.12001
[11] P. Vámos, On the representation of independence structures (1968) (unpublished).
[12] Welsh, D.J.A., Combinatorial problems in matroid theory, (), 291-306 · Zbl 0233.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.