2026/07/17 by Jesse Geneson
#math.CO #cs.DM
Fulek defined the 0-1 matrix L3=\beginpmatrix 10010
00001
01100 \endpmatrix and asked whether ex(n,L3) = O(n). We prove that every r× s 0-1 matrix avoiding L3 has at most 27r+2s 1 entries. Fulek's general lower bound construction has 6n-8 1 entries, so 6n-8≤ ex(n,L3)≤29n for n≥5. The same argument applies to an infinite family. If Qa,b,k,ℓ is the light three-row matrix with column word 1a3k1b2^ℓ, where a,b,ℓ≥1 and k≥2, then ex(r,s,Qa,b,k,ℓ) ≤(5(k-1)(4b+1)+a+b+ℓ-1)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 L3. 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.