“On the number of lower sets with fixed cardinality”
Giovedì 23 Novembre 2023, ore 17:30 - Aula 2AB40 - Kristina Oganesyan (Universitat Autònoma de Barcelona)
Abstract
We call a set $S \subset \mathbb{Z}^{d}_{+}, d \geq 2\,$, a lower set if for any $\mathbf{x}=(x_1,\ldots,x_d) \in \mathbb{Z}^{d}_{+}\,$ the condition $\mathbf{x} \in S\,$ implies $\mathbf{x’}=(x’_1,\ldots,x’_d) \in S\,$ for all $\mathbf{x’} \in \mathbb{Z}^{d}_{+}\,$ with $x’_i \leq x_i\,, 1 \leq i \leq d \,$. Equivalently, one can think of a $d$-dimensional lower set as of a union of unit cubes $\prod_{i=1}^{d}[k_i, k_i+1]\;, k_i \in \mathbb{Z}_+ \,$, such that in each direction any cube leans either on another one or on the coordinate hyperplane.
We will be interested in estimating the number $p_d(n)\,$ of $d$-dimensional lower sets of cardinality $n \,$. The two-sided inequality $C_1(d)n^{1−1/d} \lt \log{p_d(n)} \lt C_2(d)n^{1−1/d} \quad$ is known to be always true, where $C_1(d) \gt 1 \,$ whenever $\log{n} \gt 3d \;$. We show that if $d \,$ is sufficiently small with respect to $n \,$, then $C_2 \,$ does not depend on $d \,$, which means that $\log{p_d(n)} \,$ is up to an absolute constant equal to $n^{1−1/d} \,$.
