Spectral extrema for graphs: the Zarankiewicz problem (Q2380287): Difference between revisions

Summary: Let \(G\) be a graph on \(n\) vertices with spectral radius \(\lambda\) (this is the largest eigenvalue of the adjacency matrix of \(G\)). We show that if \(G\) does not contain the complete bipartite graph \(K_{t,s}\) as a subgraph, where \(2\leq t\leq s\), then \[ \lambda\leq \big((s-1)^{1/t}+ o(1)\big)n^{n-1/t}, \] for fixed \(t\) and \(s\) while \(n\to\infty\). Asymptotically, this bound matches the Kővári-Turán-Sós upper bound on the average degree of \(G\) (the Zarankiewicz problem).