2015/06/21 by Jiayin Sun, Sun, J., S. B. Damelin +1
Computer Science · Mathematics · #05B35 #Coding theory and cryptography #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1506.06425
openalex publication_date 2015/06/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce various quantities that can be defined for an arbitrary matroid, and show that certain conditions on these quantities imply that a matroid is not representable over \mathbbFq where q is a prime power. Mostly, for a matroid of rank r, we examine the proportion of size-(r-k) subsets that are dependent, and give bounds, in terms of the cardinality of the matroid and q, for this proportion, below which the matroid is not representable over \mathbbFq. We also explore connections between the defined quantities and demonstrate that they can be used to prove that random matrices have high proportions of subsets of columns independent. Our study relates to the results of our papers [4,5,11] dealing with the cardinality of sets of k-independent vectors over \mathbbFq and the Maximal Distance Separation Conjecture over \mathbbFq.