A contribution to the Zarankiewicz problem

DOI10.1016/J.LAA.2009.10.040MaRDI QIDQ846298zbMATH OpenOpenAlexFDO

Authors Vladimir Nikiforov

Publication date 9 February 2010

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0903.5350

zbMATH Keywords

spectral radiusZarankiewicz problembipartite subgraphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)

Abstract: 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}.

Recommendations

• Spectral extrema for graphs: the Zarankiewicz problem
• Some remarks on the Zarankiewicz problem
• New results on the Zarankiewicz problem
• Extremal <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msub><mml:mi>K</mml:mi><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>s</mml:mi><mml:mo>,</mml:mo><mml:mi>t</mml:mi><mml:mo stretchy="false">)<
• Maximum number of edges of a bipartite graph without complete bipartite subgraphs

Cites work

• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• An Upper Bound on Zarankiewicz' Problem
• Bounds on graph eigenvalues. II
• New asymptotics for bipartite Turán numbers
• Norm-graphs: Variations and applications
• On Graphs that do not Contain a Thomsen Graph
• On a problem of K. Zarankiewicz
• Spectral extrema for graphs: the Zarankiewicz problem

Cited in

(56)

• The signless Laplacian spectral radius of graphs without intersecting odd cycles
• The automorphism group of projective norm graphs
• Spectral extremal problem on \(t\) copies of \(\ell\)-cycles
• Contributions to the problem of Zrankiewicz
• On the spectral radius of graphs without a gem
• Spectral extrema of graphs with fixed size: forbidden triangles and pentagons
• On the spectral Turán problem of theta graphs
• The signless Laplacian spectral radius of graphs with forbidding linear forests
• On the half-half case of the Zarankiewicz problem
• Degenerate Turán problems for hereditary properties
• The maximum spectral radius of graphs without friendship subgraphs
• A spectral condition for the existence of the square of a path
• scientific article; zbMATH DE number 622086 (Why is no real title available?)
• The signless Laplacian spectral radius of \(2K_3\)-free graphs
• scientific article; zbMATH DE number 1795865 (Why is no real title available?)
• A linear hypergraph extension of the bipartite Turán problem
• The high order spectral extremal results for graphs and their applications
• The spectral even cycle problem
• scientific article; zbMATH DE number 3311770 (Why is no real title available?)
• Adjacency eigenvalues of graphs without short odd cycles
• Forbidden theta graph, bounded spectral radius and size of non-bipartite graphs
• Spectral extremal graphs for disjoint cliques
• Spectral radius conditions for the existence of all subtrees of diameter at most four
• The spectral radius of graphs with no odd wheels
• On \(A_{\alpha}\) spectral extrema of graphs forbidding even cycles
• Spectral extrema of graphs: forbidden hexagon
• Spectral extremal results with forbidding linear forests
• The maximum spectral radius of \(\{C_3, C_5\}\)-free graphs of given size
• Continuous Tur\'an numbers
• Spectral extremal graphs without intersecting triangles as a minor
• The maximum spectral radius of wheel-free graphs
• Maxima of the \(Q\)-index: graphs with no \(K_{s,t}\)
• The signless Laplacian spectral radius of graphs with no intersecting triangles
• scientific article; zbMATH DE number 7764108 (Why is no real title available?)
• Three conjectures in extremal spectral graph theory
• The spectral Turán problem about graphs with no 6-cycle
• An \(A_\alpha\)-spectral Erdős-Pósa theorem
• Sharp bounds for the signless Laplacian spectral radius in terms of clique number
• Spectral extremal graphs for intersecting cliques
• Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size
• A unique characterization of spectral extrema for friendship graphs
• Spectral extrema of \(K_{s,t}\)-minor free graphs -- on a conjecture of M. Tait
• The maximum spectral radius of graphs without spanning linear forests
• Spectral extremal problem on disjoint color-critical graphs
• An \(A_{\alpha}\)-spectral Erdős-Sós theorem
• Forbidding multiple copies of forestable graphs
• A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs
• The Colin de Verdière parameter, excluded minors, and the spectral radius
• The spectral radius of graphs with no intersecting odd cycles
• Spectral analogues of Moon-Moser's theorem on Hamilton paths in bipartite graphs
• On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees
• A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs
• On the spectral moment of graphs with given clique number
• scientific article; zbMATH DE number 3267421 (Why is no real title available?)
• Spectral Turán problems for intersecting even cycles
• Some remarks on the Zarankiewicz problem

This page was built for publication: A contribution to the Zarankiewicz problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q846298)