Improved Bounds Concerning the Maximum Degree of Intersecting Hypergraphs

For positive integers n>k>t let nk denote the collection of all k-subsets of the standard n-element set n=\1, , n\. Subsets of nk are called k-graphs. A k-graph F is called t-intersecting if |F F'| t for all F, F' F. One of the central results of extremal set theory is the Erdős-Ko-Rado Theorem which states that for n (k-t+1) (t+1) no t-intersecting k-graph has more than n-tk-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 F (i) =\F \{i\ i F F\}. The quantity (F) =₁ ₈ ₍|F (i) |/|F| measures how close a k-graph is to a star. The main result (Theorem 1. 3) shows that (F) >1/d holds if F is 1-intersecting, |F|>2ᵈd^2d+1n-d-1k-d-1 and n 4 (d-1) dk. Such a statement can be deduced from earlier results, 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 a nearly optimal bound in the case of t 2 (Theorem 1. 4).