On the rank of higher inclusion matrices (Q2922841)

An \(r\)-graph \(G\) is a pair \((V,E)\) such that \(V\) is a set and \(E\) is a family of \(r\)-element subsets of \(V\); the members of \(E\) are called edges of \(G\). Given \(r \geq s \geq 0\) and an \(r\)-graph \(G = (V,E)\), a \(\{0,1\}\)-matrix \(M = M_s^r(G)\) is said to be a higher inclusion matrix of \(G\) if the rows of \(M\) are indexed by the edges of \(G\), the columns of \(M\) are indexed by the \(s\)-element subsets of \(V\), and, for each edge \(e\) of \(G\) and each \(s\)-element subset \(S\) of \(V\), the entry of \(M\) corresponding to \(e\) and \(S\) is 1 if and only if \(S\) is a subset of \(e\). The authors denote by \(\text{rex}(n,t,r,s)\) the maximum number of edges of an \(r\)-graph \(G\) such that the rank of \(M_s^r(G)\) is at most \({n \choose s} - t\). A question of \textit{P. Keevash} [``Addendum to `Shadows and intersections: stability and new proofs''', Preprint (2010), \url{http://people.maths.ox.ac.uk/keevash/papers/kk-addendum.pdf}] can be phrased as follows: is \(\text{rex}(n,1,r,s) = {n \choose r} - {n-s \choose r-s}\), at least for \(n\) sufficiently large? The authors answer this question in the affirmative and prove the following general result: for \(r > s \geq 1\), there exist two positive constants \(c_0 := c_0(r,s)\) and \(n_0 := n_0(r,s)\) such that, for any two positive integers \(n\) and \(t\) with \(n \geq n_0\) and \(t \leq c_0n\), NEWLINE\[NEWLINE\text{rex}(n,t,r,s) = {n \choose r} - {n-s+1 \choose r-s+1} + {n-s+1-t \choose r-s+1}.NEWLINE\]NEWLINE NEWLINEFor \(n,t,r\) and \(s\) as in the result, the authors also determine the rank-extremal \(r\)-graphs, that is, the \(r\)-graphs \(G\) for which the rank of \(M_s^r(G)\) is at most \({n \choose s} - t\) and the number of edges is \(\text{rex}(n,t,r,s)\). This work is inspired by the open problem, posed by \textit{P. Frankl} and \textit{N. Tokushige} [Bolyai Soc. Math. Stud. 3, 229--250 (1994; Zbl 0816.05058)], of determining the minimum rank of \(M_s^r(G)\) in terms of the number of edges of \(G\).