Timeline for Large sets $X \subseteq \mathbb{Z}_2^n$ with $X+X \ne \mathbb{Z}_2^n$
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 4, 2014 at 21:39 | comment | added | Will Sawin | Your reduction to finding an independent set in some graph is an equivalence - a set satisfies $(X+X ) \cap S = \emptyset$ if and only if it is an independent set in your graph. So the optimal solution is the maximum independent set. If $|S|=1$, your graph is a union of disjoint edges, so a set is maximal independent if and only if it comes from your construction. Because the size of this set does not depend on $S$ as long as $|S|=1$, this is also the best possible among all sets with $X+X \neq (\mathbb Z/2)^n$. | |
| May 4, 2014 at 6:16 | comment | added | Seva | @Will Sawin: do not get it; could you expand? | |
| May 3, 2014 at 20:51 | comment | added | Will Sawin | This construction doubles as a proof of optimality, at least for $|S|=1$. | |
| May 3, 2014 at 6:49 | history | edited | Seva | CC BY-SA 3.0 |
added 40 characters in body
|
| May 3, 2014 at 6:16 | history | answered | Seva | CC BY-SA 3.0 |