Turán number of bipartite graphs with no K_t,t

DOI10.1090/PROC/15042MaRDI QIDQ5111494zbMATH OpenOpenAlexFDO

Authors István Tomon, Benny Sudakov

Publication date 27 May 2020

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

extremal number of a graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30)

Abstract: The extremal number of a graph $H$, denoted by $mboxex(n,H)$, is the maximum number of edges in a graph on $n$ vertices that does not contain $H$. The celebrated KH{o}v'ari-S'os-Tur'an theorem says that for a complete bipartite graph with parts of size $tleqs$ the extremal number is $mboxex(K_{s,t})=O(n^{2-1/t})$. It is also known that this bound is sharp if $s>(t-1)!$. In this paper, we prove that if $H$ is a bipartite graph such that all vertices in one of its parts have degree at most $t$, but $H$ contains no copy of $K_{t,t}$, then $mboxex(n,H)=o(n^{2-1/t})$. This verifies a conjecture of Conlon, Janzer and Lee.

Recommendations

• Norm-graphs and bipartite Turán numbers
• New asymptotics for bipartite Turán numbers
• scientific article; zbMATH DE number 2197878
• Turán numbers of bipartite subdivisions
• 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">)<

Cites work

• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• Hypergraph based Berge hypergraphs
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Improved bounds for the extremal number of subdivisions
• Norm-graphs and bipartite Turán numbers
• Norm-graphs: Variations and applications
• On a Turán type problem of Erdős
• On a problem of K. Zarankiewicz
• On extremal problems of graphs and generalized graphs
• On the extremal number of subdivisions
• On the structure of linear graphs
• Problems and results in combinatorial analysis and graph theory
• Short proofs of some extremal results. II.
• The counting lemma for regular k‐uniform hypergraphs
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions

Cited in

(29)

• Some sharp lower bounds for the bipartite Turán number of theta graphs
• scientific article; zbMATH DE number 2197878 (Why is no real title available?)
• Topological minors in bipartite graphs
• The number of \(K_{s,t}\)-free graphs
• A counterexample to sparse removal
• Extremal graphs for the odd prism
• Regular Turán numbers of complete bipartite graphs
• Extremal graphs without exponentially small bicliques
• More on the extremal number of subdivisions
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
• Turán numbers of bipartite graphs plus an odd cycle
• 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">)</mml:mo></mml:mrow></mml:msub></mml:math>-free bipartite graphs
• Induced Turán numbers
• Bipartite Turán problems for ordered graphs
• Induced Turán problem in bipartite graphs
• The bipartite Turán number and spectral extremum for linear forests
• Turán numbers of bipartite subdivisions
• An ordered Turán problem for bipartite graphs
• Infinite Turán problems for bipartite graphs
• On color isomorphic subdivisions
• An extremal problem concerning graphs not containing \(K_t\) and \(K_{t,t}\)
• An extremal problem concerning graphs not containing \(K_t\) and \(K_{t,t,t}\)
• Turán number of an induced complete bipartite graph plus an odd cycle
• Turán number of the odd-ballooning of complete bipartite graphs
• New asymptotics for bipartite Turán numbers
• Turán numbers for \(K_{s,t}\)-free graphs: topological obstructions and algebraic constructions
• New bounds for a hypergraph bipartite Turán problem
• Finite Geometry and Extremal Graph Theory
• Spectral Turán problems for intersecting even cycles

This page was built for publication: Turán number of bipartite graphs with no \(K_{t,t}\)

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