Timeline for For every partition of $E(K_{n,n})$ into $n$ colour classes of size $n$, there is a vertex incident to at least $\sqrt{n}$ colours
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 7, 2023 at 8:47 | vote | accept | Marina Drygala | ||
| Feb 3, 2023 at 21:33 | history | edited | Tony Huynh | CC BY-SA 4.0 |
deleted 366 characters in body
|
| Feb 3, 2023 at 20:48 | comment | added | Tony Huynh | @DavidESpeyer That's nice! Thanks. We can make the proof even slightly shorter by just defining $v_i$ to be the number of vertices incident to color $i$. Then $v_i \geq 2\sqrt{n}$ for each colour $i$. | |
| Feb 3, 2023 at 19:18 | comment | added | David E Speyer | It seems like, after your key observation $\ell_i + r_i \geq 2 \sqrt{n}$, we can finish much faster than that. Note that $\sum \ell_i + \sum r_i$ is the number of ordered pairs $(v,c)$ where $v$ is a vertex and $i$ is a color incident to $i$. From $\ell_i + r_i \geq 2 \sqrt{n}$, we deduce that $\sum \ell_i + \sum r_i \geq 2n \sqrt{n}$. There are $2n$ options for $v$, so there is some $v$ incident to $\geq \sqrt{n}$ colors. | |
| Feb 3, 2023 at 18:41 | history | edited | Tony Huynh | CC BY-SA 4.0 |
deleted 17 characters in body
|
| Feb 3, 2023 at 18:05 | history | answered | Tony Huynh | CC BY-SA 4.0 |