Timeline for The hypercube: $|A {\stackrel2+} E| \ge |A|$?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 7, 2011 at 9:56 | vote | accept | Seva | ||
| Nov 5, 2011 at 8:44 | comment | added | Seva | @fedja: correct; I should have noticed this... | |
| Nov 5, 2011 at 2:29 | answer | added | fedja | timeline score: 8 | |
| Nov 5, 2011 at 0:35 | comment | added | fedja | As stated, it is overly optimistic. Take $A$ to be the set of all vertices of the same parity. Then the count is sharp. Now, we can kill one 2-neighbour vertex removing at most $n$ vertices in $A$. But it costs nothing to add $n$ vertices of the opposite parity (in fact, you can add as many as $2^{n-1}/n$ of them without creating new 2-neighbour vertices). So even if the conjecture is true, the cutoff is not at $2^{n-1}$. | |
| Nov 4, 2011 at 17:41 | history | asked | Seva | CC BY-SA 3.0 |