Optimal pairs of incomparable clouds in multisets
type: Item
instance of: scholarly article
title: Optimal pairs of incomparable clouds in multisets
zbMATH Open document ID: 0854.06002
DOI: 10.1007/BF01858448
author: Levon H. Khachatrian
author: Rudolf Ahlswede
published in: Graphs and Combinatorics
publication date: 1997-01-19T00:00:00Z
review text: Let \(k^n\) be the \(n\)th product of \(n\)-element chains. Two sets \(A,B \subset k^n\) are incomparable if \(a \nleq b\), \(a \ngeq b\) for all \(a \in A\), \(b \in B\). Let \(f_n (\alpha) = \max \{|B |: A, B \subset k^n\) with \(|A |= \alpha\) and \(A\) incomparable to \(B\}\). The authors are concerned with the growth of the function \(f_n\) and prove, for example, the recursion: for every \(\alpha\), \(0 \leq \alpha \leq k^{n - 2}\) and for \(s \geq 0\): \[ f_n (\alpha) = (k - 1)k^{n - 1} + kf_{n - 2} (\alpha) - (k - 1) \alpha, \] \[ f_{n + 2s} (\alpha) = (k^s - 1) ( k^{n + s} - \alpha) + k^s f_n (\alpha). \] In the case \(k = 2\) these results are improvements of earlier ones by \textit{R. Ahlswede} and \textit{Z. Zhang} [Discrete Math. 85, 225-245 (1990; Zbl 0723.06001)].
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 887173
zbMATH Keywords: multisets
zbMATH Keywords: antichains
zbMATH Keywords: incomparable sets
reviewed by: Valeriy B. Mnukhin
MaRDI profile type: Publication
cites work: On cloud-antichains and related configurations
cites work: On incomparable collections of sets
cites work: Families of Non-disjoint subsets
cites work: A THEOREM ON FINITE SETS
cites work: The number of meets between two subsets of a lattice
cites work: An inequality for the weights of two families of sets, their unions and intersections
cites work: Q5688110
cites work: The maximal length of cloud-antichains
description: scientific article; zbMATH DE number 887173