Zarankiewicz problem

Zarankiewicz problem

The Zarankiewicz problem asks for the maximum number of edges in a bipartite graph that avoids a fixed complete bipartite subgraph, tracing roots to Kazimierz Zarankiewicz and attracting contributions from Paul Erdős, Pál Turán, Vera T. Sós, and Tibor Gallai. It sits at the crossroads of extremal graph theory, combinatorial design, and incidence geometry, linking to results by Kővári, Sós, and Turán and influencing work by József Beck, László Lovász, Endre Szemerédi, and Ronald Graham.

Statement and definitions

The standard formulation considers an m-by-n bipartite graph with parts often denoted by sizes m and n and seeks the extremal function z(m,n;s,t) giving the maximum number of edges while avoiding a complete bipartite graph K_{s,t} as a subgraph; classical contributors include Kazimierz Zarankiewicz, Paul Erdős, Vera T. Sós, and Pál Turán. Definitions rely on bipartite graphs studied in the context of Turán's theorem, Ramsey theory, Erdős–Stone theorem, and extremal functions such as ex(n,H) studied by Erdős and Andrásfai. The problem is often stated with symmetric parameters m=n and s=t, linking to bipartite incidence structures from projective plane constructions, finite field geometries, and combinatorial designs investigated by E. H. Moore, Reidemeister, and contemporary researchers like Fan Chung.

Known results and bounds

The foundational upper bound is the Kővári–Sós–Turán theorem, established by Kővári, Vera T. Sós, and Pál Turán, which gives z(m,n;s,t) = O(n m^{1-1/s} + m) in asymmetric form and supplies asymptotic constraints used by Paul Erdős, Endre Szemerédi, and Alfréd Rényi. For fixed s and t, matching lower bounds come from algebraic and geometric constructions by Elekes, József Beck, László Lovász, and Noga Alon, while specific exact values are known for small parameters via work of Faudree, Simonovits, and Bollobás. Improvements and refinements employ probabilistic methods of Paul Erdős and Joel Spencer, spectral techniques of Noga Alon and Béla Bollobás, and incidence bounds from Jean Bourgain and Terence Tao; these link the problem to results on unit distances studied by Erdős and Branko Grünbaum. Several conjectures remain open, notably exact asymptotics for z(n,n;s,s) for many s; progress connects to László Pyber's combinatorial group theory applications and to extremal problems studied by Miklós Ajtai and János Komlós.

Constructions and extremal examples

Extremal constructions exploit incidence structures from finite geometries such as finite projective planes, finite affine planes over finite field GF(q), and polarity graphs studied by Paul Erdős and Rónyai. Algebraic constructions using norm graphs and pseudorandom graphs were developed by Szemerédi, Miklós Ajtai, Elekes, and Michael Krivelevich to give lower bounds that match upper bounds in many regimes; explicit families include those by Kollár, Rónyai, and Szabó. Turán-type extremal examples relate to classical extremal graphs studied by Mantel and Turán and to polarity-based examples from H. F. Taranovsky and Vera T. Sós; these constructions often draw on combinatorial designs attributed to Kirkman and Steiner systems. Known tight examples for small s and t arise from incidence graphs of projective planes attributed to Évariste Galois-based finite field constructions and from extremal bipartite cages examined by Paul Erdős and C. A. B. Smith.

Methods and proof techniques

Techniques include double counting and the Cauchy–Schwarz inequality used in classical proofs by Kővári, Sós, and Turán; probabilistic methods pioneered by Paul Erdős and Joel Spencer yield nonconstructive lower bounds; algebraic geometry methods employed by Kollár and Terry Tao produce explicit norm graphs; spectral graph theory techniques by Noga Alon and Béla Bollobás give eigenvalue bounds; and the regularity lemma of Endre Szemerédi combined with counting lemmas from József Komlós and Miklos Simonovits provides asymptotic structure. Incidence theorems from Béla Szőkefalvi-Nagy-style combinatorics, polynomial method innovations by Larry Guth and Nets Katz, and sum-product estimates from Jean Bourgain and Terence Tao have been adapted to tighten bounds, while extremal set system methods relate to the Sauer–Shelah lemma associated with Vapnik–Chervonenkis theory and researchers like Noga Alon.

Variants and generalizations

Generalizations include hypergraph versions studied by Paul Erdős, Béla Bollobás, and Vera T. Sós, ordered bipartite variants connected to permutation patterns studied by Miklós Bóna and Richard Stanley, multidimensional Zarankiewicz-type problems linked to Elekes and Endre Szemerédi, and boolean matrix extremal problems with connections to learning theory developed by Noga Alon and Janos Komlos. Other variants consider forbidding induced copies related to the induced Turán problem explored by Vera T. Sós and Miklós Simonovits, density versions tied to removal lemmas by Jacob Fox and László Székely, and geometric incidence analogues stemming from the Sylvester–Gallai theorem studied by J. J. Sylvester and Tibor Gallai. The problem remains central to open questions in extremal combinatorics addressed by contemporary researchers including Noga Alon, Béla Bollobás, Jacob Fox, and Terence Tao.

Category:Extremal graph theory