1-cross intersecting set pair systems are small

Dylan King; Van Magnan; Cory Palmer

In the authors' words

A set pair system ${(A_{i}, B_{i})}_{i = 1}^{m}$ is $1$ -cross intersecting if $∣ A_{i} \cap B_{i} ∣ = 0$ for all $i$ and $∣ A_{i} \cap B_{j} ∣ = 1$ whenever $i \neq = 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} ∣ \leq a$ and $∣ B_{i} ∣ \leq b$ for all $i$ . We prove a conjecture of F\"uredi, Gy\'arf\'as, and Kir\'aly [Combin. Probab. Comput. 32 (2023)] that asserts $m (n, n, 1) / (n 2 n) \to 0$ as $n \to \infty$ .

Main resultThe abstract does not state a limitation.

1-cross intersecting set pair systems are small

In the authors' words

More on Combinatorics & discrete math that day

Circular s-choice parking functions: an exact closed formula via rotational symmetry

Single-Fragment Forensic Coding via Multidimensional Cyclically Permutable Codes

The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach

Proof of Almkvist's conjecture on the unimodality of partition polynomials

On infinite families of [Pn​]-irregular graphs

$1$ -cross intersecting set pair systems are small

On infinite families of $[P_{n}]$ -irregular graphs