Timeline for Expected Size of Independent Set
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 22, 2016 at 6:30 | comment | added | Fedor Petrov | We use an explicit formula for the number of independent subsets. In arbitrary tree I do not know it. | |
| Oct 21, 2016 at 17:44 | comment | added | addddddc | Thanks. Just an immediate question: If I generalize the problem to a tree, can the answer here generalize to that case please? | |
| Oct 21, 2016 at 17:40 | vote | accept | addddddc | ||
| Oct 21, 2016 at 8:49 | history | edited | Fedor Petrov | CC BY-SA 3.0 |
added 163 characters in body
|
| Oct 20, 2016 at 8:14 | history | undeleted | Fedor Petrov | ||
| Oct 20, 2016 at 8:14 | history | edited | Fedor Petrov | CC BY-SA 3.0 |
added 714 characters in body
|
| Oct 20, 2016 at 5:49 | history | deleted | Fedor Petrov | via Vote | |
| Oct 20, 2016 at 5:49 | comment | added | Fedor Petrov | Oh, you are correct, me not. Deleted. | |
| Oct 20, 2016 at 4:21 | comment | added | addddddc | Suppose there are $4$ vertices. If I understand your answer correctly, if in the first round I remove $v_2$, then the attained independent set is of size $f(1) + f(2) = 2$ in expectation. But this is not correct. There are two cases. First, $v_1$ is removed in second round (with probability $1/3$), the attained independent set would be of size $1$ because we further need to remove one of $v_3$ and $v_4$. Second, one of $v_3$ and $v_4$ is removed (with probability $2/3$), the attained independent set is of size $2$. Therefore, in expectation, the size should be $1/3 + 4/3 = 5/3$. | |
| Oct 19, 2016 at 19:35 | history | answered | Fedor Petrov | CC BY-SA 3.0 |