The Turán number of blow-ups of trees
The Turán number of blow-ups of trees
复制标题
树木爆炸的图兰数
DOI：
10.1016/j.jctb.2022.05.004
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Zolt'an L'or'ant Nagy
中科院分区：
文献类型：
--
作者：
Andrzej Grzesik;Oliver Janzer;Zolt'an L'or'ant Nagy
őS 1967年提出的一个猜想断言：任何不包含固定r-退化二部图F的n个顶点上的图至多有Cn2条−1/r条边，其中C是一个仅依赖于F的常数.我们证明了这个界对一大类r-退化二部图成立，包括树的所有r-退化爆破.我们的结果推广了许多已被证明的ERDőS猜想的情形，包括Füredi和Alon，Krivelevich和sudakov的相关结果。我们的证明使用了辅助图上的过饱和和随机游动。
A conjecture of Erdős from 1967 asserts that any graph on n vertices which does not contain a fixed r-degenerate bipartite graph F has at most C n 2− 1/r edges, where C is a constant depending only on F. We show that this bound holds for a large family of r-degenerate bipartite graphs, including all r-degenerate blow-ups of trees. Our results generalise many previously proven cases of the Erdős conjecture, including the related results of Füredi and Alon, Krivelevich and Sudakov. Our proof uses supersaturation and a random walk on an auxiliary graph.