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

DOI10.1090/PROC/15042zbMATH Open1440.05129arXiv1910.11048OpenAlexW3006674765MaRDI QIDQ5111494FDOQ5111494

Authors: István Tomon, Benny Sudakov 

Publication date: 27 May 2020

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

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.

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

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">)<

zbMATH Keywords

extremal number of a graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (16)

• On color isomorphic subdivisions
• An extremal problem concerning graphs not containing \(K_t\) and \(K_{t,t,t}\)
• Regular Turán numbers of complete bipartite graphs
• Turán numbers of bipartite graphs plus an odd cycle
• Title not available (Why is that?)
• Bipartite Turán problems for ordered graphs
• Spectral Turán problems for intersecting even cycles
• New asymptotics for bipartite Turán numbers
• Extremal graphs for the odd prism
• The bipartite Turán number and spectral extremum for linear forests
• The number of \(K_{s,t}\)-free graphs
• Induced Turán problem in bipartite graphs
• Topological minors in bipartite graphs
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
• 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
• An extremal problem concerning graphs not containing \(K_t\) and \(K_{t,t}\)

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)