Problems / combinatorics
combinatorics / Topological graph theory; crossing numbers
Zarankiewicz's crossing-number conjecture (Turan's brick factory problem)
Claims cr(Km,n)=⌊2m⌋⌊2m−1⌋⌊2n⌋⌊2n−1⌋ for all positive m,n. The lower bound comes from a linear-algebra inequality ∑i,jdim(Ui∩Vj)≤⌊m2/4⌋N for subspaces with Ui∩Vi=0, proved by interpolation, applied through signed intersections of cycles; Zarankiewicz's drawing gives the upper bound. Crossings are counted as points. It does NOT address rectilinear, pair or odd crossing numbers of Km,n.