On maximal antihierarchic sets of integers (Q2366018): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 07:52, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On maximal antihierarchic sets of integers |
scientific article |
Statements
On maximal antihierarchic sets of integers (English)
0 references
29 June 1993
0 references
Let us be given a fixed \(b>1\) integer and write the positive integers in base-\(b\) representation. Two positive integers are said to be comparable, if every entry in the base-\(b\) representation of one integer is greater than or equal to the corresponding entry in the base-\(b\) representation of the other integer. A set of pairwise incomparable numbers is called an antihierarchic set. The author investigates the following problem: what is the maximum cardinality of an antihierarchic set in the interval \([0,N-1]\)? An explicit formula (although involving alternating signs) answers the problem for \(N=b^ n\), asymptotics is given for the explicit formula in this case, and lower and upper bounds are given for the maximum cardinality of an antihierarchic set for arbitrary \(N\) which differ by a multiplicative factor 4 only. The proofs are based on Sperner type theorems for posets and generating function techniques.
0 references
digit
0 references
antichain
0 references
antihierarchic set
0 references
generating function
0 references