A contribution to the Zarankiewicz problem

By Vladimir Nikiforov. 2009

100 citations recorded by the source corpus.

Given positive integers m,n,s,t, let z(m,n,s,t) be the maximum number of ones in a (0,1) matrix of size m-by-n that does not contain an all ones submatrix of size s-by-t. We find a flexible upper bound on z(m,n,s,t) that implies the known bounds of Kovari, Sos and Turan, and of Furedi. As a consequence, we find an upper bound on the spectral radius of a graph of order n without a complete bipartite subgraph K_{s,t}.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/5fad14ae3f2878e9349be579711a77d30f298ed9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Yongtao Li
2. Xiaodong Zhang
3. Lihua Feng
4. Weijun Liu
5. Ya-Lei Jin
6. Bian He
7. Dheer Noal Desai
8. Michael Tait

In Discrete Mathematics and Combinatorics

1. Yongtao Li
2. Lihua Feng
3. Weijun Liu
4. Xiaodong Zhang
5. Bian He
6. Ya-Lei Jin
7. Dheer Noal Desai
8. Michael Tait

In Geometry and Topology

1. Yongtao Li
2. Xiaodong Zhang
3. Lihua Feng
4. Weijun Liu
5. Ya-Lei Jin
6. Bian He
7. Vladimir Nikiforov
8. Dheer Noal Desai

Citations in the corpus

• Some new results in extremal graph theory (2011, methodology): “Using a different method, in [82] we improved this result as follows: Theorem 3.”
• A survey on spectral conditions for some extremal graph problems (2021, background): “Furthermore, Nikiforov [154], Babai and Guiduli [7] independently obtained the spectral generalization of the theorem of Kővari, Sós and Turán when the forbidden graph is the complete bipartite graph Ks,t.”
• Sharp Bounds for the Signless Laplacian Spectral Radius in Terms of Clique Number (2012, background): “Further, Nikiforov explicitly advocated the study of general Turán problems in many publications (see [10–15]).”
• Spectral extremal graphs for intersecting cliques (2021, background): “In addition, Fiedler and Nikiforov [16] obtained tight sufficient conditions for graphs to be Hamiltonian or traceable.”
• The History of Degenerate (Bipartite) Extremal Graph Problems (2013, unknown): “In fact, he proved [198] that for all n ≥ b ≥ a ≥ 2 and a Ka,b-free graph Gn we have Λ(Gn) ≤ (b− a+ 1)1/an1−(1/a) + (a− 1)n1−(2/a) + (a− 2).”