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

zbMATH Open1333.05305arXiv1206.3752MaRDI QIDQ2800779FDOQ2800779

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)

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.

Full work available at URL: https://arxiv.org/abs/1206.3752

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

zbMATH Keywords

separating systemcompletely separating system

Mathematics Subject Classification ID

Extremal set theory (05D05)

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)