|
This article is cited in 1 scientific paper (total in 1 paper)
On sizes of $1$-cross intersecting set pair systems
A. V. Kostochkaab, G. McCourta, M. Nahvia a University of Illinois at Urbana–Champaign, Urbana IL, USA
b Sobolev Institute of Mathematics, Novosibirsk, Russia
Abstract:
Let $\{(A_i,B_i)\}_{i=1}^m$ be a set pair system. Füredi, Gyárfás, and Király called it $1$-cross intersecting if $|A_i\cap B_j|$ is $1$ when $i\neq j$ and $0$ if $i=j$. They studied the systems and their generalizations and, in particular, considered $m(a,b,1)$, the maximum size of a $1$-cross intersecting set pair system in which $|A_i|\leq a$ and $|B_i|\leq b$ for all $i$. Füredi, Gyárfás, and Király proved that $m(n,n,1)\geq 5^{(n-1)/2}$ and asked whether there are upper bounds on $m(n,n,1)$ significantly better than the classical bound ${2n\choose n}$ of Bollobás for cross intersecting set pair systems. Answering one of their questions, Holzman proved recently that if $a,b\geq 2$, then $m(a,b,1)\leq \frac{29}{30}\binom{a+b}{a}$. He also conjectured that the factor $\frac{29}{30}$ in his bound can be replaced by $\frac{5}{6}$. Our goal is to prove this bound.
Keywords:
set pair system, cross intersecting systems, edge partitions.
Received: 24.04.2021 Revised: 24.04.2021 Accepted: 11.06.2021
Citation:
A. V. Kostochka, G. McCourt, M. Nahvi, “On sizes of $1$-cross intersecting set pair systems”, Sibirsk. Mat. Zh., 62:5 (2021), 1039–1048; Siberian Math. J., 62:5 (2021), 842–849
Linking options:
https://www.mathnet.ru/eng/smj7612 https://www.mathnet.ru/eng/smj/v62/i5/p1039
|
Statistics & downloads: |
Abstract page: | 161 | Full-text PDF : | 38 | References: | 24 | First page: | 1 |
|