Kalinowski, Thomas

Leck, Uwe

Reiher, Christian

Roberts, Ian T

2016-02

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

Australasian Journal of Combinatorics, v.64, p. 277-288

2202-3518

1034-4942

https://hdl.handle.net/1959.11/26793

Centre for Discrete Mathematics & Computing

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

Journal Article

Publication