PreprintarXiv licencearXiv
$1$-cross intersecting set pair systems are small
Abstract
A set pair system {(Ai,Bi)}i=1m is $1$-cross intersecting if |Ai ∩ Bi|=0 for all i and |Ai ∩ Bj| = 1 whenever i ≠ j. Let m(a,b,1) denote the maximum size m of a $1$-cross intersecting set pair system {(Ai,Bi)}i=1m where |Ai| ≤ a and |Bi| ≤ b for all i. We prove a conjecture of Füredi, Gyárfás, and Király [Combin. Probab. Comput. 32 (2023)] that asserts m(n,n,1)/binom2nn → 0 as n → ∞.
Related
- A product inequality and its application to cross-intersecting families
- Asymptotic enumeration of minimally intersecting filling curve systems on closed surfaces
- Sizes of cross-intersecting families
- A Sharp Product Bound for Disjoint Cross-Intersecting 3-Graphs with Covering Number Three
- A product theorem for r-cross intersecting families of subspaces
BibTeX
@misc{king20261cross,
title = {{$1$-cross intersecting set pair systems are small}},
author = {Dylan King and Van Magnan and Cory Palmer},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23891},
eprint = {2609.23891},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23891},
}
RIS
TY - UNPB
TI - $1$-cross intersecting set pair systems are small
AU - Dylan King
AU - Van Magnan
AU - Cory Palmer
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.23891
UR - https://arxiv.org/abs/2609.23891
AB - A set pair system {(A_i,B_i)}_i=1^m is $1$-cross intersecting if |A_i ∩ B_i|=0 for all i and |A_i ∩ B_j| = 1 whenever i ≠ j. Let m(a,b,1) denote the maximum size m of a $1$-cross intersecting set pair system {(A_i,B_i)}_i=1^m where |A_i| ≤ a and |B_i| ≤ b for all i. We prove a conjecture of Füredi, Gyárfás, and Király [Combin. Probab. Comput. 32 (2023)] that asserts m(n,n,1)/binom2nn → 0 as n → ∞.
ER -