Linear Tur'an Numbers of Four-Edge Uniform Paths via Incidence Rank
Abstract
Let P4r denote the r-uniform expansion of the graph path with four edges. We prove that every n-vertex linear r-uniform P4r-free hypergraph has at most (r+1)n/r edges, resolving a conjecture of Adak and Verma for every r ≥ 2. Equality holds precisely for vertex-disjoint unions of Steiner systems S(2,r,r2). The main ingredient is a sharp incidence-rank inequality. If N(H) is the edge-vertex incidence matrix of a linear r-uniform hypergraph whose line graph is a cograph, then (r+1)rankℝ N(H) ≥ r|E(H)|. Equality holds exactly when every edge-containing component is an S(2,r,r2). The proof follows the union-join decomposition of cographs. At a join node, the row-difference spaces of the co-components are mutually orthogonal, and the possible rank defect is determined by balanced co-components. Perron-Frobenius theory identifies the smallest balanced pieces as parallel classes of r disjoint r-sets, while an orthogonality argument bounds their number by r+1. The equality case then reconstructs the Steiner system. The linear Turán bound follows from rankℝ N(H) ≤ |V(H)|.
Related
BibTeX
@misc{ramani2026linear,
title = {{Linear Tur'an Numbers of Four-Edge Uniform Paths via Incidence Rank}},
author = {Mahesh Ramani},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20173},
eprint = {2609.20173},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20173},
}
RIS
TY - UNPB
TI - Linear Tur'an Numbers of Four-Edge Uniform Paths via Incidence Rank
AU - Mahesh Ramani
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.20173
UR - https://arxiv.org/abs/2609.20173
AB - Let P_4^r denote the r-uniform expansion of the graph path with four edges. We prove that every n-vertex linear r-uniform P_4^r-free hypergraph has at most (r+1)n/r edges, resolving a conjecture of Adak and Verma for every r ≥ 2. Equality holds precisely for vertex-disjoint unions of Steiner systems S(2,r,r^2). The main ingredient is a sharp incidence-rank inequality. If N(H) is the edge-vertex incidence matrix of a linear r-uniform hypergraph whose line graph is a cograph, then (r+1)rank_ℝ N(H) ≥ r|E(H)|. Equality holds exactly when every edge-containing component is an S(2,r,r^2). The proof follows the union-join decomposition of cographs. At a join node, the row-difference spaces of the co-components are mutually orthogonal, and the possible rank defect is determined by balanced co-components. Perron-Frobenius theory identifies the smallest balanced pieces as parallel classes of r disjoint r-sets, while an orthogonality argument bounds their number by r+1. The equality case then reconstructs the Steiner system. The linear Turán bound follows from rank_ℝ N(H) ≤ |V(H)|.
ER -