TY - JOUR

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

AU - Kalinowski, Thomas

AU - Leck, Uwe

AU - Reiher, C

AU - Roberts, Ian

PY - 2016

Y1 - 2016

N2 - 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 [n] \ A there is an A ∈ 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.

AB - 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 [n] \ A there is an A ∈ 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.

UR - http://www.scopus.com/inward/record.url?scp=84949781836&partnerID=8YFLogxK

M3 - Article

VL - 64

SP - 277

EP - 288

JO - Australasian Journal of Combinatorics

JF - Australasian Journal of Combinatorics

SN - 1034-4942

IS - 2

ER -