Let $c \geq 4$ be an even integer. In some football league, each team has a home uniform and anaway uniform. Every home uniform is coloured in two different colours, and every away uniformis coloured in one colour. A team’s away uniform cannot be coloured in one of the colours fromthe home uniform. There are at most $c$ distinct colours on all of the uniforms. If two teams havethe same two colours on their home uniforms, then they have different colours on their away uniforms. We say a pair of uniforms is clashing if some colour appears on both of them. Suppose that for every team $X$ in the league, there is no team $Y$ in the league such that the home uniform of $X$ is clashing with both uniforms of $Y$. Determine the maximum possible number of teams in the league.
Problem
Source: MEMO 2023 T4
Tags: combinatorics
25.08.2023 14:31
Claim: The problem is equivalent to the following: Let $G$ be a graph with $c$ vertices, what is maximum the number of $\{u, v, w\}\subseteq V(G)$ such that exactly $2$ of $uv, vw, wu$ are in $E(G)$.
Lemma: let $G$ be a graph with $n$ vertices and $m$ edges, the number of $\{u, v, w\}$ such that exactly $2$ of $uv, vw, wu$ are in $E(G)$ is at most $\begin{cases}mn-m-\frac{2m^2}n\text{, if }m\geq\frac{n^2}4\\m(\frac12n-1)\text{, if }m\leq\frac{n^2}4\end{cases}$.
In the lemma, the bound is maximized when $|m-\frac{n-1}{\frac4n}|=|m-\frac{n^2}4+\frac n4|$ is minimized or $m(\frac12n-1)$ is maximized. $\therefore$ the bound is maximized when $m=\lfloor\frac{n^2}4\rfloor=\lfloor\frac n2\rfloor\lceil\frac n2\rceil$, which can be reached by $G=K_{\lfloor\frac n2\rfloor, \lceil\frac n2\rceil}$ (or by numbering the $c$ colors from $1$ to $c$, and each team choose two odd (or even) colors to put on its home uniforms and one even (or odd) color to put on its away uniform). $\therefore$ the answer is $c\lfloor\frac{c^2}4\rfloor$.