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.
This post imported from StackExchange MathOverflow at 2024-06-17 13:14 (UTC), posted by SE-user Mario Krenn
Q&A (4863)
