Timeline for Average minimum number of random k-sparse vectors in GF(2) to span the whole space?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| May 4, 2016 at 20:34 | comment | added | mhsnk | This is a nice analogy. Do you know the exact value of the minimum number of edges to be added to make this graph connected. | |
| May 4, 2016 at 18:56 | vote | accept | mhsnk | ||
| May 4, 2016 at 14:31 | comment | added | Sam Zbarsky | When k=2, this is equivalent to taking a graph on n+1 vertices and adding random edges until it is connected. Here the vector $e_i+e_j$ corresponds to edge $(i,j)$ and the vector $e_i$ corresponds to edge $(0,i)$ | |
| May 4, 2016 at 8:59 | answer | added | Sam Zbarsky | timeline score: 5 | |
| May 3, 2016 at 17:37 | comment | added | mhsnk | Thank you Robert! I have seen this post before and also the mentioned papers. My guess is that if $k$ is larger than the XORSAT satisfiability threshold, the average minimum required number of vectors will be equal to $n(1+o(1))$ but I don't know how to prove or disprove it? | |
| May 3, 2016 at 17:21 | comment | added | Robert Israel | You might look at this related MO question of mine and its answer by Kevin Costello. | |
| May 3, 2016 at 16:17 | history | asked | mhsnk | CC BY-SA 3.0 |