On the rational Turán exponents conjecture
On the rational Turán exponents conjecture
复制标题
关于有理图兰指数猜想
DOI：
10.1016/j.jctb.2020.12.003
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Kang D
中科院分区：
文献类型：
--
作者：
Kang D
图F的极值数ex（n，F）是指不含F的n-顶点图的最大边数。如果存在图F，且ex（n，F）= Θ（nr），则真实的数r∈[1，2]是可实现的.几十年前，Erdens和Simonovits证明了[1，2]中的每一个有理数都是可实现的。经过几十年的努力，已知的可实现的数只有0、1、7、5、2，以及1+ 1 m、2− 1 m、2− 2 m（m≥ 1）。特别是，我们甚至不知道所有可实现数的集合是否包含除了1和2之外的唯一极限点。本文对Erdés和Simonovits猜想作了进一步的改进。首先，我们证明了2− a B对任意整数a，B≥ 1是可实现的，其中B> a且B ≥ ±1（mod a）。这包括了所有先前已知的数，并由此在所有可实现数的集合中给出了无穷多个极限点2− 1 m。其次，我们提出了一个关于二部图的剖分的猜想。除了有趣的本身，我们表明，有点令人惊讶的是，这种细分猜想实际上意味着，1和2之间的每一个有理数是可实现的。
The extremal number ex (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 r∈[1, 2] is realisable if there exists a graph F with ex (n, F)= Θ (n r). Several decades ago, Erdő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, 7 5, 2, and the numbers of the form 1+ 1 m, 2− 1 m, 2− 2 m for integers m≥ 1. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than the two numbers 1 and 2. In this paper, we make progress on the conjecture of Erdős and Simonovits. First, we show that 2− a b is realisable for any integers a, b≥ 1 with b> a and b≡±1 (mod a). This includes all previously known ones, and gives infinitely many limit points 2− 1 m 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.
登录
查看更多内容
影响因子：
0.8
作者：
Janzer O
通讯作者：
Janzer O
所有有理数均以指数形式出现
DOI：
10.1016/0097-3165(86)90090-7
发表时间：
1986
期刊：
J. Comb. Theory A
影响因子：
--
作者：
P. Frankl
通讯作者：
P. Frankl
DOI：
10.1016/j.jctb.2018.05.003
发表时间：
2019-01
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Jacques Verstraëte;Jason S. Williford
通讯作者：
Jacques Verstraëte;Jason S. Williford
许多图兰指数通过细分
DOI：
--
发表时间：
2019
期刊：
Combinatorics, probability & computing
影响因子：
--
作者：
T. Jiang;Y. Qiu
通讯作者：
Y. Qiu
影响因子：
0.8
作者：
Jiang, Tao;Qiu, Yu
通讯作者：
Qiu, Yu