Given a partition of the edges of $K_{n,n}$ into $n$ colours, where each colour appears exactly $n$ times, prove that there exists a vertex incident to at least $\sqrt{n}$ colours.
$\begingroup$
$\endgroup$
7
-
1$\begingroup$ As it's now, this sounds as a misunderstanding. Every vertex of $\ K_{n\,n}\ $ is an end of $\ n\ $ different edges that are of $n$-different colors (by the definition of the edge-coloring). $\endgroup$– Wlod AACommented Feb 3, 2023 at 14:17
-
1$\begingroup$ Its not a proper edge colouring $\endgroup$– Marina DrygalaCommented Feb 3, 2023 at 15:20
-
$\begingroup$ Would you provide the definition of proper edge coloring (straight in your Question)? -- it'd be so nice. $\endgroup$– Wlod AACommented Feb 3, 2023 at 15:28
-
1$\begingroup$ Sorry I had missed an important detail, is it more clear now? $\endgroup$– Marina DrygalaCommented Feb 3, 2023 at 15:48
-
2$\begingroup$ @WlodAA Proper edge colouring = edge colouring. Based on the discussion, I assume what the OP means is that we are given a labelling of edges by colours without any constraints on incident edges. $\endgroup$– Emil JeřábekCommented Feb 3, 2023 at 16:19
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
2
Here is a short proof. Thanks to David Speyer for simplifying an earlier proof of mine (see the comments below).
For each colour $i \in [n]$, let $a_i$ be the number of vertices incident to an edge of colour $i$. Observe that $a_i \geq 2\sqrt{n}$ for all $i$, where equality is obtained if and only if the edges of colour $i$ induce a $K_{\sqrt{n}, \sqrt{n}}$. Thus, $\sum_{i \in [n]} a_i \geq 2n \sqrt{n}$. On the other hand, $\sum_{i \in [n]} a_i$ is the number of ordered pairs $(v,i)$, where $v$ is a vertex, and $i$ is a colour incident to $v$. Therefore, since there are only $2n$ vertices, some vertex must be incident to at least $\sqrt{n}$ colours.
answered Feb 3, 2023 at 18:05
-
4$\begingroup$ 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. $\endgroup$ Commented Feb 3, 2023 at 19:18
-
$\begingroup$ @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$. $\endgroup$ Commented Feb 3, 2023 at 20:48