3
$\begingroup$

Suppose $a\in \{0,1\}^n$ and $S \subseteq \mathbb{F}_2^n$ is a subspace of dimension $d$. Define an affine subspace $S_a$ as follows: $$S_a=\{a+x \mid x\in S\}.$$ What is the largest possible size of the antichain sitting inside $S_a$ for all $a \in \{0,1\}^n$?

For example, $S=\{000,001,010,011\}$. Clearly $\operatorname{dimension}(S)=2$. Observe that there is no point in choosing $a \in S$ as we will obtain the same set $S$ (by definition).

Suppose $a\in \{100,101,110,111\}$. Then affine subspace, $S_a=\{100,101,110,111\}$ irrespective of which $a$ we chose. In this scenario, the size of the antichain is 2 ($\{101,110\}$) which is same as antichain of $S$. I am wondering, if this is the case for all subspaces $S$ or we can obtain a bigger antichain. Is there an explanation for this observation?

$\endgroup$

1 Answer 1

4
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Thank you, Professor. The explanation is great. $\endgroup$
    – akr_
    Sep 11, 2021 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.