On the rank of higher inclusion matrices
type: Item
instance of: scholarly article
title: On the rank of higher inclusion matrices
zbMATH Open document ID: 1307.05215
author: Codruţ Grosu
author: Yury Person
author: Tibor Szabó
publication date: 2014-10-15T00:00:00Z
full work available at URL: https://arxiv.org/abs/1306.2197
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 05B20
zbMATH DE Number: 6355574
zbMATH Keywords: \(r\)-graph
MaRDI profile type: Publication
OpenAlex ID: W1979031177
arXiv ID: 1306.2197
cites work: Maximum number of constant weight vertices of the unit \(n\)-cube contained in a \(k\)-dimensional subspace
cites work: Shadows and intersections in vector spaces
cites work: Intersection theorems and mod \(p\) rank of inclusion matrices
cites work: Sharp thresholds of graph properties, and the $k$-sat problem
cites work: On extremal hypergraphs for Hamiltonian cycles
cites work: A Certain Class of Incidence Matrices
cites work: Shadows and intersections: Stability and new proofs
cites work: Q5726070
cites work: Incidence Matrices of Subsets—A Rank Formula
cites work: Q3889197
cites work: Q3919726
cites work: Local resilience of graphs
DOI: 10.1112/JLMS/JDU029
published in: Journal of the London Mathematical Society. Second Series
review text: 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 o…
reviewed by: Peter Borg
description: scientific article; zbMATH DE number 6355574