A graph coloring problem from quantum physics (with prizes!)

What follows is a nice problem that was recently posed by Mario Krenn. Progress on this problem may lead to new insights in quantum physics (see this, this, this, and this for details). In addition, Mario has announced two cash prizes to encourage work in this direction. (!)

Consider a weighted and edge-colored bipartite graph $G=(A,B,E,k,w)$ consisting of

• disjoint vertex sets $A$ and $B$,
• an edge set $E\subseteq A\times B$,
• an edge coloring $k\colon E\to\mathbb{N}$, and
• a complex vertex weighting $w\colon A\to\mathbb{C}$.

This graph provides a combinatorial abstraction of a quantum mechanical system. Specifically, $A$ denotes a set of photon sources, $B$ is the set of optical output paths, $E$ is the set of all possible photons, $k(a,b)$ gives the mode number of photon $(a,b)\in E$, and the complex weights $w$ allow one to model quantum interference between the photon sources. Consider the following experiment: Place a detector at each $b\in B$, and let each $a\in A$ randomly produce either $\mathrm{deg}(a)$ correlated photons or no photons. We are interested in the event that all detectors simultaneously detect exactly one photon. The mode numbers of these photons can be viewed as a vertex coloring $c\colon B\to\mathbb{N}$, and this coloring reveals some information about which sources produced which photons. Specifically, we say $M\subseteq A$ is $c$-consistent if

• the neighborhoods $\{N(a):a\in M\}$ form a partition of $B$, and
• for every $a\in M$ and every $(a,b)\in E$, it holds that $k(a,b)=c(b)$.

In quantum optics, we cannot directly access the mode numbers of the photons, and in fact, we obtain a superposition of various possibilities. This superposition forms something called a Greenberger–Horne–Zeilinger (GHZ) state if $G$ satisfies an additional monochromatic property, defined below. Let $\mathcal{M}(c)$ denote the set of all $c$-consistent $M\subseteq A$, and define the weight of a coloring $c$ of $B$ to be

$\displaystyle w_G(c):=\sum_{M\in \mathcal{M}(c)}\prod_{a\in M}w(a).$

By convention, $\mathcal{M}(c)=\emptyset$ implies $w_G(c)=0$. We say $G$ is monochromatic if the weight of every coloring $c$ of $B$ takes the form

Here, $k(E)\subseteq\mathbb{N}$ denotes the image of the map $k\colon E\to\mathbb{N}$. In words, $G$ is monochromatic if $w_G(c)$ indicates whether $c$ gives every member of $B$ the same color in the palette $k(E)$. If $G$ is monochromatic, then the corresponding quantum mechanical system produces GHZ states, and the dimensionality of the state space is the size of the color palette $k(E)$.

In practice, one is interested in producing high-dimensional states with a given number particles, and the most practical of photon sources creates only two photons. For these reasons, we are particularly interested in the supremum of $|k(E)|$ over all monochromatic $G=(A,B,E,k,w)$ such that $|B|=n$ and $\mathrm{deg}(a)=2$ for every $a\in A$. Let $k_\mathrm{max}(n)$ denote this supremum. Notice that the constraint on $A$ implies that $G$ is monochromatic only if $n$ is even. For such $n$, Mario poses the following conjecture:

Excitingly, there are two prizes associated with this conjecture. First, there’s a 3000-Euro prize for its resolution (i.e., for either a proof or a disproof). In addition, there’s a 1000-Euro best-paper award offered for the best results obtained in this vein (to be judged by Mario). See this page for more details.

To explain the source of Krenn’s Conjecture, we point out that “half” of the conjecture is known to be true; that is, the inequality $\geq$ holds, while the inequality $\leq$ is open for every $n\in2\mathbb{N}$ with $n\geq4$. We obtain this lower bound on $k_\mathrm{max}(n)$ by restricting our attention to $G$ for which

