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

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.

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

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.

• 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

I’ll formulate the essence of the problem with a hope that a specialist will read it and solve. Its graph theoretical formulation is only introductive, because in fact it is about matchings on a compete graph with possible zero edge weights. Then the graph-theoretical problem transforms into an algebraic one about an existence of solutions of a special system of polynomial equations. Its graph-theoretical origin only determines the system structure.

According to our conjecture we have to show that the system is solvable iff $$d=2$$ or $$d=3$$ and $$n=4$$. We already know the solvability for the mentioned $$(n,d)$$. Moreover, the existence of solutions only in very special cases is very expected because the system has exponentially many ($$d^n$$) equations but only quadratically many ($$d^2n(n-1)/2$$) variables.

Due to system origin from the family $$\mathcal M$$ of all perfect matchings on a complete graph, the system structure is relatively simple and highly symmetric. So I read “Symmetry”by Hermann Weyl and in its conclusion I found the following advice.

What we learn from our whole discussion and what has indeed become a guiding principle in modern mathematics is this lesson: Whenever you have to do with a structure-endowed entity $$\Sigma$$ try to determine its group of automorphisms, the group of those element-wise transformations which leave all structural relations undisturbed. You can expect to gain a deep insight into the constitution of $$\Sigma$$ in this way. After that you may start to investigate symmetric configurations of elements, i.e. configurations which are invariant under a certain subgroup of the group of all automorphisms; and it may be advisable, before looking for such configurations, to study the subgroups themselves, e.g. the subgroup of those automorphisms which leave one element fixed, or leave two distinct elements fixed, and investigate what discontinuous or finite subgroups there exist, and so forth. In the study of groups of transformations one does well to stress the mere structure of such a group.

Indeed, I found some transformations of the system variables which keep solutions, but not to many. I particular, I don’t know how to construct a symmetric solution of the system from a given one.

The structure of the system is the following. For each vertices $$i of $$\{1,\dots, n\}=[n]$$ and colors $$c_i,c_j\in\{1,\dots,d\}=[d]$$ we have a variable $$ij,c_ic_j$$ whose value is a complex number and is a weight of an edge from $$i$$ to $$j$$, whose endpoint $$i$$ is colored by $$c_i$$ and endpoint $$j$$ is colored by $$c_j$$. There are $$d^n$$ vertex colorings $$c:[n]\to [d]$$. Each coloring $$c$$ determines a weight $$c(PM)$$ of each perfect mathching $$PM\in\mathcal M$$ as $$c(PM)=\prod ij,c(i)c(j)$$. The corresponding to $$c$$ equation of the system is $$\sum{PM\in\mathcal M} c(PM)=\delta(c),$$ where $$\delta(c)=1$$, if $$c$$ is monochromatic, and $$\delta(c)=0$$, otherwise.

In some special cases we can say more. Recall that all presently known solutions are monochromatic, that is all their non-zero edge weights $$ij,c_ic_j$$ correspond to monochromatic edges, that is for $$c_i=c_j$$. I expect that by means of graph theory I can prove that if the system has a monochromatic solution then $$d\le (n-1)(n-2)/2$$, which fits the conjecture for $$n=4$$. But I guess this result has no physical value, so I didn’t write its proof or tried hard to improve this bound.

Another special (but still unsolved) case is $$n=4$$. In this case we can split the system in the following sense. If we fix values $$ij,c_ic_j$$ for all $$i then we obtain a linear system $$Ax=b$$ for the values $$i4,c_ic_4$$ for all $$i<4$$. It is well-known that this system has no solutions iff $$\operatorname{rank} A<\operatorname{rank} A|b$$, so we have to verify this condition for each choice of values $$ij,c_ic_j$$ for all $$i.

As a visual aid, we present a system for $$d=2$$. For the sake of simplicity we restrict ourselves for monochromatic case, when $$c_i=c_j$$ for each $$ij,c_ic_j$$, which we therefore denote by $$ij,c$$. We have $${n\choose 2}d=12$$ variables

12,1 13,1 14,1 22,1 23,1 24,1 12,2 13,2 14,2 22,2 23,2 24,2


When we fix values of $$ij,c$$ for $$j\ne 4$$, we can describe the structure of the system $$Ax=b$$ by the following table

      14,1 24,1 34,1 14,2 24,2 34,2
1111  23,1 13,1 12,1                1
1122                           12,1
1212                      13,1
1221  23,2
2112                 23,1
2121       13,2
2211            12,2
2222                 23,2 13,2 12,2 1


The first column lists the colorings of $$[n]=[4]$$ into $$d=2$$ colors, determining the respective row of the matrix $$A$$. There are $$d^4=16$$ colorings of $$[4]$$ into $$2$$ colors, but the monochromaticity condition implies that all rows corresponding to colorings containing monochromatic sets of odd size are zero, so we skipped these rows. All not listed entries of table are zeroes. The last column corresponds to the vector $$b$$.

Thus, for instance, the first three equations of the system $$Ax=b$$ are:

$$23,1\cdot 14,1+13,1\cdot 24,1+12,1\cdot 34,1=1$$

$$12,1\cdot 34,2 =0$$

$$13,1\cdot 24,2 =0$$.