×

A density Hales-Jewett theorem for matroids. (English) Zbl 1310.05047

Summary: We show that if \(\alpha\) is a positive real number, \(n\) and \(\ell\) are integers exceeding 1, and \(q\) is a prime power, then every simple matroid \(M\) of sufficiently large rank, with no \(U_{2, \ell}\)-minor, no rank-\(n\) projective geometry minor over a larger field than \(\operatorname{GF}(q)\), and at least \(\alpha q^{r(M)}\) elements, has a rank-\(n\) affine geometry restriction over \(\operatorname{GF}(q)\). This result can be viewed as an analogue of the multidimensional density Hales-Jewett theorem for matroids.

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Dodos, P.; Kanellopoulos, V.; Tyros, K., A simple proof of the density Hales-Jewett theorem, Int. Math. Res. Not. (2013), in press
[2] Erdős, P.; Stone, A. H., On the structure of linear graphs, Bull. Amer. Math. Soc., 52, 1087-1091 (1946) · Zbl 0063.01277
[3] Furstenberg, H.; Katznelson, Y., IP-sets, Szemerédi’s theorem and Ramsey theory, Bull. Amer. Math. Soc. (N.S.), 14, 2, 275-278 (1986) · Zbl 0636.05016
[4] Furstenberg, H.; Katznelson, Y., A density version of the Hales-Jewett theorem, J. Anal. Math., 57, 64-119 (1991) · Zbl 0770.05097
[5] Geelen, J.; Kabell, K., Projective geometries in dense matroids, J. Combin. Theory Ser. B, 99, 1-8 (2009) · Zbl 1179.05026
[6] Geelen, J.; Kung, J. P.S.; Whittle, G., Growth rates of minor-closed classes of matroids, J. Combin. Theory Ser. B, 99, 420-427 (2009) · Zbl 1229.05072
[7] Geelen, J.; Nelson, P., The number of points in a matroid with no \(n\)-point line as a minor, J. Combin. Theory Ser. B, 100, 625-630 (2010) · Zbl 1231.05058
[8] Geelen, J.; Nelson, P., On minor-closed classes of matroids with exponential growth rate, Adv. Appl. Math., 50, 142-154 (2013) · Zbl 1310.05046
[9] Geelen, J.; Whittle, G., Cliques in dense \(GF(q)\)-representable matroids, J. Combin. Theory Ser. B, 87, 264-269 (2003) · Zbl 1026.05023
[10] Hales, A.; Jewett, R., Regularity and positional games, Trans. Amer. Math. Soc., 106, 2, 222-229 (1963) · Zbl 0113.14802
[11] Kung, J. P.S., Numerically regular hereditary classes of combinatorial geometries, Geom. Dedicata, 21, 1, 85-105 (1986) · Zbl 0591.05019
[12] Kung, J. P.S., Extremal matroid theory, (Graph Structure Theory. Graph Structure Theory, Seattle, WA, 1991. Graph Structure Theory. Graph Structure Theory, Seattle, WA, 1991, Contemp. Math., vol. 147 (1993), American Mathematical Society: American Mathematical Society Providence, RI), 21-61 · Zbl 0791.05018
[13] Nelson, P., Exponentially Dense Matroids (2011), University of Waterloo, Ph.D thesis
[14] Nelson, P., Growth rate functions of dense classes of representable matroids, J. Combin. Theory Ser. B, 103, 75-92 (2013) · Zbl 1255.05041
[15] Oxley, J. G., Matroid Theory (2011), Oxford University Press: Oxford University Press New York · Zbl 1254.05002
[16] Polymath, D. H.J., A new proof of the density Hales-Jewett theorem (2010), pp. 1-34 · Zbl 1239.05189
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.