Maximum number of colors for embedding all colored perfect matchings in the complete graph

Question

For given $n>1$ I'm looking for the maximum number $k$ of colors such that there exists a $k$-coloring of the edges of the complete graph on $2n$ vertices with the property that a copy of every possible $k$-colored perfect matching is present in the colored complete graph.

For example, we know that there are $(n+1)$ 2-colored perfect matchings. On the other hand, we know that the complete graph can be decomposed into $(2n-1)$ perfect matchings (cf. Theorem 3.2 in 1-factorizations by Wallis). This gives $k>1$. On the other hand, for $(2n-1)$ colors we need to give each of the disjoint perfect matchings a dedicated color to accomodate the monochromatic perfect matchings. But then a perfect matching with $(n-1)$ edges of color $1$ and one edge of color $2$ cannot be present. So we have $k<2n-1$.

Can we improve upon these bounds?

EDIT: The problem seems to be harder than I thought, so I narrow it down.

Prove or disprove that $k=\omega(1)$.

Answer 1

This proof is inspired by Patrick's answer. We use a uniformly random coloring of the complete graph $K_{2n}$ with $k=k(n)$ colors, yielding a random colored complete graph $C_{2n}$. For simplicity we consider $k=\sqrt{n/\ln(n)}$. We establish the following claims.

1. Let $G(2n,1/k)$ be the random graph on $2n$ vertices where each edge is drawn independently with probability $1/k$. Then $G(2n,1/k)$ has no perfect matching with probability $O(ne^{-n/k})$, using the Bachmann-Landau notation.
2. Let $M$ be the set of the $\binom{n+k-1}{k-1}$ colored perfect matchings (up to equivalence). For $m\in M$ we have $$\mathbb P(C_{2n}\textrm{ contains no copy of }m)=O(ne^{-n/k}).$$
3. We have $\mathbb P(\textrm{Exists }m\in M\textrm{ with no copy in }C_{2n})=o(1)$.

We turn to the proofs.

1. Notice that the random bipartite graph $G(n,n,1/k)$, where each edge between the two vertex sets of size $n$ each is included with probability $1/k$, is a subgraph of $G(2n,1/k)$, say the bipartite subgraph induced by the vertex sets $\{1,\dots,n\}$ and $\{n+1,\dots,2n\}$. Remark 4.3 in "Random Graphs" by Janson, Łuczak and Rucinski states that $$\mathbb P(G(n,n,p)\textrm{ has no perfect matching})=O(ne^{-np}),$$ which is valid for all $n$ and $p$. But combining these observations gives $$\mathbb P(G(2n,1/k)\textrm{ has no perfect matching})\le\mathbb P(G(n,n,1/k)\textrm{ has no perfect matching})=O(ne^{-n/k}).$$
2. We borrow the argument from the proof of Lemma 9 in Sequentially constrained Hamilton cycles in random graphs by Frieze and Pegden. Consider some order $e_1,\dots,e_N$ on the $N=\binom{2n}{2}$ edges of $K_{2n}$. For $0\le t\le N$ include edge $0<i\le t$ with probability $1$ and then choose a color uniformly at random. Include edge $i>t$ with probability $1/k$ with no color. These choices are independent. Let $\Gamma_t$ be the resulting partially colored graph. Notice that $\Gamma_0$ is $G(2n,1/k)$ and that $\Gamma_N$ is $C_{2n}$. The graph $\Gamma_t$ is proper if there exists a coloring of those edges among $e_{t+1},\dots,e_N$ which are included such that the resulting colored graph contains a copy of our perfect matching $m$. For given $t$ we couple $\Gamma_t$ and $\Gamma_{t+1}$ such that they coincide for all edges but $e_{t+1}$ and work conditional to these choices, denoted by $R$. If $R$ is proper, then we have $$\mathbb P(\Gamma_t\textrm{ proper}|R)=\mathbb P(\Gamma_{t+1}\textrm{ proper}|R)=1.$$ If $R\cup\{e_{t+1}\}$ is not proper, then we have $$\mathbb P(\Gamma_t\textrm{ proper}|R)=\mathbb P(\Gamma_{t+1}\textrm{ proper}|R)=0.$$ Otherwise, $R$ is not proper, but $R\cup\{e_{t+1}\}$ is proper, so we have $\mathbb P(\Gamma_t\textrm{ proper}|R)=1/k$. In particular, there exists a color $1\le i\le k$ such that $R$ with $e_{t+1}$ colored in $i$ is proper. This means that $$\mathbb P(\Gamma_{t+1}\textrm{ proper}|R)\ge\mathbb P(e_{t+1}\textrm{ colored in }i)=1/k=\mathbb P(\Gamma_t\textrm{ proper}|R).$$ This shows that $\mathbb P(\Gamma_t\textrm{ proper})\le\mathbb P(\Gamma_{t+1}\textrm{ proper})$ and with $\Gamma_0=G(2n,1/k)$, $\Gamma_N=C_{2n}$ that $$\mathbb P(G(2n,1/k)\textrm{ has perfect matching})\le\mathbb P(C_{2n}\textrm{ contains a copy of }m).$$ The claim is now immediate using the first claim.
3. The union bound gives $$\mathbb P(\textrm{exists }m\in M\textrm{ with no copy in }C_{2n})\le\sum_{m\in M}\mathbb P(C_{2n}\textrm{ contains no copy of }m).$$ A well-known bound for the binomial coefficient with $p=\frac{k-1}{n+k-1}$ and $H(p)=-p\ln(p)-(1-p)\ln(1-p)$ gives $$|M|=\binom{n+k-1}{k-1}\le\sqrt{\frac{1}{2\pi p(1-p)(n+k-1)}}e^{(n+k-1)H(p)}.$$ Using the second claim to bound the probabilities yields the bound $$O\left(\sqrt{\frac{n^2}{2\pi p(1-p)(n+k-1)}}\exp\left((n+k-1)H(p)-\frac nk\right)\right).$$ Substituting $k=\sqrt{n/\ln(n)}$ , we observe that the exponent is $-(1+o(1))\frac12\sqrt{n\ln(n)}$, while the leading factor is $O((n^3\ln(n))^{1/4})$, so the bound is $O(\exp(-(1+o(1))\frac12\sqrt{n\ln(n)}))$.

This shows that for any typical coloring of $K_{2n}$ we can simultaneously find copies of all colored perfect matchings, using up to $k=\sqrt{n/\ln(n)}$ colors.