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

Original · EN

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