| Abstrakt: |
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 exF(n,G) ${\text{ex}}_{F}(n,G)$ denote the maximum number of edge‐disjoint copies of a fixed simple graph F $F$ that can be placed on an n $n$‐vertex ground set without forming a subgraph G $G$ whose edges are from different F $F$‐copies. The case when both F $F$ and G $G$ are triangles essentially gives back the theorem of Ruzsa and Szemerédi. We extend their results to the case when F $F$ and G $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 $r$‐uniform hypergraph Turán problems to determine exrlin(n,G) ${\text{ex}}_{r}^{lin}(n,G)$ form a class of the multicolor Turán problem, following the identity exrlin(n,G)=exKr(n,G) ${\text{ex}}_{r}^{lin}(n,G)={\text{ex}}_{{K}_{r}}(n,G)$, our results determine the linear hypergraph Turán numbers of every graph of girth 3 and for every r $r$ up to a subpolynomial factor. Furthermore, when G $G$ is a triangle, we settle the case F=C5 $F={C}_{5}$ and give bounds for the cases F=C2k+1 $F={C}_{2k+1}$, k≥3 $k\ge 3$ as well. [ABSTRACT FROM AUTHOR] |
Plný text