pith. sign in

arxiv: 1206.3752 · v3 · pith:OA5BG3CNnew · submitted 2012-06-17 · 🧮 math.CO

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

classification 🧮 math.CO
keywords mathcalmaximalregularantichainseverymemberregularitysubseteq
0
0 comments X
read the original abstract

Let $n\geqslant 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.