# Vertex coloring inherited from perfect matchings (motivated by quantum physics)

Added (19.01.2021): Dustin Mixon wrote a blog post about the question where he reformulated and generalized the question.

Added (24.08.2019): As I consider this question important for quantum physics, I have announced a 3000 Euro award on its solution, see here for more details.

The following purely graph-theoretic question is motivated by quantum mechanics (and a special case of the questions asked here).

Bi-Colored Graph: A bi-colored weighted graph $$G=(V(G),E(G))$$, on $$n$$ vertices with $$d$$ colors is an undirected, not necessarily simple graph where there is a fixed ordering of the vertices $$V(G)=v_1, \ldots, v_n$$ and to each edge $$e \in E(G)$$ there is a complex weight $$w_e$$ and an ordered pair of (not necessarily different) colors $$(c_1(e),c_2(e))$$ associated with it from the $$d$$ possible colors. We say that an edge is monochromatic if the associated pair of colors are not different, otherwise the edge is bi-chromatic. Moreover, if $$e$$ is an edge incident to the vertices $$v_i,v_j \in V(G)$$ with $$i and the associated ordered pair of colors to $$e$$ is $$(c_1(e),c_2(e))$$ then we say that $$e$$ is colored $$c_1$$ at $$v_i$$ and $$c_2$$ at $$v_j$$.

We will be interested in a special coloring of this graph:

Inherited Vertex Coloring: Let $$G$$ be a bi-colored weighted graph and $$PM$$ denote a perfect matching in $$G$$. We associate a coloring of the vertices of G with PM in the natural way: for every vertex $$v_i$$ there is a single edge $$e(v_i) \in PM$$ that is incident to $$v_i$$, let the color of $$v_i$$ be the color of $$e(v_i)$$ at $$v_i$$. We call this coloring $$c$$, the inherited vertex coloring (IVC) of the perfect matching PM.

Weight of Vertex Coloring: Let $$G$$ be a bi-colored weighted graph. Let $$\mathcal{M}$$ be the set of perfect matchings of $$G$$ which have the coloring $$c$$ as their inherited vertex coloring. We define the weight of $$c$$ as $$w(c) := \sum_{PM \in \mathcal{M}} \prod_{e \in PM}w_e.$$ Moreover, if $$w(c)$$=1 we say that the coloring gets unit weight, and if $$w(c)$$=0 we say that the coloring cancels out.

Question: For which values of $$n$$ and $$d$$ are there bi-colored graphs on $$n$$ vertices and $$d$$ different colors with the property that all the $$d$$ monochromatic colorings have unit weight, and every other coloring cancels out?

We call such graphs monochromatic with respect to the IVC.

• The only known examples are $$C_{2n}$$ and $$K_4$$. Furthermore, Ilya Bogdanov has shown that, if all $$w_e$$ are positive real numbers, these examples are the only solutions.

Example of Inherited Vertex Coloring: A bi-chromatic weighted edge with one double edge between vertex 4 and 6 is shown on the top left, the edge weights $$E_{ij}$$ are shown below. On the right top, its eight perfect matchings are shown, and $$w(PM_i)$$ denotes the product of the edge weights of the perfect matching $$PM_i$$. The perfect matching 4 and 5 have the same inherited vertex coloring. As $$w(c)=w(PM_4)+w(PM_5)=0$$, we say this coloring cancels out. There are six remaining IVCs with nonzero weights, three of them are monochromatic, while three others are non-monochromatic. Therefore, the graph is not monochromatic.

PS: This problem can be rephrased entirely in terms of equation systems, without the connections to graph theory, as Alex Ravsky has already suggested.

• Do we allow multiple edges (of different colors/bicolors) connecting the same pair of vertices? – Mikhail Tikhomirov Sep 24 '18 at 23:36
• yes, multiedges are allowed (i specify that now). – Mario Krenn Sep 25 '18 at 5:28
• Are multicolor edges necessary? It seems that appropriate weights are enough to fulfill property 2. – LeechLattice Oct 1 '18 at 15:41
• Am I right thet a bichromatic edge is directed, i.e., that it is specified which its endpoint should get which color? Can some edge heve zero weight? – Ilya Bogdanov Oct 5 '18 at 16:26
• As for me, the question doesn’t look hopeless, so I sent an inspiring letter to five strong related specialists and I hope we’ll make a group to attack it. – Alex Ravsky Feb 26 '19 at 6:23