Minimizing the regularity of maximal regular antichains of 2- and 3-sets

Abstract

Let $n⩾3$ be a natural number. We study the problem to find the smallest $r$ such that there is a family $\mathcal{A}$ of 2-subsets and 3-subsets of $[n]=\{1,2,...,n\}$ with the following properties: (1) $\mathcal{A}$ is an antichain, i.e. no member of $\mathcal{A}$ is a subset of any other member of $\mathcal{A}$, (2) $\mathcal{A}$ is maximal, i.e. for every $X\in 2^{[n]}\setminus \mathcal{A}$ there is an $A\in \mathcal{A}$ with $X\subseteq A$ or $A\subseteq X$, and (3) $\mathcal{A}$ is $r$-regular, i.e. every point $x\in [n]$ is contained in exactly $r$ members of $\mathcal{A}$. We prove lower bounds on $r$, and we describe constructions for regular maximal antichains with small regularity.

7 pages, updated references