论文标题
树木超图炸弹的极端问题
Extremal problems for hypergraph blowups of trees
论文作者
论文摘要
在本文中，我们提出了一种极端集理论中的新方法，可以将其视为Katona置换方法的不对称版本。我们使用它来在erdős-ko-rado系列中找到更多的Turán数量。 a $（a，b）$ - 路径$ p $长度$ 2K-1 $由$ 2K-1 $ seet s s s y $ r = a+b $，如下所示。 Take $k$ pairwise disjoint $a$-element sets $A_0, A_2, \dots, A_{2k-2}$ and other $k$ pairwise disjoint $b$-element sets $B_1, B_3, \dots, B_{2k-1}$ and order them linearly as $A_0, B_1, A_2, B_3, A_4\dots$.将$ p_ {2k-1}（a，b）$的（hyper）边缘定义为表格$ a_i \ cup b_ {i+1} $和$ b_j \ cup a_ {j+1} $的集合。 $ p $的成员可以表示为$ r $ emlement间隔，$ ak+bk $ element seet集。 我们的主要结果是关于树木爆炸的超图，这意味着对于固定的$ k，a，b $，as $ n \ to \ to \ infty $ \ [{\ rm ex} _r（n，p_ {2k -1}（a，a，b）） 这概括了ERDőS-gallai定理用于图$ a = b = 1 $的情况。当$ a+b $均匀时，我们还确定了渐近学；其余案例仍然开放。
In this paper we present a novel approach in extremal set theory which may be viewed as an asymmetric version of Katona's permutation method. We use it to find more Turán numbers of hypergraphs in the Erdős--Ko--Rado range. An $(a,b)$-path $P$ of length $2k-1$ consists of $2k-1$ sets of size $r=a+b$ as follows. Take $k$ pairwise disjoint $a$-element sets $A_0, A_2, \dots, A_{2k-2}$ and other $k$ pairwise disjoint $b$-element sets $B_1, B_3, \dots, B_{2k-1}$ and order them linearly as $A_0, B_1, A_2, B_3, A_4\dots$. Define the (hyper)edges of $P_{2k-1}(a,b)$ as the sets of the form $A_i\cup B_{i+1}$ and $B_j\cup A_{j+1}$. The members of $P$ can be represented as $r$-element intervals of the $ak+bk$ element underlying set. Our main result is about hypergraphs that are blowups of trees, and implies that for fixed $k,a,b$, as $n\to \infty$ \[ {\rm ex}_r(n,P_{2k-1}(a,b)) = (k - 1){n \choose r - 1} + o(n^{r - 1}).\] This generalizes the Erdős--Gallai theorem for graphs which is the case of $a=b=1$. We also determine the asymptotics when $a+b$ is even; the remaining cases are still open.
