4 papers
Beyond Liu's 0.382709 threshold for the union-closed sets conjecture
Simone Costa, Ankan Sadhu
The union-closed sets conjecture asks whether every finite union-closed family containing a nonempty set has an element contained in at least half of its members. Let $c_{\mathrm{U…
A Proof of Albertson's Conjecture
Ankan Sadhu
Albertson's conjecture states that every graph of chromatic number r has crossing number at least that of the complete graph K_r. We prove the conjecture for all r. The proof combi…
An improved upper bound for the Zarankiewicz number z(43;2) <= 294 via structural rigidity, including hexary packing number pa(5;6) = 31
Ankan Sadhu
The Zarankiewicz number z(n;2) is the largest number of ones in an n x n zero-one matrix with no all-one 2x2 submatrix. At n=43, the Kovari-Sos-Turan bound, sharpened by Reiman, gi…
A congruence obstruction to Roman's bound for Zarankiewicz numbers
Ankan Sadhu
Let z(m,n;s,t) be the largest number of ones in an m x n zero-one matrix with no s x t all-ones submatrix. Roman's 1975 inequality remains the best general upper bound for s>=3, bu…