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
|
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.
Item Type: | Article |
---|---|
Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 24 Mar 2023 12:44 |
Last Modified: | 24 Mar 2023 12:44 |
URI: | http://real.mtak.hu/id/eprint/162688 |
Actions (login required)
![]() |
Edit Item |