Almost entropic matroids establish new limits for set intersection systems
Almost entropic matroids and $(k,L)$-systems
Information Theory
Summary
This work looks at special families of sets where each set has the same number of elements, and any two sets share a number of elements from a specific list. The authors connect how large these families can grow to a mathematical object called almost entropic matroids. This connection lets them create a single, computable formula that improves or unifies all previous limits on the size of these families.
What this means in practice
- •For network designers: Determine precise bounds for network coding setups where combining information respects specific overlap constraints.
- •For error correction engineers: Use improved upper limits on code structures defined by intersection properties to guide design of robust error-correcting codes.
A theory result. No direct application yet.
Authors
Andrey Kupavskii, Nikolai Terekhov
Abstract
For an integer $k$ and a set of integers $L$, a $(k,L)$-system is a family of $k$-element sets such that the size of the intersection of any two distinct members belongs to $L$. Let $m(n,k,L)$ denote the maximum size of a $(k,L)$-system on a ground set of $n$ elements. In this work, we establish a close connection between the asymptotic growth of $m(n,k,L)$ and almost entropic matroids. As a consequence, we obtain a general computable upper bound on the asymptotics of $m(n,k,L)$ that unifies and strengthens all previously known upper bounds.