Spectral extrema for graphs: the Zarankiewicz problem L´szl´ Babai∗ a o Barry Guiduli†Submitted: Jul 12, 2007; Accepted: Sep 21, 2009; Published: Sep 25, 2009 Abstract Let G be a graph on n vertices with spectral radius λ (this is the largest eigenvalue of the adjacency matrix of G). We show that if G does not contain the complete bipartite graph Kt,s as a subgraph, where 2 t s, then λ (s − 1)1/t + o(1) n1−1/t for fixed t and s while n → ∞. Asymptotically, this bound matches the K˝v´rio a Tur´n-S´s upper bound on the average degree of G. | Spectral extrema for graphs the Zarankiewicz problem László Babai Barry Guiduli Submitted Jul 12 2007 Accepted Sep 21 2009 Published Sep 25 2009 Abstract Let G be a graph on n vertices with spectral radius A this is the largest eigenvalue of the adjacency matrix of G . We show that if G does not contain the complete bipartite graph Kt s as a subgraph where 2 t s then A s - 1 1 t o 1 n1-1 t for fixed t and s while n TO. Asymptotically this bound matches the Kovari-Turan-Sos upper bound on the average degree of G the Zarankiewicz problem . 1 Introduction The Zarankiewicz problem 16 is one of the classical and still largely open problems in extremal graph theory. The problem asks for the maximum number m of edges in a graph on n vertices which does not contain the complete bipartite graph Kt s. We will assume that 2 t s throughout the paper. We formulate the results in terms of the average degree 2m n. The following upper bound was given in 1954 by Kovari Sos and Turan 11 see also 2 . Theorem 1 Kovari-Sos-Turan . Let G be a graph on n vertices with m edges. If G does not contain Kt s as a subgraph then the average degree in G is 2m n s - 1 1 tn1-1 t t - 1. In 1996 Furedi 7 improved the asymptotic coefficient s 1 1 t to s t 1 1 t. Theorem 2 Ftiredi . Under the conditions of Theorem 1 2m n s t 1 1 tn1-1 t tn1-2 t t. 1 University of Chicago. E-mail laci@ E-mail barry@ THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R123 1 The order of magnitude n1-1 t is conjectured best possible but this has only been proven for special cases For t 2 it was proved by E. Klein as reported by P. Erdos in 5 . W. G. Brown 4 showed it for t 3 and more recently Kollar Ronyai and Szabo 10 showed it for all t s satisfying s t 1 improved to s t 1 in 1 . For the case t 2 even the coefficient of the leading n1-1 t term given by Kovari Sós and Turan has been shown to be best possible E. Klein for s 2 Z. Furedi 6 for all s . For t s 3 Furedi s upper bound 1 and Brown s .
