Spectral extrema for graphs: the Zarankiewicz problem (Q2380287): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 07:56, 5 March 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