More on the extremal number of subdivisions

DOI10.1007/S00493-020-4202-1zbMATH Open1488.05263arXiv1903.10631OpenAlexW2924365128MaRDI QIDQ2236656FDOQ2236656

Authors: David Conlo, Oliver Janzer, Joonkyung Lee 

Publication date: 25 October 2021

Published in: Combinatorica (Search for Journal in Brave)

Abstract: Given a graph $H$, the extremal number $mathrmex(n,H)$ is the largest number of edges in an $H$-free graph on $n$ vertices. We make progress on a number of conjectures about the extremal number of bipartite graphs. First, writing $K{\text{'}}_{s,t}$ for the subdivision of the bipartite graph $K_{s,t}$, we show that $mathrmex(n,K{\text{'}}_{s,t})=O(n^{3/2-frac12s})$. This proves a conjecture of Kang, Kim and Liu and is tight up to the implied constant for $t$ sufficiently large in terms of $s$. Second, for any integers $s,kgeq1$, we show that $mathrmex(n,L)=Theta(n^{1+fracssk+1})$ for a particular graph $L$ depending on $s$ and $k$, answering another question of Kang, Kim and Liu. This result touches upon an old conjecture of ErdH{o}s and Simonovits, which asserts that every rational number $rin(1,2)$ is realisable in the sense that $mathrmex(n,H)=Theta(n^r)$ for some appropriate graph $H$, giving infinitely many new realisable exponents and implying that $1+1/k$ is a limit point of realisable exponents for all $kgeq1$. Writing $H^k$ for the $k$-subdivision of a graph $H$, this result also implies that for any bipartite graph $H$ and any $k$, there exists $delta>0$ such that $mathrmex(n,H^{k-1})=O(n^{1+1/k-delta})$, partially resolving a question of Conlon and Lee. Third, extending a recent result of Conlon and Lee, we show that any bipartite graph $H$ with maximum degree $r$ on one side which does not contain $C_4$ as a subgraph satisfies $mathrmex(n,H)=o(n^{2-1/r})$.

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

Recommendations

• The extremal number of the subdivisions of the complete bipartite graph
• Improved bounds for the extremal number of subdivisions
• The extremal number of longer subdivisions
• On the extremal number of subdivisions
• Turán number of bipartite graphs with no \(K_{t,t}\)

zbMATH Keywords

bipartite graphssubdivisionextremal numbers

Mathematics Subject Classification ID

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

Cites Work

• The History of Degenerate (Bipartite) Extremal Graph Problems
• Title not available (Why is that?)
• On the structure of linear graphs
• On the combinatorial problems which I would most like to see solved
• Norm-graphs and bipartite Turán numbers
• On a problem of K. Zarankiewicz
• Weak hypergraph regularity and linear hypergraphs
• Norm-graphs: Variations and applications
• Small topological complete subgraphs of ``dense graphs
• Dependent random choice
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
• Compact topological minors in graphs
• On a class of degenerate extremal graph problems
• On a Turán type problem of Erdős
• Title not available (Why is that?)
• Rational exponents in extremal graph theory
• On the rational Turán exponents conjecture
• Graphs without theta subgraphs
• Graphs with few paths of prescribed length between any two vertices
• Improved bounds for the extremal number of subdivisions
• Turán Numbers of Subdivided Graphs

Cited In (21)

• Maximum bipartite subgraphs in $H$-free graphs
• Random polynomial graphs for random Turán problems
• On color isomorphic subdivisions
• The spectral radius of graphs with no intersecting odd cycles
• Extremal connectivity for topological cliques in bipartite graphs
• Improved bounds for the extremal number of subdivisions
• Dense induced bipartite subgraphs in triangle-free graphs
• Tree-Degenerate Graphs and Nested Dependent Random Choice
• The fine structure of octahedron-free graphs
• Splits with forbidden subgraphs
• Spectral Turán problems for intersecting even cycles
• Extremal graphs for the odd prism
• On the Turán number of the hypercube
• The asymptotics of \(r(4,t)\)
• Color Isomorphic Even Cycles and a Related Ramsey Problem
• Induced Turán problem in bipartite graphs
• The extremal number of longer subdivisions
• A polynomial resultant approach to algebraic constructions of extremal graphs
• Many Turán exponents via subdivisions
• Some remarks on the Zarankiewicz problem
• Repeated Patterns in Proper Colorings

This page was built for publication: More on the extremal number of subdivisions

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