Opuscula Math. 37, no. 4 (2017), 597-608
http://dx.doi.org/10.7494/OpMath.2017.37.4.597

Opuscula Mathematica

# A hierarchy of maximal intersecting triple systems

Joanna Polcyn
Andrzej Ruciński

Abstract. We reach beyond the celebrated theorems of Erdȍs-Ko-Rado and Hilton-Milner, and a recent theorem of Han-Kohayakawa, and determine all maximal intersecting triples systems. It turns out that for each $$n\geq 7$$ there are exactly 15 pairwise non-isomorphic such systems (and 13 for $$n=6$$). We present our result in terms of a hierarchy of Turán numbers $$\operatorname{ex}^{(s)}(n; M_2^{3})$$, $$s\geq 1$$, where $$M_2^{3}$$ is a pair of disjoint triples. Moreover, owing to our unified approach, we provide short proofs of the above mentioned results (for triple systems only). The triangle $$C_3$$ is defined as $$C_3=\{\{x_1,y_3,x_2\},\{x_1,y_2,x_3\},\{x_2,y_1,x_3\}\}$$. Along the way we show that the largest intersecting triple system $$H$$ on $$n\geq 6$$ vertices, which is not a star and is triangle-free, consists of $$\max\{10,n\}$$ triples. This facilitates our main proof's philosophy which is to assume that $$H$$ contains a copy of the triangle and analyze how the remaining edges of $$H$$ intersect that copy.

Keywords: maximal intersecting family, 3-uniform hypergraph, triple system.

Mathematics Subject Classification: 05D05, 05C65.

Full text (pdf)