• $k(a,b)=k(a,b')$ for every $a\in A$ and $b,b'\in N(a)$, and
• $w(a)=1$ for every $a\in A$.

This restriction is convenient, since we can capture $G$ using the edge-colored multigraph $G'=(V',E',r',k')$ with vertex set $V':=B$, edge set $E':=A$, assignment $r'\colon A\to\binom{B}{2}$ defined by $r'(a):=N(a)$, and edge coloring $k'\colon E'\to \mathbb{N}$ defined by $k'(a):=k(a,b)$ for every $(a,b)\in E$. For such $G'$, the corresponding $G$ is monochromatic if and only if the following hold simultaneously:

• for every color $i\in k'(E')$, there exists a unique perfect matching $M\subseteq E'$ of $G'$ such that $k'(M)={i}$, and
• for every perfect matching $M\subseteq E'$ of $G'$, it holds that $k'(M)$ is a singleton set.

This reduces our problem to finding multigraphs $(V',E',r')$ whose perfect matchings are all disjoint, since one may color edges $e$ in the $i$th perfect matching with $k'(e)=i$, and then color any remaining edges $e$ with $k'(e)=1$. Let $k'_\mathrm{max}(n)$ denote the supremum of $m$ for which there exists a multigraph on $n$ vertices with a total of $m$ perfect matchings, all of which are disjoint. Then the above discussion gives

$k_\mathrm{max}(n) \geq k'_\mathrm{max}(n).$

Notice we can already conclude $k_\mathrm{max}(n)\geq k'_\mathrm{max}(n)\geq1$ for every $n\in2\mathbb{N}$ by taking $G'$ to be a $1$-factor. In the special case where $n=2$, one may draw arbitrarily many edges between the two vertices to obtain $k_\mathrm{max}(2)\geq k'_\mathrm{max}(2)=\infty$, i.e., $k_\mathrm{max}(2)=\infty$. It remains to consider $n\in2\mathbb{N}$ with $n\geq4$. In this case, the multigraph we seek can be taken to be a simple graph without loss of generality (i.e., multiple edges are not helpful here), and so in this language, Ilya Bogdanov proved that $k'_\mathrm{max}(n)$ equals the right-hand side of Krenn’s Conjecture. The $n=4$ case corresponds to the $1$-factorization of $K_4$, while the remaining cases correspond to the $1$-factorization of $C_n$:

In order to determine whether this lower bound is sharp, one must consider more general choices of $G$. In particular, do non-unit weights on $A$ allow for a larger color palette? Interestingly, Mario has an example of $G=(A,B,E,k,w)$ with $|A|=9$, $|B|=6$, $|k(E)|=3$, and $w(a)\in\{x,1/x^2\}$ for every $a\in A$. However, this graph is only monochromatic in the limit as $x\to\infty$, so this does not quite prove that $k_\mathrm{max}(6)$ is at least $3$.

2 thoughts on “A graph coloring problem from quantum physics (with prizes!)”

1. One thing that I find very strange of this question: It seems that it should have a very simple solution, at least for large number of vertices n. The reason is that we can rewrite this question in a complex equation system, i wrote it at mathoverflow: https://mathoverflow.net/questions/341983/combinatorial-equation-system-with-exponentially-many-equations-in-quadratic-man

That equation system has c^n many equations for O(n^2) complex weights (c is the number of different colors, lets say c=3). That means the equation system is exponentially overdetermined. I would have expected that even the most crude technique could show that for sufficiently large n, there is no solution.

2. kevin says:

I’ve played with this a bit and have solved the n=4 case.
If people are interested in a mini-polymath push for n=6, I think that may be doable as well. Other techniques would be required to fully solve the conjecture though.

For n=4, there is actually an even stronger statement:
— Even allowing complex weights, the only solutions for n=4 c=3 are equivalent (by some scaling and relabeling freedoms) to the “trivial” solution found with just non-negative real valued weights.

From this stronger conjecture, the n=4 conjecture then follows.
For if there were an n=4 c=4 solution, we could choose a subset of three colors and the constraints are such that considering only the weights with those three colors, it must be a solution for n=4 c=3.
If such a solution must be equivalent to the trivial solution, the three colors must use distinct perfect matchings in their constraint corresponding to a monochrome coloring.
As this must be true for any subset of three colors, the c=4 case is therefore impossible due to the pigeonhole principle. There are only 3 perfect matchings with n=4, so 4 colors cannot all have pairwise distinct matchings.

My approach to the problem was initially to do some brute force computer searches for some non-trivial n=4 c=3 solutions and then try building up to a c=4 counter example. But then I became increasingly convinced there were none, and so embarked on proving that.

I treat the problem focusing on the edge weights as a set of variables.
Labelling them as
w[nodeA, nodeB, color of nodeA, color of nodeB]
the weights obey
w[i,i,k,l] = 0 # no self links
w[i,j,k,l] = w[j,i,l,k] for all nodes i,j and colors l,k
So this means we have n(n-1)/2 variables in total.

The problem then gives a set of polynomial (multi-linear in the weights) constraints. There is one constraint for each coloring of the nodes, so there are c^n constraints.

After working out the symmetries of the problem, we can work out some conditions a non-trivial solution must have. As the problem constraints are already polynomials, this lends itself well to Groebner bases. While in principle any constraints forcing the solution to be non-trivial would be enough, it took awhile to find a set of constraints that could be computed without running out of memory. I currently have a constraint set for a non-trivial n=4 c=3 solution that Mathematica can calculate the basis in about 4 minutes (and I verified with Macaulay2 … but it took > 30 hours! for some reason).

So this is analogous to a computer proof via a SAT solver. It is not as satisfying as a simple argument by hand, but at least we know the answer now.

Scaling symmetries:

In addition to node relabeling and color relabeling symmetries, the problem also has what I call “scaling” symmetries.

The scaling symmetries in the n>4 problem took me awhile to find, but are obvious once you see them so I’ll share here.

Choose any two nodes i,j, and separate the weights into three sets like so:
set0 edge {i,j}
set1 edges other than {i,j} which touch node i
set2 edges other than {i,j} which touch node j
If a perfect matching has the edge from set0, it cannot have edges from set1 or set2.
Similarly, if the matching has an edge from set1, it must have an edge from set2, and vice versa. So if we scale all the weights in set1 by k, and all those in set2 by 1/k, all the constraint terms stay the same value.

This works for any pair of nodes.

So for example, we can see that an n=6 c=2 solution must have some non-zero term in each of the monochrome constraints. Without loss of generality, let’s take the term with w1211 to be non-zero, and then we can use the scaling freedom to set w1211=1. So the symmetry is exploited to break the problem down into a simpler concrete case.

As the sets of weights involved with the different scaling in n>4 are not distinct, care must be taken to not accidentally misuse these freedoms when fixing values to simplify the problem. In the n=4 case though, the scaling freedoms are completely isolated. The edges cleanly separates into 6 sets that pair off, providing three scaling freedoms that are completely independent.

Current thoughts:
Playing with all this awhile, it really feels like the “correct” phrasing of this problem is actually as some linear algebra (tensor) problem. Since the problem came from QM, this isn’t all that surprising. Since the constraints are multi-linear in the weights, this can always be reformulated as a tensor constraint.

In particular, for n=4 it felt something like there only being so many ways that vectors can be orthogonal before they just have to be zero. Eventually I found this math overflow post which made it more clear what is going on: https://mathoverflow.net/a/308341
The problem can be “linearized”. That is, we can promote the _terms_ in the constraints to variables, and because they are multilinear, this means a matrix of these terms must have rank 1. This is highly constraining, and as proved by mucking around with the constraints, all the multi-color weights get forced to zero.

I have hope someone else could prove that from linear algebra, and then extend it to to the n>4 case.

The other attack I can see is if the n=6 case was proved with more mucking about in the components, and then someone proves that an n>6 c=3 solution would imply an n=6 c=3 solution. I currently don’t know how to do either of those, but in some free time I’ll keep poking at the n=6 c=2 case.