Largest size of a domination free family

Question

Given $n,d$, we can consider $S=[d]^n$. Given $x,y\in S$, we say $x$ dominates $y$ if $x_i\geq y_i$ for all i.

We say a family $F\in2^S$ is domination free, if it contains no $x,y$ with $x$ dominating $y$.

Is this well known in the literature?

What is the largest size of a domination free family?

Answer 1

The largest domination-free family (the largest antichain in the grid poset $[d]^n$) is given by the subset $S^* \subseteq [d]^n$ consisting of all points $(x_1, x_2, \dots, x_n)$ that satisfy $x_1 + x_2 + \dots + x_n = \lfloor \frac12 n(d+1)\rfloor$.

The standard proof is in the spirit of Dilworth's theorem. We partition $[d]^n$ into disjoint symmetrical chains: sequences $x^1, x^2, \dots, x^k$ with the property that:

1. Each pair $(x^i, x^{i+1})$ is exactly one step apart: they differ by $1$ in one coordinate and agree in all others.
2. The number of steps from $(1,1,\dots,1)$ to $x^1$ is the same as the number of steps from $x^k$ to $(d,d,\dots,d)$.

If this can be done, it proves that the family $S^*$ given above is the largest domination-free family: any domination-free family can contain at most one element of every symmetrical chain, and $S^*$ contains exactly one element of every symmetrical chain. (An equivalent way of defining $S^*$ is as the set of points which are an equal number of steps apart from $(1,1,\dots,1)$ and $(d,d,\dots,d)$.)

A short (and possibly historically the first published) proof of this is in the paper On the set of divisors of a number by de Bruijn et al. There, the problem is stated in terms of sets of divisors of $p_1^{d-1} p_2^{d-1} \dotsb p_n^{d-1}$ which contain no pair of distinct $x,y$ with $x \mid y$, which is equivalent to this problem.