On A Hypergraph Turán Problem Of Frankl
On A Hypergraph Turán Problem Of Frankl
复制标题
弗兰克尔超图图兰问题
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
B. Sudakov
中科院分区：
文献类型：
--
作者：
Peter Keevash;B. Sudakov
Let $$
C^{{{left( {2k}
ight)}}}_{r}
$$ be the 2k-uniform hypergraph obtained by letting P1, . . .,Pr be pairwise disjoint sets of size k and taking as edges all sets Pi∪Pj with i ≠ j. This can be thought of as the ‘k-expansion’ of the complete graph Kr: each vertex has been replaced with a set of size k. An example of a hypergraph with vertex set V that does not contain $$
C^{{{left( {2k}
ight)}}}_{3}
$$ can be obtained by partitioning V = V1 ∪V2 and taking as edges all sets of size 2k that intersect each of V1 and V2 in an odd number of elements. Let $$
{user1{mathcal{B}}}^{{{left( {2k}
ight)}}}_{n}
$$ denote a hypergraph on n vertices obtained by this construction that has as many edges as possible. For n sufficiently large we prove a conjecture of Frankl, which states that any hypergraph on n vertices that contains no $$
C^{{{left( {2k}
ight)}}}_{3}
$$ has at most as many edges as $$
{user1{mathcal{B}}}^{{{left( {2k}
ight)}}}_{n}
$$.Sidorenko has given an upper bound of $$
frac{{r - 2}}
{{r - 1}}
$$ for the Tur´an density of $$
C^{{{left( {2k}
ight)}}}_{r}
$$ for any r, and a construction establishing a matching lower bound when r is of the form 2p+1. In this paper we also show that when r=2p+1, any $$
C^{{{left( 4
ight)}}}_{r}
$$-free hypergraph of density $$
frac{{r - 2}}
{{r - 1}} - o{left( 1
ight)}
$$ looks approximately like Sidorenko’s construction. On the other hand, when r is not of this form, we show that corresponding constructions do not exist and improve the upper bound on the Turán density of $$
C^{{{left( 4
ight)}}}_{r}
$$ to $$
frac{{r - 2}}
{{r - 1}} - c{left( r
ight)}
$$, where c(r) is a constant depending only on r.The backbone of our arguments is a strategy of first proving approximate structure theorems, and then showing that any imperfections in the structure must lead to a suboptimal configuration. The tools for its realisation draw on extremal graph theory, linear algebra, the Kruskal–Katona theorem and properties of Krawtchouck polynomials.
Let $$
C^{{{left( {2k}
ight)}}}_{r}
$$ be the 2k-uniform hypergraph obtained by letting P1, . . .,Pr be pairwise disjoint sets of size k and taking as edges all sets Pi∪Pj with i ≠ j. This can be thought of as the ‘k-expansion’ of the complete graph Kr: each vertex has been replaced with a set of size k. An example of a hypergraph with vertex set V that does not contain $$
C^{{{left( {2k}
ight)}}}_{3}
$$ can be obtained by partitioning V = V1 ∪V2 and taking as edges all sets of size 2k that intersect each of V1 and V2 in an odd number of elements. Let $$
{user1{mathcal{B}}}^{{{left( {2k}
ight)}}}_{n}
$$ denote a hypergraph on n vertices obtained by this construction that has as many edges as possible. For n sufficiently large we prove a conjecture of Frankl, which states that any hypergraph on n vertices that contains no $$
C^{{{left( {2k}
ight)}}}_{3}
$$ has at most as many edges as $$
{user1{mathcal{B}}}^{{{left( {2k}
ight)}}}_{n}
$$.Sidorenko has given an upper bound of $$
frac{{r - 2}}
{{r - 1}}
$$ for the Tur´an density of $$
C^{{{left( {2k}
ight)}}}_{r}
$$ for any r, and a construction establishing a matching lower bound when r is of the form 2p+1. In this paper we also show that when r=2p+1, any $$
C^{{{left( 4
ight)}}}_{r}
$$-free hypergraph of density $$
frac{{r - 2}}
{{r - 1}} - o{left( 1
ight)}
$$ looks approximately like Sidorenko’s construction. On the other hand, when r is not of this form, we show that corresponding constructions do not exist and improve the upper bound on the Turán density of $$
C^{{{left( 4
ight)}}}_{r}
$$ to $$
frac{{r - 2}}
{{r - 1}} - c{left( r
ight)}
$$, where c(r) is a constant depending only on r.The backbone of our arguments is a strategy of first proving approximate structure theorems, and then showing that any imperfections in the structure must lead to a suboptimal configuration. The tools for its realisation draw on extremal graph theory, linear algebra, the Kruskal–Katona theorem and properties of Krawtchouck polynomials.