Note on the number of antichains in generalizations of the boolean lattice

We give a short and self-contained argument that shows that, for any positive integers \(t\) and \(n\) with \(t =O\Bigl(\frac{n}{\log n}\Bigr)\), the number \(\alpha([t]^n)\) of antichains of the poset \([t]^n\) is at most \[{\exp_2\Bigl[\Bigl(1+O\Bigl(\Bigl(\frac{t\log^3 n}{n}\Bigr)^{1/2}\Bigr)\Bigr)N(t,n)\Bigr]}\,,\] where \(N(t,n)\) is the size of a largest level of \([t]^n\). This, in particular, says that if \({t \!\ll\! n/\log^3 \! n}\) as \(n \rightarrow \infty\), then \(\log\alpha([t]^n)=(1+o(1))N(t,n)\), giving a (partially) positive answer to a question of Moshkovitz and Shapira for \(t, n\) in this range. Particularly for \(t=3\), we prove a better upper bound: \[\log\alpha([3]^n)\le(1+4\log 3/n)N(3,n),\] which is the best known upper bound on the number of antichains of \([3]^n\).Mathematics Subject Classifications: 05A16, 06A07Keywords: Boolean lattice, antichains, entropy method

Authors

Publication Details

Journal
Combinatorial Theory
Published
2025-03-14
DOI
https://doi.org/10.5070/c65165018
Primary Topic
Mathematical Dynamics and Fractals
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Note on the number of antichains in generalizations of the boolean lattice

Michail Sarantis, Prasad Tetali, Jinyoung Park
Combinatorial Theory
Mathematical Dynamics and Fractals
article

Note on the number of antichains in generalizations of the boolean lattice

Michail Sarantis, Prasad Tetali, Jinyoung Park
article en

Abstract

We give a short and self-contained argument that shows that, for any positive integers \(t\) and \(n\) with \(t =O\Bigl(\frac{n}{\log n}\Bigr)\), the number \(\alpha([t]^n)\) of antichains of the poset \([t]^n\) is at most \[{\exp_2\Bigl[\Bigl(1+O\Bigl(\Bigl(\frac{t\log^3 n}{n}\Bigr)^{1/2}\Bigr)\Bigr)N(t,n)\Bigr]}\,,\] where \(N(t,n)\) is the size of a largest level of \([t]^n\). This, in particular, says that if \({t \!\ll\! n/\log^3 \! n}\) as \(n \rightarrow \infty\), then \(\log\alpha([t]^n)=(1+o(1))N(t,n)\), giving a (partially) positive answer to a question of Moshkovitz and Shapira for \(t, n\) in this range. Particularly for \(t=3\), we prove a better upper bound: \[\log\alpha([3]^n)\le(1+4\log 3/n)N(3,n),\] which is the best known upper bound on the number of antichains of \([3]^n\).Mathematics Subject Classifications: 05A16, 06A07Keywords: Boolean lattice, antichains, entropy method

Combinatorial TheoryVol. 5(1)
National Science Foundation, Carnegie Mellon University, Alexander S. Onassis Public Benefit Foundation
Openalex Percentile: Top 91%
Mathematical Dynamics and Fractals
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.