Skip to main content
addendum added
Source Link
Richard Stanley
  • 50.8k
  • 14
  • 155
  • 279

Let $S=\{00,11\}$ and $a=10$. The largest antichain in $S$ has size 1, while the largest antichain in $S_a$ has size 2. We can extend this construction to get an affine subspace of any dimension $k$, all of whose elements form an antichain (of size $2^k$). Namely, letting $0^j$ denote a string of $j$ $0$'s, let $S$ be generated by $110^{2k-2}$, $00110^{2k-4}$, $0^4110^{2k-6}, \dots, 0^{2k-2}11$, and let $a=101010\cdots 10$.

Addendum. We can also ask for the size $A(k)$ of the largest possible antichain contained in a $k$-dimensional linear subspace. Clearly $A(k)\leq 2^k-1$, since the zero vector is in the subspace. The Hamming single-error correcting code $H(2^k,2^k-k-1)$ of length $n=2^k-1$ and dimension $k$ has all its nonzero vectors having $2^{k-1}$ 1's, so they form an antichain. Hence $A(k)=2^k-1$.

Let $S=\{00,11\}$ and $a=10$. The largest antichain in $S$ has size 1, while the largest antichain in $S_a$ has size 2. We can extend this construction to get an affine subspace of any dimension $k$, all of whose elements form an antichain (of size $2^k$). Namely, letting $0^j$ denote a string of $j$ $0$'s, let $S$ be generated by $110^{2k-2}$, $00110^{2k-4}$, $0^4110^{2k-6}, \dots, 0^{2k-2}11$, and let $a=101010\cdots 10$.

Let $S=\{00,11\}$ and $a=10$. The largest antichain in $S$ has size 1, while the largest antichain in $S_a$ has size 2. We can extend this construction to get an affine subspace of any dimension $k$, all of whose elements form an antichain (of size $2^k$). Namely, letting $0^j$ denote a string of $j$ $0$'s, let $S$ be generated by $110^{2k-2}$, $00110^{2k-4}$, $0^4110^{2k-6}, \dots, 0^{2k-2}11$, and let $a=101010\cdots 10$.

Addendum. We can also ask for the size $A(k)$ of the largest possible antichain contained in a $k$-dimensional linear subspace. Clearly $A(k)\leq 2^k-1$, since the zero vector is in the subspace. The Hamming single-error correcting code $H(2^k,2^k-k-1)$ of length $n=2^k-1$ and dimension $k$ has all its nonzero vectors having $2^{k-1}$ 1's, so they form an antichain. Hence $A(k)=2^k-1$.

Source Link
Richard Stanley
  • 50.8k
  • 14
  • 155
  • 279

Let $S=\{00,11\}$ and $a=10$. The largest antichain in $S$ has size 1, while the largest antichain in $S_a$ has size 2. We can extend this construction to get an affine subspace of any dimension $k$, all of whose elements form an antichain (of size $2^k$). Namely, letting $0^j$ denote a string of $j$ $0$'s, let $S$ be generated by $110^{2k-2}$, $00110^{2k-4}$, $0^4110^{2k-6}, \dots, 0^{2k-2}11$, and let $a=101010\cdots 10$.