Spectral extrema for graphs: the Zarankiewicz problem (Q2380287): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 19:37, 2 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Spectral extrema for graphs: the Zarankiewicz problem |
scientific article |
Statements
Spectral extrema for graphs: the Zarankiewicz problem (English)
0 references
26 March 2010
0 references
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).
0 references
spectral radius
0 references
Kövari Turan Sos upper bound
0 references
Zarankiewicz problem
0 references