To avoid issues with the parity of n and small sporadic examples, I will focus on the following relaxation of Problem 1, which asks for the asymptotically maximum basis density for rank-r matroids with no $U_{s,t}$-minor.<\/p>\n
Problem 2:<\/strong> What is $\\lim_{n \\to\\infty}\\frac{\\text{ex}_{\\mathsf M}(n, r, U_{s,t})}{\\binom{n}{r}}$? Call this number $\\pi_{\\mathsf M}(r, U_{s,t})$.<\/p>\n In this post I will discuss recent joint work with Jorn van der Pol and Michael Wigal [vdPWW25+] on these problems, with an emphasis on the following two points. First, Problems 1 and 2 are the specializations of the Tur\u00e1n number and Tur\u00e1n density of the daisy hypergraph $\\mathcal D_r(s, t)$ to the class of matroid basis hypergraphs. Second, Problems 1 and 2 lead to many interesting related open problems of varying levels of difficulty. I hope that the interested reader will solve some of these open problems!<\/p>\n\n\n\n I’ll begin with the original motivation for Problem 1: it is the Tur\u00e1n number of the daisy hypergraph $\\mathcal D_r(s,t)$ within the class of matroid basis hypergraphs. I will briefly explain what this means, and why it is interesting. For all integers r,s,t with $r,t \\ge s \\ge 1$, an (r, s, t)-daisy<\/em>, denoted $\\mathcal D_r(s,t)$, is an r-uniform hypergraph with vertex set $S \\cup T$ and edge set $\\{S \\cup X \\mid X \\in T^{(s)}\\}$, where S is an (r – s)-element set, T is a t-element set disjoint from S, and $T^{(s)}$ is the set of all s-element subsets of T. The set S is the stem<\/em> and the sets in $T^{(s)}$ are the petals<\/em>. Note that $\\mathcal D_r(s,t)$ has $\\binom{t}{s}$ edges, that $\\mathcal D_s(s, t)$ is simply the t-vertex, s-uniform hypergraph $K^{(s)}_t$, and that $\\mathcal D_r(s,t)$ is a subgraph of both $\\mathcal D_r(s , t+1)$ and $\\mathcal D_r(s+1, t+1)$. See Figure 1 for some examples of daisies.<\/p>\n\n\n\n Daisies were first defined explicitly by Bollab\u00e1s, Leader, and Malvenuto, who showed that a well-known problem about the hypercube graph [Conjecture 8, BLM11] is equivalent to a natural conjecture about the Tur\u00e1n densities of daisies. The Tur\u00e1n number <\/em>of an r-uniform hypergraph H, denoted $\\text{ex}(n, r, H)$, is the maximum number of edges of an n-vertex, r-uniform hypergraph without H as a subgraph, and the Tur\u00e1n density<\/em> of H is $\\pi(r, H) = \\lim_{n \\to\\infty}\\frac{\\textrm{ex}(n, r, H)}{\\binom{n}{r}}$. These parameters are very well-studied; see Keevash’s survey [K11]. Bollob\u00e1s, Leader, and Malvenuto conjectured that $\\lim_{r \\to \\infty} \\pi(\\mathcal D_r(s,t)) = 0$ for all integers s and t with $t \\ge s \\ge 1$ [Conjecture 4, BLM11], which is a natural conjecture because as r grows, the daisy $\\mathcal D_r(s,t)$ becomes sparser and sparser and therefore should be harder to avoid as a subgraph. However, this conjecture was recently disproved by Ellis, Ivan, and Leader for all $t \\ge s \\ge 2$ [Theorem 5, EIL24].<\/p>\n\n\n\n Theorem 1<\/strong> [EIL24]: If q is a prime power, then $$\\lim_{r \\to \\infty} \\pi(\\mathcal D_r(2, q + 2)) \\ge \\prod_{i=1}^{\\infty} (1 – q^{-i}).$$<\/p>\n\n\n\n This is where matroids come into play: the hypergraphs used to find this lower bound are basis hypergraphs of $\\mathbb F_q$-representable matroids, meaning that the vertex set is the ground set of the matroid and the edge set is the basis set of the matroid. In [vdPWW25+] we explored the construction used to prove Theorem 1 and found a connection between daisies and matroids: the basis hypergraph of a rank-r matroid M has a $\\mathcal D_r(s,t)$-subgraph if and only if M has a $U_{s,t}$-minor [Corollary 2.3, vdPWW25+]. So $\\textrm{ex}_{\\mathsf M}(n, r, U_{s,t})$ is the maximum number of edges of an n-element, rank-r matroid basis hypergraph without $\\mathcal D_r(s,t)$ as a subgraph. Therefore, $\\textrm{ex}_{\\mathsf M}(n, r, U_{s,t}) \\le \\textrm{ex}(n, r, \\mathcal D_r(s,t))$ and $\\pi_{\\mathsf M}(r, U_{s,t}) \\le \\pi(r, \\mathcal D_r(s,t))$, so Problems 1 and 2 give an approach for finding new lower bounds for $\\lim_{r \\to \\infty} \\pi(\\mathcal D_r(s,t))$, which in turn would likely lead to new insights into the hypercube graph.<\/p>\n\n\n\n The basis density parameter $\\pi_{\\mathsf M}(r, U_{s,t})$ is known in only a few nontrivial cases. In light of Theorem 1, the case $(s, t) = (2, q + 2)$ for a prime power q is particularly interesting.<\/p>\n\n\n\n Theorem 2<\/strong> [vdPWW25+]: If $r \\ge 2$ and $q$ is a prime power, then $$\\pi_{\\mathsf M}(r, U_{2,q + 2}) = r! \\cdot \\left(\\frac{q – 1}{q^r – 1}\\right)^r \\cdot b(r,q),$$ where $b(r,q)$ is the number of bases of the rank-r projective geometry over the finite field of order q. In particular, $\\lim_{r \\to \\infty} \\pi_{\\mathsf M}(r, U_{2,q+2}) = \\prod_{i=1}^{\\infty} (1 – q^{-i})$.<\/p>\n\n\n\n This was proved for q = 2 by Alon [A24] but was unknown in all other cases. Interestingly, Theorem 2 shows that one cannot use matroid basis hypergraphs to improve the lower bound of Theorem 1. The key to the proof is a theorem of Kung [K93] that upper bounds the number of points of a rank-r matroid with no $U_{2,q + 2}$-minor. <\/p>\n\n\n\n The only other known instances of Problem 2 are for the smallest nontrivial values of s and t.<\/p>\n\n\n\n Theorem 3 <\/strong>[vdPWW25+]: If $r \\ge 3$, then $\\pi_{\\mathsf M}(r, U_{3,4}) = \\frac{r! \\cdot 2^{\\lfloor r\/2 \\rfloor}}{r^r}$.<\/p>\n\n\n\n The proof is straightforward and relies on the fact that every matroid with no $U_{3,4}$-minor is a direct sum of matroids with rank at most two. The instance $(s,t) = (3,5)$ is more difficult, and we were only able to solve the case $r = 3$.<\/p>\n\n\n\n Theorem 4<\/strong> [vdPWW25+]: $\\pi_{\\mathsf M}(3, U_{3,5}) = 3\/4$.<\/p>\n\n\n\n However, this is notable because Tur\u00e1n [T41] conjectured that $\\pi(3, K_5^{(3)}) = 3\/4$, so Theorem 3 shows that this conjecture holds within the class of matroid basis hypergraphs, via the connection described in the previous section. The proof of Theorem 4 is structural, and relies on the fact that every rank-3 matroid with no $U_{3,5}$-restriction either has no $U_{2,5}$-minor or can be covered by two lines [Lemma 6.4, vdPWW25+].<\/p>\n\n\n\n In light of Theorems 2, 3, and 4, there are several instances of Problem 2 that may not be difficult to solve.<\/p>\n A solution to (1) would surely use a theorem of Geelen and Nelson about the number of points of a rank-r matroid with no $U_{2,t+2}$-minor [GN15], so when r is sufficiently large I expect that $\\pi_{\\mathsf M}(r, U_{2,t+2}) = \\pi_{\\mathsf M}(r, U_{2,q+2})$ where q is the largest prime power at most t. For (2), I expect that $\\pi_{\\mathsf M}(r, U_{q,q+2}) = \\pi_{\\mathsf M}(r, U_{2,q+2})$. Problem (3) is interesting because $\\pi_{\\mathsf M}(r, U_{s,s+1})$ is the asymptotic maximum basis density for rank-r matroids with circumference at most s. It seems likely that the densest such matroids are direct sums of uniform matroids with rank at most s – 1. Finally, for (4) it seems like the answer should be given by the freest rank-3 matroids that can be covered by $(t-1)\/2$ lines when t is odd, or by $(t – 2)\/2$ lines and one point when t is even.<\/p>\n I’ll close by discussing some interesting problems related to Problems 1 and 2, beginning with the following generalization of Problem 1.<\/p>\n Problem 3: <\/strong>Let $\\mathcal M$ and $\\mathcal F$ be sets of matroids. What is the maximum number of bases of an n-element, rank-r matroid in $\\mathcal M$ with no minor in $\\mathcal F$?\u00a0<\/p>\n This problem has many interesting special cases. For example, when $\\mathcal M$ is the class of graphic matroids and $\\mathcal F$ is empty, Problem 3 is asking for the maximum number of spanning trees among all n-edge, (r+1)-vertex graphs, which has been solved for many choices of n and r by Kelmans [K96]. It would be interesting to obtain the binary analogue of Kelmans’ results.<\/p>\n Problem 4:<\/strong> Find the maximum number of bases of an n-element, rank-r binary matroid.<\/p>\n This is just Problem 1 for $(s,t) = (2,4)$, and is most interesting when $n < 2^r – 1$. When $n = 2^r – 2^{r – c}$ for some $c \\ge 1$ it seems likely that the number of bases will be maximized by the rank-r Bose-Burton geometry on n elements, but it is unclear what the answer should be for other values of n.<\/p>\n In the case that $\\mathcal M$ is the class of rank-3 affine matroids over $\\mathbb R$ and $\\mathcal F$ is empty, Problem 3 has a more geometric flavor.<\/p>\n Problem 5:<\/strong> Among all sets of n points in $\\mathbb R^2$ with no t in general position, what is the maximum number of non-collinear triples?<\/p>\n Theorems 3 and 4 can be used to solve this problem when t = 4 or 5, but this problem is open for all t at least six. Of course, one can also replace $\\mathbb R^2$ with $\\mathbb F^s$ for any field $\\mathbb F$ and integer $s \\ge 2$, and seek to maximize the the number of s-sets in general position. However, Problem 5 as stated is in some sense dual to a still-open problem of Erd\u0151s [E88]: among all sets of n points in $\\mathbb R^2$ with no four on a line, what is the maximum cardinality of a subset in general position, in the worst case?\u00a0<\/p>\n Clearly Problem 3 has a wide variety of specializations, so I hope that every matroid theorist can find (and solve!) some instance that suits their interests.<\/p>\n\n\n\n [A24] N. Alon. Erasure list-decodable codes and Tur\u00e1n hypercube problems. Finite Fields and Their Applications, <\/em>100:102513, 2024.<\/p>\n\n\n\n [BLM11] B. Bollab\u00e1s, I. Leader, C. Malvenuto. Daisies and other Tur\u00e1n problems. Combin. Probab. Comput,, <\/em>20(5):743\u2014747, 2011.<\/p>\n\n\n\n [EIL24] D. Ellis, M.-R. Ivan, I. Leader. Tur\u00e1n densities for daisies and hypercubes. Bull. London Math. Soc., <\/em>56(12):3838\u20143853, 2024.<\/p>\n\n\n\n [E88] P. Erd\u0151s. Some old and new problems in combinatorial geometry. In Applications of discrete mathematics (Clemson, SC, 1986), <\/em>pages 32\u201437, 1988.<\/p>\n\n\n\n [GN15] J. Geelen, P. Nelson. The number of points in a matroid with no n-point line as a minor. J. Combin. Theory Ser. B, <\/em>100(6):625\u2014630, 2010.<\/p>\n\n\n\n [K11] P. Keevash. Hypergraph Tur\u00e1n problems. In Surveys in combinatorics, volume 392<\/em> of London Math. Soc. Lecture Note Ser., <\/em>pages 83\u2014139. Cambridge Univ. Press, Cambridge, 2011.<\/p>\n\n\n\n [K96] A. Kelmans. On graphs with the maximum number of spanning trees. Random Struct. Algorithms, <\/em>9:177\u2014192, 1996.<\/p>\n\n\n\n [K93] J. P. S. Kung. Extremal matroid theory. In Graph structure theory (Seattle, WA, 1991), volume 147 of Comtemp. Math., <\/em>pages 21\u201461. Amer. Math. Soc., Providence, RI, 1993.<\/p>\n\n\n\n [T41] P. Tur\u00e1n. On an extremal problem in graph theory. Mat. Fiz. Lapok, <\/em>48:436\u2014452, 1941.<\/p>\n\n\n","protected":false},"excerpt":{"rendered":" What is the maximum number of bases of an n-element, rank-r matroid? This question is not interesting: the answer the answer is $\\binom{n}{r}$, and equality holds only for the uniform matroid $U_{r,n}.$ However, if we exclude a fixed uniform matroid … Continue reading The Tur\u00e1n Density of a Daisy<\/h2>\n\n\n\n
![\"\"](\"https:\/\/matroidunion.org\/wp-content\/uploads\/2025\/03\/Blog_images_daisy.png\")
<\/a>Results<\/h2>\n\n\n\n
Open Problems<\/h2>\n\n\n\n
\n
References<\/h2>\n\n\n\n