论文标题
多色Turán数字II- ruzsa-szemerédi定理的概括以及集团和奇数的新结果
Multicolor Turán numbers II -- a generalization of the Ruzsa-Szemerédi theorem and new results on cliques and odd cycles
论文作者
论文摘要
在本文中，我们继续研究Turán禁止的子图问题和Ruzsa-Szemerédi问题的自然概括。令$ ex_f（n，g）$表示可以放置在$ n $ vertex接地套件上的固定简单图$ f $的最大边缘 - 迪斯连接副本，而不会形成来自不同$ f $ copies的子graph $ g $。当$ f $和$ g $都是三角形的情况下，本质上将Ruzsa和Szemerédi的定理还给您。当$ f $和$ g $是任意集团时，我们将其结果扩展到了案例，这是由于ERDőS，Frankl和Rödl所致的数字理论结果。此延伸反过来决定了大型图对家庭的数量级，这将是次级的，但几乎是二次。 Since the linear $r$-uniform hypergraph Turán problems to determine $ex_r^{lin}(n,G)$ form a class of the multicolor Turán problem, following the identity $ex_r^{lin}(n,G)=ex_{K_r}(n,G)$, our results determine the linear hypergraph Turán numbers of every graph of girth $3$ and for every $r$ up to a子聚集因子。此外，当$ g $是三角形时，我们解决案例$ f = c_5 $，并为情况提供界限$ f = c_ {2k+1} $，$ k \ ge 3 $。
In this paper we continue the study of a natural generalization of Turán's forbidden subgraph problem and the Ruzsa-Szemerédi problem. Let $ex_F(n,G)$ denote the maximum number of edge-disjoint copies of a fixed simple graph $F$ that can be placed on an $n$-vertex ground set without forming a subgraph $G$ whose edges are from different $F$-copies. The case when both $F$ and $G$ are triangles essentially gives back the theorem of Ruzsa and Szemerédi. We extend their results to the case when $F$ and $G$ are arbitrary cliques by applying a number theoretic result due to Erdős, Frankl and Rödl. This extension in turn decides the order of magnitude for a large family of graph pairs, which will be subquadratic, but almost quadratic. Since the linear $r$-uniform hypergraph Turán problems to determine $ex_r^{lin}(n,G)$ form a class of the multicolor Turán problem, following the identity $ex_r^{lin}(n,G)=ex_{K_r}(n,G)$, our results determine the linear hypergraph Turán numbers of every graph of girth $3$ and for every $r$ up to a subpolynomial factor. Furthermore, when $G$ is a triangle, we settle the case $F=C_5$ and give bounds for the cases $F=C_{2k+1}$, $k\ge 3$ as well.
