论文标题
提高了有关相交超图的最大程度的界限
Improved bounds concerning the maximum degree of intersecting hypergraphs
论文作者
论文摘要
对于正整数，$ n> k> t $ let $ \ binom {[n]} {k} $表示标准$ n $ - element set $ [n] = \ {1，\ ldots的所有$ k $ -subsets的集合。 $ \ binom {[n]} {k} $的子集称为$ k $ -graphs。 A $ K $ -GRAPH $ \ MATHCAL {f} $如果$ | f \ cap f'| \ geq t $ for All $ f，f'\ in \ Mathcal {f} $，则称为$ t $ - 缩放。极端集理论的主要结果之一是ERDőS-KO-RADO定理，该定理指出，对于$ n \ geq（k-t+1）（t+1）（t+1）$ no $ t $ -t $ - 缩放$ k $ -graph具有超过$ \ binom {n-t-t} {k-t} {k-t} $ EDGES。对于$ n $，比此阈值大的$ t $ - 标准（所有$ k $ - 包含固定的$ t $ set）是唯一获得此界限的家庭。定义$ \ MATHCAL {f}（i）= \ {f \ setMinus \ {i \} \ colon i \ in f \ in \ Mathcal {f} \} $。数量$ \ varrho（\ mathcal {f}）= \ max \ limits_ {1 \ leq i \ leq n} | \ mathcal {f}（i）|/| \ m马理{f} | $测量$ k $ - $ k $ - graph at a star a a $ a $ k $。主要结果（定理1.5）表明，如果$ \ varrho（\ Mathcal {f}）> 1/d $保持，则如果$ \ \ \ \ m rathcal {f} $是1 interting，$ | \ mathcal {f} 4（d-1）dk $。可以从\ cite {f78-2}和\ cite {df}的结果中得出这样的语句，但是仅以$ n/k $和/或$ n $的更大值。证明是纯粹的组合，它基于一种新方法：转移广告极端。在$ t \ geq 2 $（定理1.11）以及许多相关结果的情况下，使用相同的方法来获得一些几乎最佳的边界。
For positive integers $n>k>t$ let $\binom{[n]}{k}$ denote the collection of all $k$-subsets of the standard $n$-element set $[n]=\{1,\ldots,n\}$. Subsets of $\binom{[n]}{k}$ are called $k$-graphs. A $k$-graph $\mathcal{F}$ is called $t$-intersecting if $|F\cap F'|\geq t$ for all $F,F'\in \mathcal{F}$. One of the central results of extremal set theory is the Erdős-Ko-Rado Theorem which states that for $n\geq (k-t+1)(t+1)$ no $t$-intersecting $k$-graph has more than $\binom{n-t}{k-t}$ edges. For $n$ greater than this threshold the $t$-star (all $k$-sets containing a fixed $t$-set) is the only family attaining this bound. Define $\mathcal{F}(i)=\{F\setminus \{i\}\colon i\in F\in \mathcal{F}\}$. The quantity $\varrho(\mathcal{F})=\max\limits_{1\leq i\leq n}|\mathcal{F}(i)|/|\mathcal{F}|$ measures how close a $k$-graph is to a star. The main result (Theorem 1.5) shows that $\varrho(\mathcal{F})>1/d$ holds if $\mathcal{F}$ is 1-intersecting, $|\mathcal{F}|>2^dd^{2d+1}\binom{n-d-1}{k-d-1}$ and $n\geq 4(d-1)dk$. Such a statement can be deduced from the results of \cite{F78-2} and \cite{DF}, however only for much larger values of $n/k$ and/or $n$. The proof is purely combinatorial, it is based on a new method: shifting ad extremis. The same method is applied to obtain some nearly optimal bounds in the case of $t\geq 2$ (Theorem 1.11) along with a number of related results.
