TY  - JOUR
ID  - Polcyn2017
LB  - Polcyn2017
AU  - Polcyn, Joanna
AU  - Ruciński, Andrzej
TI  - A hierarchy of maximal intersecting triple systems
ST  - A hierarchy of maximal intersecting triple systems
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2017
VL  - 37
IS  - 4
SP  - 597
EP  - 608
DO  - http://dx.doi.org/10.7494/OpMath.2017.37.4.597
UR  - http://dx.doi.org/10.7494/OpMath.2017.37.4.597
AB  - 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.
KW  - maximal intersecting family
KW  - 3-uniform hypergraph
KW  - triple system
SN  - 1232-9274
ER  -