Timeline for One part of a bipartite graph has max degree 3. Partition the other part to 3 ~equal subsets s.t. just a fraction of first part see all 3 subsets
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 6, 2020 at 14:59 | vote | accept | Ruhollah Majdoddin | ||
| May 6, 2020 at 14:59 | vote | accept | Ruhollah Majdoddin | ||
| May 6, 2020 at 14:59 | |||||
| May 4, 2020 at 14:47 | comment | added | Tony Huynh | For a fixed vertex of degree 3, there are 27 ways its neighbours can be colored, and 6 of them in which its neighbours are rainbow. Since the colouring is random, the probability the neighborhood is rainbow is 6/27=2/9. Then use linearity of expectation. | |
| May 4, 2020 at 13:48 | comment | added | Ruhollah Majdoddin | It's not straightforward for me to get the $2/9$ bound for the general case with random coloring, still thinking ... | |
| May 3, 2020 at 17:05 | comment | added | Tony Huynh | In that case, taking a random colouring by flipping a fair 3-sided coin for each vertex seems to work. The expected number of vertices in $V$ that see all three colours is $\frac{2}{9} |V|$. | |
| May 3, 2020 at 13:28 | comment | added | Ruhollah Majdoddin | I just edited the question. In fact $2/9$ can be pretty acceptable. But $d$ can begi | |
| May 3, 2020 at 11:03 | comment | added | Ruhollah Majdoddin | Give me 1 hour or 2 ... | |
| May 3, 2020 at 10:15 | history | answered | Tony Huynh | CC BY-SA 4.0 |