论文标题
伪图中的Turán问题
Turán problems in pseudorandom graphs
论文作者
论文摘要
给定图形$ f $，我们考虑确定不包含$ f $副本的最密集的假轴图的问题。我们提供了一个嵌入过程，该过程改善了Conlon，Fox和Zhao的总体结果，该过程在密度上给出了上限。特别是，我们的结果意味着，密度大于$ n^{ - 1/3} $的最佳伪随机图必须包含彼得森图的副本，而先前的最佳结果给出了绑定的$ n^{ - 1/4} $。此外，我们猜想指数$ 1/3 $我们的界限很紧。我们还构建了最密集的已知pseudorandom $ k_ {2,3} $ - 也不三角形的免费图。最后，我们以一种新颖的方式获得了由于Bishnoi，Ihringer和Pepe而获得的最密集的已知伪数图，并给出了不同的证据，证明它们没有大集团。
Given a graph $F$, we consider the problem of determining the densest possible pseudorandom graph that contains no copy of $F$. We provide an embedding procedure that improves a general result of Conlon, Fox, and Zhao which gives an upper bound on the density. In particular, our result implies that optimally pseudorandom graphs with density greater than $n^{-1/3}$ must contain a copy of the Peterson graph, while the previous best result gives the bound $n^{-1/4}$. Moreover, we conjecture that the exponent $1/3$ in our bound is tight. We also construct the densest known pseudorandom $K_{2,3}$-free graphs that are also triangle-free. Finally, we obtain the densest known construction of clique-free pseudorandom graphs due to Bishnoi, Ihringer and Pepe in a novel way and give a different proof that they have no large clique.
