Incidence Rank and Bounded Defect for Linear Hypergraphs with Cograph Line Graphs

Abstract

Let $N(H)$ be the edge--vertex incidence matrix of a finite linear $s$-uniform hypergraph whose line graph is a cograph, and define \[ R_s(H)=(s+1)\operatorname{rank}_{\mathbb R}N(H)-s|E(H)|. \] The inequality $R_s(H)\ge 0$ holds, with equality characterized by affine planes of order $s$ on every row-dependent component. Under the corresponding finite-net completion hypothesis, connected systems with bounded $R_s$ admit an explicit classification. If $F$ is connected, $R_s(F)=d\le s-1$, the completion hypothesis holds through deficiency $d$, and $s>(d-1{)}^2$, then either $N(F)$ has full row rank and $|E(F)|=d$, or $F$ lies in a unique affine plane of order $s$. In the latter case, for some $0\le h\le d$, the system contains every line in $s+1-h$ parallel classes and exactly $d-h$ additional lines from the remaining $h$ classes. Conversely, each such system has defect $d$. Bruck's theorem gives the classification for every fixed $d$ and all sufficiently large $s$, while Metsch's completion theorem covers $d=o(s^{1/3})$. As a global consequence, if the total defect is at most $D$ in the completion range, deleting at most $D$ edges leaves a vertex-disjoint union of finite nets and affine planes. The associated column defect and row leverage are determined explicitly as well.

arXiv comment15 pages