zbMATH — the first resource for mathematics

A theorem on incidence matrices and quasirandom hypergraphs. (English) Zbl 1277.05106
Brualdi, Richard A. (ed.) et al., Combinatorics and graphs. Selected papers based on the presentations at the 20th anniversary conference of IPM on combinatorics, Tehran, Iran, May 15–21, 2009. Dedicated to Reza Khosrovshahi on the occasion of his 70th birthday. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4865-4/pbk). Contemporary Mathematics 531, 201-207 (2010).
Summary: Let \(\binom{X}{\leq k}\) denote the family of subsets of \(X\) having at most \(k\) elements. Consider a family \(\mathcal F\) containing subsets of \(X\) and an incidence matrix \(M=M(\mathcal F)\) with columns indexed by \(\binom{X}{\leq k}\) and with rows indexed by \(\mathcal F\), namely, \(M_{F,G} = 1\) if \(F\supset G\) or \(0\) otherwise.
We give sufficient conditions for a family \(\mathcal F\) to guarantee that \(M(\mathcal F)\) has full rank. As a corollary we infer that for \(\mathcal F= \binom{X}{\geq | X| -k}\), \(| X| \geq 2k\), \(M(\mathcal F)\) has full rank. This extends a well-know theorem of D. H. Gottlieb [Proc. Am. Math. Soc. 17, 1233–1237 (1966; Zbl 0146.01302)] which found many applications in combinatorics.
As an application of our result, we show that if a \(k\)-uniform hypergraph on \(n\) vertices contains roughly the same number of edges in every set of size \(0.99n\) then this is also true for sets of size \(0.01n\). This yields an alternative proof of a result of R. Yuster [Combinatorica 30, No. 2, 239–246 (2010; Zbl 1224.05476)] on hereditary quasirandom properties.
For the entire collection see [Zbl 1202.05003].
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C65 Hypergraphs
05C80 Random graphs (graph-theoretic aspects)
05D05 Extremal set theory
15A03 Vector spaces, linear dependence, rank, lineability