Problems and results on 1-cross intersecting set pair systems

Füredi, Zoltán and Gyárfás, András and Király, Zoltán (2023) Problems and results on 1-cross intersecting set pair systems. COMBINATORICS PROBABILITY AND COMPUTING. ISSN 0963-5483

Preview

Text 1911.03067v2.pdf Download (197kB) | Preview

Abstract

The notion of cross intersecting set pair system of size m, ({Ai}mi=1,{Bi}mi=1) with Ai∩Bi=∅ and Ai∩Bj≠∅, was introduced by Bollobás and it became an important tool of extremal combinatorics. His classical result states that m≤(a+ba) if |Ai|≤a and |Bi|≤b for each i. Our central problem is to see how this bound changes with the additional condition |Ai∩Bj|=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 5n/2 for n even, a=b=n, -- equal to (⌊n2⌋+1)(⌈n2⌉+1) if a=2 and b=n≥4, -- at most |∪mi=1Ai|, -- asymptotically n2 if {Ai} is a linear hypergraph (|Ai∩Aj|≤1 for i≠j), -- asymptotically 12n2 if {Ai} and {Bi} are both linear hypergraphs.

Actions (login required)

Edit Item