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: enter image description here 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.

  • $\begingroup$ Do we allow multiple edges (of different colors/bicolors) connecting the same pair of vertices? $\endgroup$ Sep 24, 2018 at 23:36
  • $\begingroup$ yes, multiedges are allowed (i specify that now). $\endgroup$ Sep 25, 2018 at 5:28
  • $\begingroup$ Are multicolor edges necessary? It seems that appropriate weights are enough to fulfill property 2. $\endgroup$ Oct 1, 2018 at 15:41
  • 1
    $\begingroup$ 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? $\endgroup$ Oct 5, 2018 at 16:26
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 26, 2019 at 6:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.