Added (19.01.2021): Dustin Mixon wrote a blog post about the question where he reformulated and generalized the question.
Added (25.12.2020): I made a youtube video to explain the question in detail.
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<j$ 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.
