Linear extremal bounds for a family of forbidden $0$-$1$ matrices

Abstract

Fulek defined the $0$-$1$ matrix \[ L_3=\begin{pmatrix} 1&0&0&1&0\\ 0&0&0&0&1\\ 0&1&1&0&0 \end{pmatrix} \] and asked whether $\text{ex}(n,L_3) = O(n)$. We prove that every $r\times s$ $0$-$1$ matrix avoiding $L_3$ has at most $27r+2s$ $1$ entries. Fulek's general lower bound construction has $6n-8$ $1$ entries, so \[ 6n-8\leq \text{ex}(n,L_3)\leq29n \] for $n\geq5$. The same argument applies to an infinite family. If $Q_{a,b,k,\ell}$ is the light three-row matrix with column word $1^a3^k1^b2^\ell$, where $a,b,\ell\geq1$ and $k\geq2$, then \[ \text{ex}(r,s,Q_{a,b,k,\ell}) \leq\bigl(5(k-1)(4b+1)+a+b+\ell-1\bigr)r+2s. \] This verifies a conjecture of Pettie and Tardos on linear light patterns for an infinite family that includes the previously unresolved weight-five pattern $L_3$. The proof assigns matrix entries to edges of a bar $1$-visibility hypergraph, cuts gaps to control the multiplicity of these edges, and charges the cuts to a noncrossing graph on the rows.

Disclosure

“2. Fulek proposed L4 together with L3 and noted that the extremal functions of both are in O(nα(n)), where α is the inverse Ackermann function [1]. The method of this note does not prove a linear bound for L4 . Acknowledgments Codex with GPT-5.6 and Claude Code with Fable 5 were used for proof exploration, proof criticism, exposition, and revision. References [1] R. Fulek, Linear bound on extremal functions of some forbidden patterns in 0-1 matrices, Discrete Math. 309 (2009”

PDF page 9

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T18:57:31.074138Z

Structural counts