2025/02/11 by David Ellis, Ellis, David, Maria‐Romina Ivan +3
Chemistry · Computer Science · Mathematics · #05C65 #Advanced Algebra and Logic #Combinatorics (math.CO) #Commutative Algebra (math.AC) #FOS: Mathematics #Graph theory and applications #History and advancements in chemistry
paper · pdf · doi:10.48550/arxiv.2502.07768
openalex publication_date 2025/02/11 · openalex created_date 2025/02/13 · openalex updated_date 2026/07/28
The proportion of d-element subsets of \mathbbF2d that are bases is asymptotic to ∏j=1∞(1-2-j) ≈ 0.29 as d → ∞. It is natural to ask whether there exists a (large) subset F of \mathbbF2d such that the proportion of d-element subsets of F that are bases is (asymptotically) greater than this number. As well as being a natural question in its own right, this would imply better lower bounds on the Turán densities of certain hypercubes and `daisy' hypergraphs. We give a negative answer to the above question. More generally, we obtain an asymptotically sharp upper bound on the proportion of linearly independent r-element subsets of a (large) family of vectors in \mathbbF2d, for r ≤ d. This bound follows from an exact result concerning the probability of obtaining a linearly independent sequence when we randomly sample r elements with replacement from our family of vectors: we show that this probability, for any family of vectors, is at most what it is when the family is the whole space \mathbbF2d ∖ \0\. Our results also go through when \mathbbF2 is replaced by \mathbbFq for any prime power q.