On the rational Turán exponents conjecture

DOI10.1016/J.JCTB.2020.12.003zbMATH Open1459.05133arXiv1811.06916OpenAlexW3120870204MaRDI QIDQ1998761FDOQ1998761

Authors: Dong Yeap Kang, Jaehoon Kim, Hong Liu 

Publication date: 8 March 2021

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: The extremal number $mathrmex(n,F)$ of a graph $F$ is the maximum number of edges in an $n$-vertex graph not containing $F$ as a subgraph. A real number $rin[1,2]$ is realisable if there exists a graph $F$ with $mathrmex(n,F)=Theta(n^r)$. Several decades ago, ErdH{o}s and Simonovits conjectured that every rational number in $[1,2]$ is realisable. Despite decades of effort, the only known realisable numbers are $0,1,frac75,2$, and the numbers of the form $1+frac1m$, $2-frac1m$, $2-frac2m$ for integers $mgeq1$. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers $1$ and $2$. In this paper, we make progress on the conjecture of ErdH{o}s and Simonovits. First, we show that $2-fracab$ is realisable for any integers $a,bgeq1$ with $b>a$ and $bequivpm1(mmod:a)$. This includes all previously known ones, and gives infinitely many limit points $2-frac1m$ in the set of all realisable numbers as a consequence. Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable.

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

Recommendations

• On a Turán Conjecture and random multiplicative functions
• Rational exponents for hypergraph Turan problems
• scientific article; zbMATH DE number 714715
• The Erdős-Turán conjecture in the positive rational numbers
• On a conjecture on exponential Diophantine equations
• TERAI'S CONJECTURE ON EXPONENTIAL DIOPHANTINE EQUATIONS
• The Riemann Hypothesis and the Turan Inequalities
• Many Turán exponents via subdivisions
• A conjecture on the Łojasiewicz exponent
• scientific article; zbMATH DE number 4045750

zbMATH Keywords

extremal numberTurán 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
• Norm-graphs: Variations and applications
• Problems and results in combinatorial analysis and graph theory
• Dependent random choice
• On a class of degenerate extremal graph problems
• Turán numbers of theta graphs
• All rationals occur as exponents
• The Extremal Number of the Subdivisions of the Complete Bipartite Graph
• Title not available (Why is that?)
• Rational exponents for hypergraph Turan problems
• Rational exponents in extremal graph theory
• Graphs without theta subgraphs
• Graphs with few paths of prescribed length between any two vertices
• Random algebraic construction of extremal graphs
• Improved bounds for the extremal number of subdivisions
• Turán Numbers of Bipartite Subdivisions

Cited In (10)

• On Turán exponents of bipartite graphs
• Random polynomial graphs for random Turán problems
• On color isomorphic subdivisions
• More on the extremal number of subdivisions
• On the Turán Number of the Blow-Up of the Hexagon
• Rational exponents for hypergraph Turan problems
• Rational exponents in extremal graph theory
• The Extremal Number of the Subdivisions of the Complete Bipartite Graph
• Many Turán exponents via subdivisions
• Some remarks on the Zarankiewicz problem

This page was built for publication: On the rational Turán exponents conjecture

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