Dedekind's problem in the hypergrid

Falgas-ravry, Victor

doi:10.1016/j.aim.2026.110796

Dedekind's problem in the hypergrid

2026-01-01

0

OA

AI

DOI：10.1016/j.aim.2026.110796

Original

Save

View PDF

Abstract

En 中文

Consider the partially ordered set on [t](n):= {0, ... , t-1}(n) equipped with the natural coordinate-wise ordering, and let A(t, n) denote the number of antichains of this poset. Determining A(2, n) is the celebrated problem of Dedekind from 1897, and the general quantity A(t, n) has a number of combinatorial interpretations: it is precisely the number of (n-1)-dimensional partitions with entries from {0, ... , t}, and by a result of Moshkovitz and Shapira, A(t, n) + 1 is equal to the n-color Ramsey number of monotone paths of length tin 3-uniform hypergraphs. This has led to significant interest in the growth rate of A(t, n). Trivially, log(2) A(t, n) > alpha(t, n), where alpha(t, n) is the size of a maximal antichain in [t]n. In the present paper, we prove that this simple lower bound is close to optimal, in particular for every t, n > 2, (log(2) A(t, n) <= 1 + O ((log n)(3)/)) n . alpha(t, n). This resolves a conjecture of Moshkovitz and Shapira, and gives the first bound that is close to optimal for growing t. Our proof is based on the graph container method, partly inspired by previous work of Pohoata and Zakharov. One of our main contributions is a novel supersaturation result in [t](n). We prove that for any k is an element of Z(+) and delta > 0, any set A subset of [t](n) of size at least (k + delta)alpha(t, n) contains a vertex comparable to at least Omega(delta,k)((n/ log n)(k)) other elements of A, a bound that is optimal up to logarithmic factors. We achieve this by constructing a normalized matching flow on the cover graph of [t](n) in which the distribution of weights is close to uniform, a result that may be of independent interest. (c) 2026 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

Keywords:

Dedekind's problem

Hypergrid

Antichain

High-dimensional partition

Dedekind's problem in the hypergrid

Abstract

AI Summary

Journal

Organization

Cited Papers