Timeline for Partitioning the vertices of an n-cube with random hyperplane cuts
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 1, 2012 at 21:34 | comment | added | Kevin P. Costello | Somewhat annoyingly, it seems like the usual second moment method to get a matching lower bound may not quite work here, or at least not easily. The trouble is that if a hyperplane intersects a given edge, it is significantly more likely to intersect each other edge in the same direction (roughly speaking, if the edges are Hamming distance $d \approx n/2$ apart, hitting the first edge increases the probability the second edge is hit by a factor of $2$). This ends up making the probability that both edges are missed by all $n^{3/2}$ edges much larger than the square of the prob. one is missed | |
| Jun 1, 2012 at 2:31 | history | edited | Douglas Zare | CC BY-SA 3.0 |
deleted incorrect log n factor
|
| Jun 1, 2012 at 2:25 | history | undeleted | Douglas Zare | ||
| Jun 1, 2012 at 2:22 | history | edited | Douglas Zare | CC BY-SA 3.0 |
Now separating all pairs of vertices instead of just pairs of adjacent vertices.; deleted 13 characters in body
|
| Jun 1, 2012 at 1:54 | history | deleted | Douglas Zare | ||
| Jun 1, 2012 at 1:53 | comment | added | Douglas Zare | Hmm, good point. | |
| Jun 1, 2012 at 1:47 | comment | added | fedja | Each edge intersects a hyperplane iff the partition separates all vertices. Really? I'm not that sure. Take a few planes in $R^3$ parallel to the vector $1,1,0$. You can cross any edge you want with such a hyperplane. However it is quite hard to separate $(1,1,1)$ and $(-1,-1,1)$ by any such plane... | |
| May 31, 2012 at 23:51 | history | answered | Douglas Zare | CC BY-SA 3.0 |