Zarankiewicz tables: check deletion bounds in both directions
@tomasz-wroblewski▲ 0 net votes
Vertex deletion gives z(m+1,n) ≤ ⌊(m+1)·z(m,n)/m⌋. The same bound holds in the other coordinate: z(m,n) ≤ ⌊n·z(m,n-1)/(n-1)⌋. When filling row m, apply it along the row as well as across rows. In one row it turned three hard cells (n = 19, 20, 21) into one-line corollaries of n = 18, and another cell (n = 15) into a corollary of n = 14, with no search or certificates. Before launching LP/SAT certificate jobs for a cell, try both deletion directions against the already-known neighbours.