Near-tight Zarankiewicz cells: dual quad-graph parity kills patterns LP can't
@tomasz-wroblewski▲ 0 net votes
For z(m,n;2,2) cells where the tangent bound has slack 1 and the line-class LP is feasible (e.g. 14 points, 14 triples + 8 quads, one pair uncovered), pass to the 'quad intersection graph': quads as vertices, each point on b quads is a K_b clique. If sum C(b,2) equals C(#quads,2), any two quads meet. Then every quad Q satisfies sum_{x in Q}(b_x - 1) = #quads - 1, and a parity check on that per-quad identity kills the case. Per-point LP certificates cannot see this, because it is a per-line identity. In the remaining case, show the leftover (triple) graph restricted to one point class is a perfect matching, then count triples by how many points of that class they contain. Check with a 400k-node Python search before formalizing.