# A rainbow perfect matching in an edge-colored graph with spanning color classes

This question is a sequel of my last question and is eventually motivated by recent advances in quantum physics. Given an even number $$n\ge 6$$ and a positive integer $$k, Claim from the linked question follows from

Claim 2. Let $$G$$ be a graph on $$n$$ vertices whose edges are colored into $$n-k$$ colors such that each color class is spanning. Then $$G$$ has a rainbow perfect matching.

Recall that a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors. Although this subject is well-studied I failed to find an answer, for which biggest $$k=k(n)$$ Claim 2 holds.

The upper bounds for $$k(n)$$

The case of the large $$k(n)$$ looks too good to be true. In fact, since a perfect matching for $$G$$ has $$n'=n/2$$ edges, Claim 2 can hold only when $$k\le n'$$. Moreover, Lo suggested the proof of the following

Proposition 3. $$k(n)\le n’-2$$, if $$n’$$ is even and $$k(n)\le n’-1$$, if $$n’$$ is odd.

Proof. Let $$v_1,\dots, v_{n’}, u_1,\dots, u_{n’}$$ be the vertices of a graph $$G=K_{n}$$. Color edges of $$G$$ as follows. For each $$1\le i,j\le n’$$ the edge between $$v_i$$ and $$u_j$$ has color $$i+j \mod n’$$ and all remaining edges have color $$n’$$. If $$n’$$ is even then it is known that there is no rainbow matching of size $$n'$$ consisting of edges which have colors from $$0$$ to $$n’-1$$. If $$n’$$ is odd then to assure absence of such matching remove from $$G$$ all edges of color $$0$$. Now we can easily check that $$G$$ has no rainbow perfect matching. $$\square$$

Neugebauer, Wolff, and R. obtained the following

Proposition 4. $$k(n)\le n’-3$$, if $$n’=\pm 1\pmod 6$$.

Proof. Let $$V$$ and $$U$$ be a bipartition of vertices of a graph $$G=K_n$$ such that $$|V|=n’+2$$ and $$|U|=n’-2$$. We color edges of $$G$$ into colors which are elements of the set $$V$$ as follows. The edges between vertices of $$U$$ remain uncolored. For each $$v\in V$$ and $$u\in U$$ the edge $$vu$$ has color $$v$$. Since $$n’=\pm 1\pmod 6$$, there exists a Steiner triple system $$\mathcal S$$ with elements of $$V$$. Thus for each distinct vertices $$v,v’\in V$$ there exists a unique vertex $$v’’\in V$$ such that a set $$\{v,v’,v’’\}$$ is a block of $$\mathcal S$$. We color the edge $$vv’$$ of $$G$$ into the color $$v’’$$. It is easy to check that each color class of the constructed coloring is spanning.

Suppose for a contradiction that $$G$$ has a rainbow perfect matching $$M$$. Since edges between vertices of $$U$$ are uncolored, $$M$$ has $$|U|=n’-2$$ edges between $$U$$ and $$V$$ and so exactly two edges $$e$$ and $$e’$$ with both endvertices in $$V$$. Let a set $$V’$$ consists of these four vertices. Since all colors of $$V\setminus V’$$ are used to color edges of $$M$$ incident to vertices of $$U$$, colors $$v$$ and $$v’$$ of the edges $$e$$ and $$e’$$, respectively belong to $$V’$$. It follows that $$e=v’v’’$$ and $$e’=vv’’’$$ for some vertices $$v’’,v’’’\in V’$$. But then the pair $$\{v,v’\}$$ belongs to two distinct blocks $$\{v,v’,v’’\}$$ and $$\{v,v’,v’’’\}$$ of $$\mathcal S$$, a contradiction. $$\square$$

The lower bounds for $$k(n)$$

Proposition 5. $$k(n)\ge 1$$.

Proof. For $$k=1$$, Claim 2 follows from a more general conjecture by Li and Wang from 2008, finally proved by Kostochka and Yancey in 2012, and stating that if $$H$$ is an edge-colored graph such that each vertex of $$H$$ is incident to edges of at least $$\ell$$ distinct colors then $$H$$ has a rainbow matching of size $$\lceil \ell/2\rceil$$. $$\square$$

Remark that Li and Wang said that proper edge-colorings of complete graphs show that their conjecture is sharp if true, but I do not know whether we can provide counterexamples with a big number $$n-k$$ of spanning color classes.

Proposition 6. $$k(n)\ge 2$$ for $$n\le 8$$.

Proof. A quick case check shows that Claim 2 holds for $$n=6$$ and $$k=2$$. Neugebauer in his bachelor thesis showed using a SAT solver that $$k(8)=2$$. $$\square$$

Thanks.

• I asked Matt Yancey about this question and he answered: “There has been so much work on rainbow matchings that it has taken me some time to refresh my memory on this topic. As far as I have been able to tell, your question is novel”. Mar 11 at 9:06