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

Thomas Kalinowski, Uwe Leck, C Reiher, Ian Roberts

    Research output: Contribution to journalArticlepeer-review

    13 Downloads (Pure)

    Abstract

    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. 
    Original languageEnglish
    Pages (from-to)277-288
    Number of pages12
    JournalAustralasian Journal of Combinatorics
    Volume64
    Issue number2
    Publication statusPublished - 2016

    Fingerprint

    Dive into the research topics of 'Minimizing the regularity of maximal regular antichains of 2-sets and 3-sets'. Together they form a unique fingerprint.

    Cite this