2016/08/22 by Joanna Polcyn, Polcyn, Joanna, Andrzej Rucinski +1 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1608.06114
arxiv created 2016/08/22 · arxiv updated 2016/08/23
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 Turán numbers \ex(s)(n, M23), s≥1, where M23 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.