Acta Mathematica Hungarica Математика (общая)
Concise proofs concerning the size and structure of large intersecting $$k$$-graphs
Аннотация
Abstract Let $$n > 2k \geq 4$$ n > 2 k ≥ 4 and let $$\mathcal F \subset {[n]\choose k}$$ F ⊂ [ n ] k be an intersecting $$k$$ k -graph on $$n$$ n vertices, that is, $$F\cap F' \neq \emptyset$$ F ∩ F ′ ≠ ∅ for all $$F, F' \in \mathcal F$$ F , F ′ ∈ F . By the Erd\H{o}s--Ko--Rado Theorem $$|\mathcal F| \leq { n - 1\choose k - 1}$$ | F | ≤ n - 1 k - 1 with equality holding only for the full-star, $$\mathcal S_x$$ S x , the family of all $$k$$ k -sets containing the vertex $$x$$ x . If we exclude stars, that is, subfamilies of $$\mathcal S_x$$ S x then $$|\mathcal F| \leq { n - 1\choose k - 1} - { n - k - 1\choose k - 1} + 1$$ | F | ≤ n - 1 k - 1 - n - k - 1 k - 1 + 1 was proved by Hilton and Milner who determined the families attaining equality as well. Half a century later Han and Kohayakawa determined the next largest families. Then very recently Huang and Peng determined the fourth largest families. That is, they determined the largest families assuming that $$\mathcal F$$ F is not a star and it is not contained neither in the Hilton--Milner families nor in the Han--Kohayakawa families. In the present paper we provide a unified simple proof for these two theorems as well as solve the corresponding problem for $$t $$ t -intersecting families $$(|F \cap F'| \geq t)$$ ( | F ∩ F ′ | ≥ t ) albeit only for $$n > t + \max \{4t(k - t + 1)^2, 2(t + 1)^2\}$$ n > t + max { 4 t ( k - t + 1 ) 2 , 2 ( t + 1 ) 2 } .