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)

1. M. Całczyńska-Karłowicz, Theorem on families of finite sets, Bull. Acad. Pol. Sci., Ser. Sci Math. Astron. Phys. 12 (1964), 87-89.
2. R. Csákány, J. Kahn, A homological Approach to Two Problems on Finite Sets, J. Algebraic Combin. 9 (1999), 141-149.
3. P. Erdös, C. Ko, R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. 12 (1961) 2, 313-320.
4. P. Frankl, Z. Füredi, Non-trivial intersecting families, J. Combin. Theory Ser. A 41 (1986), 150-153.
5. P. Frankl, Z. Füredi, Exact solution of some Turán-type problems, J. Combin. Theory Ser. A 45 (1987), 226-262.
6. J. Han, Y. Kohayakawa, Maximum size of a non-trivial intersecting uniform family which is not a subfamily of the Hilton-Milner family, Proc. Amer. Math. Soc. 145 (2017) 1, 73-87.
7. M.A. Henning, A. Yeo, Transversals and matchings in 3-unoform hypergraphs, Europ. J. Combin. 34 (2013), 217-228.
8. A.J.W. Hilton, E.C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. 18 (1967) 2, 369-384.
9. E. Jackowska, J. Polcyn, A. Ruciński, Multicolor Ramsey numbers and restricted Turán numbers for the loose 3-uniform path of length three, submitted.
10. A. Kostochka, D. Mubayi, The structure of large intersecting families, Proc. Amer. Math. Soc., to appear.
11. Zs. Tuza, Critical hypergraphs and intersecting set-pair systems, J. Combin. Theory Ser. B 39 (1985), 134-145.
• Joanna Polcyn
• Adam Mickiewicz University, Faculty of Mathematics and Computer Science, Department of Discrete Mathematics, Umultowska 87, 61-614 Poznań, Poland
• Andrzej Ruciński
• Adam Mickiewicz University, Faculty of Mathematics and Computer Science, Department of Discrete Mathematics, Umultowska 87, 61-614 Poznań, Poland
• Communicated by Dalibor Fronček.
• Revised: 2016-12-12.
• Accepted: 2016-12-13.
• Published online: 2017-04-28.