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.
- 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.
- R. Csákány, J. Kahn, A homological Approach to Two Problems on Finite Sets, J. Algebraic Combin. 9 (1999), 141-149.
- P. Erdös, C. Ko, R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. 12 (1961) 2, 313-320.
- P. Frankl, Z. Füredi, Non-trivial intersecting families, J. Combin. Theory Ser. A 41 (1986), 150-153.
- P. Frankl, Z. Füredi, Exact solution of some Turán-type problems, J. Combin. Theory Ser. A 45 (1987), 226-262.
- 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.
- M.A. Henning, A. Yeo, Transversals and matchings in 3-unoform hypergraphs, Europ. J. Combin. 34 (2013), 217-228.
- 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.
- 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.
- A. Kostochka, D. Mubayi, The structure of large intersecting families, Proc. Amer. Math. Soc., to appear.
- 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.
- Received: 2016-08-22.
- Revised: 2016-12-12.
- Accepted: 2016-12-13.
- Published online: 2017-04-28.
