An Improved Upper Bound on the Zarankiewicz Number z(43;2)
2026-08-03 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study a special type of graph with two groups of 43 nodes and no small squares (cycles of length four) inside it. They focus on finding the maximum number of connections such a graph can have. They improved the known upper limit from 300 to 299 using a clever counting argument without computers. They also provide a construction showing that the number can be at least 284. Their work uses ideas from designs and Latin squares to exclude some possibilities.
Zarankiewicz numberbipartite graphfour-cycle-freeprojective planedegree profiletransversal designLatin squaresTarry's theoremPG(2,7)combinatorial design
Authors
Ankan Sadhu
Abstract
The Zarankiewicz number z(43;2) is the largest number of edges in a four-cycle-free bipartite graph with two parts of size 43. Reiman's bound gives z(43;2) <= 301, with equality only for the incidence graph of a projective plane of order six; no such plane exists, so z(43;2) <= 300. We prove z(43;2) <= 299. The argument is elementary and uses no computer search: a counting identity for the leave of the configuration shows that a hypothetical 300-edge graph admits one of exactly twenty-seven degree profiles per side, of which only four combinations are locally compatible. Three force two vertices to share six neighbours; the fourth forces a transversal design TD(6,6), hence four mutually orthogonal Latin squares of order six, contradicting Tarry's theorem. We also give an explicit 284-edge construction inside PG(2,7), so that 284 <= z(43;2) <= 299.