Problems and results on 1-cross intersecting set pair systems

2019/11/08 by Zoltán Füredi, Füredi, Zoltán, András Gyárfás +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1911.03067

openalex publication_date 2019/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The notion of cross intersecting set pair system of size m, (\A_i\_i=1^m, \B_i\_i=1^m) with A_i∩ B_i=∅ and A_i∩ B_j≠∅, was introduced by Bollobás and it became an important tool of extremal combinatorics. His classical result states that m≤ a+b\choose a if |A_i|≤ a and |B_i|≤ b for each i. Our central problem is to see how this bound changes with the additional condition |A_i∩ B_j|=1 for i≠ j. Such a system is called 1-cross intersecting. We show that the maximum size of a 1-cross intersecting set pair system is -- at least 5^n/2 for n even, a=b=n, -- equal to (\lfloor(n)/(2)\rfloor+1)(\lceil(n)/(2)\rceil+1) if a=2 and b=n≥ 4, -- at most |∪_i=1^m A_i|, -- asymptotically n² if \A_i\ is a linear hypergraph (|A_i∩ A_j|≤ 1 for i≠ j), -- asymptotically 1\over 2n² if \A_i\ and \B_i\ are both linear hypergraphs.

Related

• On sizes of 1-cross intersecting set pair systems
• A bound for 1-cross intersecting set pair systems
• Counting intersecting and pairs of cross-intersecting families
• Union-intersecting set systems
• Disjoint pairs in set systems with restricted intersection