A hierarchy of maximal intersecting triple systems

• Autorzy: Polcyn J. , Ruciński A.

Identyfikatory

DOI

10.7494/OpMath.2017.37.4.597

• Języki publikacji: EN

Abstrakty

EN

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 ≥ 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 Turan numbers [formula], s ≥ 1, where [formula] 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 C3 is defined as C3 = {{x1,y3,x2}, {x1,y2,x3}, {x2, y1,x3}}. Along the way we show that the largest intersecting triple system H on n ≥ 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.

Słowa kluczowe

EN

maximal intersecting family; 3-uniform hypergraph; triple system

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2017
• Tom: Vol. 37, no. 4
• Strony: 597--608
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Polcyn J.

• Adam Mickiewicz University Faculty of Mathematics and Computer Science Department of Discrete Mathematics Umultowska 87, 61-614 Poznań, Poland

autor

Ruciński A.

• Adam Mickiewicz University Faculty of Mathematics and Computer Science Department of Discrete Mathematics Umultowska 87, 61-614 Poznań, Poland

Bibliografia

• [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. Csakany, 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. Franki, Z. Furedi, Non-trivial intersecting families, J. Combin. Theory Ser. A 41 (1986), 150-153.
• [5] P. Franki, Z. Furedi, Exact solution of some Turdn-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, (6—o I.
• [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 Turdn 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.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).