2017/01/01 by Joanna Polcyn, Andrzej Ruciński · 1 citation
Mathematics · Engineering · Computer Science · #Limits and Structures in Graph Theory #graph theory and CDMA systems #Advanced Graph Theory Research #Combinatorics #Disjoint sets #Triple system #Mathematical proof #Mathematics #Hierarchy #Pigeonhole principle #Pairwise comparison #Discrete mathematics #Geometry
paper · pdf · doi:10.7494/opmath.2017.37.4.597
openalex publication_date 2017/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
We reach beyond the celebrated theorems of Erds-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 Turn numbers ex (s) (n; M 3 2 ), s 1, where M 3 2 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 max10, 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.