Antichains in the set of subsets of a multiset
type: Item
instance of: scholarly article
title: Antichains in the set of subsets of a multiset
zbMATH Open document ID: 0534.05006
DOI: 10.1016/0012-365X(84)90128-6
author: G. F. Clements
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: Let M be a multiset on \(\{\) 1,2,...,\(n\}\) with i occuring \(k_ i\) times, \(k_ n\leq...\leq k_ 1.\) S is the family of subsets, i.e. sequences \(\underline x=(x_ n,...,x_ 1)\) with \(0\leq x_ i\leq k_ i.\) A c- chain is a sequence \(\underline x_ 0\subset ...\subset \underline x_ c\) from S. A c-antichain is an \(F\subseteq S\) without a c-chain. For \(\underline x=(x_ n,...,x_ 1)\) put \(| \underline x| =x_ n+...+x_ 1.\) The weight of \(F\subseteq S\) is \(wF=\sum \{| \underline x|:\underline x\in F\}.\) In this paper min wF is calculated when F ranges the f-element c-antichains. The formula uses a certain binomial coefficient-like representation of integers. The proof is modeled after \textit{D. E. Daykin's} [Nanta Math. 8, 84-94 (1975; Zbl 0332.05002)] proof of the special case for sets, i.e. \(k_ 1=1\).
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05A10
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 3847394
zbMATH Keywords: subsets
zbMATH Keywords: multisets
zbMATH Keywords: c-antichain
zbMATH Keywords: Kruskal-Katona theorem
zbMATH Keywords: binomial coefficient
reviewed by: Péter Komjáth
MaRDI profile type: Publication
cites work: A generalization of a combinatorial theorem of macaulay
cites work: A minimization problem concerning subsets of a finite set
cites work: The minimal number of basic elements in a multiset antichain
cites work: Inequalities concerning numbers of subsets of a finite set
cites work: On Existence of Distinct Representative Sets for Subsets of a Finite Set
cites work: More on the generalized Macaulay theorem. II
cites work: On maximal antichains containing no set and its complement
cites work: A generalization of the Kruskal-Katona theorem
cites work: Q4096951
cites work: Q4096954
cites work: Existence theorems for Sperner families
cites work: Q4196436
cites work: Q4071752
cites work: Q5726070
description: scientific article; zbMATH DE number 3847394