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

MaRDI QIDQ2800779zbMATH OpenFDO

Authors Thomas Kalinowski, Uwe Leck, Christian Reiher, Ian T. Roberts

Publication date 18 April 2016

Published in The Australasian Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.3752, http://ajc.maths.uq.edu.au//pdf/64/ajc_v64_p277.pdf

zbMATH Keywords

separating systemcompletely separating system

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: Let $ngeqslant3$ be a natural number. We study the problem to find the smallest $r$ such that there is a family $mathcalA$ of 2-subsets and 3-subsets of $[n]=1,2,\mathrm{...},n$ with the following properties: (1) $mathcalA$ is an antichain, i.e. no member of $mathcalA$ is a subset of any other member of $mathcalA$, (2) $mathcalA$ is maximal, i.e. for every $Xin{2}^{[n]}setminusmathcalA$ there is an $AinmathcalA$ with $XsubseteqA$ or $AsubseteqX$, and (3) $mathcalA$ is $r$-regular, i.e. every point $xin[n]$ is contained in exactly $r$ members of $mathcalA$. We prove lower bounds on $r$, and we describe constructions for regular maximal antichains with small regularity.

Recommendations

• Maximal antichains of minimum size
• On the existence of regular antichains
• \(k\)-regular antichains on [\(m\)] with \(k \leq m - 2\)
• \((m-1)\)-regular antichains on \([m]\)
• Maximal fiat regular antichains

Cited in

(7)

• On the existence of regular antichains
• \(k\)-regular antichains on [\(m\)] with \(k \leq m - 2\)
• Maximal antichains of minimum size
• Maximal fiat regular antichains
• Minimum weight flat antichains of subsets
• \((m-1)\)-regular antichains on \([m]\)
• Maximal flat antichains of minimum weight

This page was built for publication: Minimizing the regularity of maximal regular antichains of 2- and 3-sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2800779)