Spectral extrema for graphs: the Zarankiewicz problem
From MaRDI portal
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).
Recommendations
- An extremal problem for the spectral radius of a graph
- Extremal problems for the p-spectral radius of graphs
- Spectral extremal problems for hypergraphs
- Some new results and problems in spectral extremal graph theory
- Extremal problems on distance spectra of graphs
- Spectral extremal results for hypergraphs
- Extremal Graph Realizations and Graph Laplacian Eigenvalues
- Extremal graph characterization from the bounds of the spectral radius of weighted graphs
- Two spectral extremal results for graphs with given order and rank
- Three conjectures in extremal spectral graph theory
Cited in
(74)- The maximum spectral radius of C₄-free graphs of given order and size
- Degenerate Turán problems for hereditary properties
- The Colin de Verdière parameter, excluded minors, and the spectral radius
- The signless Laplacian spectral radius of graphs with no intersecting triangles
- Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs
- Spectral extremal results for hypergraphs
- Spectral radius and the 2-power of Hamilton cycle
- The maximum spectral radius of non-bipartite graphs forbidding short odd cycles
- Spectral extremal graphs for intersecting cliques
- The spectral radius of graphs with no intersecting odd cycles
- Generalizing theorems of Nosal and Nikiforov: triangles and quadrilaterals
- A spectral condition for the existence of the square of a path
- A unique characterization of spectral extrema for friendship graphs
- Spectral extrema of \(K_{s,t}\)-minor free graphs -- on a conjecture of M. Tait
- Adjacency eigenvalues of graphs without short odd cycles
- The spectral radius of graphs with no odd wheels
- Three conjectures in extremal spectral graph theory
- On minimally 2-(edge)-connected graphs with extremal spectral radius
- The maximum spectral radius of wheel-free graphs
- A sharp upper bound on the spectral radius of \(C_5\)-free/\(C_6\)-free graphs with given size
- On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees
- On a conjecture of spectral extremal problems
- The maximum spectral radius of graphs without spanning linear forests
- Spectral extremal graphs for disjoint cliques
- Spectral radius conditions for the existence of all subtrees of diameter at most four
- Stability of Woodall's theorem and spectral conditions for large cycles
- The maximum spectral radius of graphs of given size with forbidden subgraph
- A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs
- Sharp bounds for the signless Laplacian spectral radius in terms of clique number
- Extremal problems for the p-spectral radius of graphs
- The number of maximal cliques and spectral radius of graphs with certain forbidden subgraphs
- Maxima of the \(Q\)-index: graphs with no \(K_{s,t}\)
- Spectral extrema of graphs with bounded clique number and matching number
- The maximum spectral radius of \(\{C_3, C_5\}\)-free graphs of given size
- A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs
- Spectral extremal graphs for the bowtie
- Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size
- Refinement on Spectral Turán’s Theorem
- Forbidden theta graph, bounded spectral radius and size of non-bipartite graphs
- An \(A_\alpha\)-spectral Erdős-Pósa theorem
- On \(A_{\alpha}\) spectral extrema of graphs forbidding even cycles
- The index of signed graphs with forbidden subgraphs
- The bipartite Turán number and spectral extremum for linear forests
- Extremal results for \(C_3^-\)-free signed graphs
- Spectral extrema of \(\{ K_{k + 1}, \mathcal{L}_s \}\)-free graphs
- Spectral Turán problems for intersecting even cycles
- Spectral extremal problem on disjoint color-critical graphs
- An \(A_{\alpha}\)-spectral Erdős-Sós theorem
- On the spectral radius of graphs with given maximum degree and girth
- The signless Laplacian spectral radius of 2K₃-free graphs
- The minimum spectral radius for \(K_{r+1}\)-saturated graphs with \(r = 4\), 5
- Spectral extrema of graphs with fixed size: forbidden triangles and pentagons
- On the spectral radius of graphs without a gem
- Spectral extremal graphs without intersecting triangles as a minor
- The spectral even cycle problem
- Note on two Kirchhoff index Turán problems
- A spectral generalized Alon-Frankl theorem
- Spectral extremal problem on the fish graph
- A spectral version of the theorem of Zykov and Erdős
- Counting substructures and eigenvalues. II: Quadrilaterals
- Principal eigenvectors in hypergraph Turán problems
- A spectral generalized Erdős-Gallai theorem
- Spectral supersaturation: triangles and bowties
- The largest eigenvalue of \(\mathcal{C}_k^-\)-free signed graphs
- Brualdi-Hoffman-Turán problem of the gem
- Extensions on spectral extrema of \(\theta_{1,2,5}\)-free graphs with given size
- Spectral extremal results on the \(A_\alpha\)-spectral radius of graphs without \(K_{a,b}\)-minor
- Spectral bipartite Turán problems on linear hypergraphs
- Spectral radius and homeomorphically irreducible spanning trees of graphs
- More on Nosal's spectral theorem: books and 4-cycles
- Bowtie-saturated graphs and the spectral radius
- Bounds on the spectral radii of Berge C₅-free linear r-graphs
- Spectral extrema of graphs: forbidden hexagon
- A contribution to the Zarankiewicz problem
This page was built for publication: Spectral extrema for graphs: the Zarankiewicz problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380287)
