On an acyclic relaxation of incomparable families of sets

Abstract

For two families $\mathcal{A},\mathcal{B}\subseteq \mathcal{P}([k])$, we write $\mathcal{A}⊢\mathcal{B}$ if $A⊉B$ for each two sets $A\in \mathcal{A}$ and $B\in \mathcal{B}$. $\mathcal{A}$ and $\mathcal{B}$ are called incomparable if $\mathcal{A}⊢\mathcal{B}$ and $\mathcal{B}⊢\mathcal{A}$. Seymour proved that the maximum size of two incomparable equal-sized families in $\mathcal{P}([k])$ is $\frac{1}{4}{2}^k$. A sequence of families ${\mathcal{B}}_1,\dots ,{\mathcal{B}}_l\subseteq \mathcal{P}([k])$ is called $d$-exceeding if ${\mathcal{B}}_i⊢{\mathcal{B}}_j$ for all $i,j\in [l]$ with $j-i\in [d]$. Cyclically reusing $d+1$ pairwise incomparable families yields arbitrarily long $d$-exceeding sequences of families. We prove inversely that the maximum size of equal-sized families of a sufficiently long $1$-exceeding sequence in $\mathcal{P}([k])$ is also $\frac{1}{4}{2}^k$. A sequence of sets $B_1,\dots ,B_l\subseteq [k]$ is called $d$-exceeding if $\{B_1\},\dots ,\{B_l\}$ is $d$-exceeding, that is, if $B_i⊉B_j$ for all $i,j\in [l]$ with $j-i\in [d]$. We locate the maximum $d$ such that there exist arbitrarily long $d$-exceeding sequences of subsets of $[k]$ between $(1-o(1))\frac{1}{e}{2}^k$ and $\frac{1}{2}{2}^k-2$.