17
$\begingroup$

motivated from a physical context, we are currently interested in the following graph coloring problem:

Given a connected graph $G_n$ with $n$ vertices, how many colorings exist such that all white vertices have an odd number of black neighbors? We call this number $\omega(G_n)$.

(To the best of our knowledge, this particular coloring problem has not yet been studied, but if you have seen something like this, please let us know!)

As an example, consider the cycle graph with four vertices. There exist five such colorings: Colorings of the line graph

In constrast, the fully connected graph of four vertices has nine such colorings: Colorings of the fully connected graph

Indeed, using completely different tools from physics, one can show that $\omega(G_n)$ is maximized by the fully connected graph, yielding the upper bound $\omega(G_n) \leq \begin{cases}2^{n-1} & n\text{ odd} \\ 2^{n-1}+1 & n\text{ even} \end{cases}$. Note that there is a total of $2^n$ colorings, thus, only about half of them can have the desired property.

Now we are interested in finding graphs that minimize $\omega(G_n)$ for a fixed number of vertices $n$. Exhaustively checking all connected graphs up to size 10 [Edit: this was a mistake, we only checked up to $n=8$. See Gordon's reply for a counter example with $n=9$ vertices] suggests that the graph minimizing $\omega(G_n)$ is given by the cycle graph of size $n$, but we have no clue on how to prove it.

Our questions are as follows: i) Is there an equivalent, similar or related graph coloring problem known in the literature? ii) Is there a graph theoretical argument that the cycle graph (among others) minimizes $\omega(G_n)$ for fixed $n$?

Lots of thanks in advance!

$\endgroup$
4
  • 3
    $\begingroup$ I forgot to mention that the conjectured lower bound by the cycle graph yields $\omega(G_n) = 1+\sum_{k=1}^{\lfloor \frac{n}{3} \rfloor} \frac{n}{k} \binom{n-2k-1}{k-1}$ $\endgroup$
    – Herimon
    Nov 5 '20 at 9:23
  • 1
    $\begingroup$ So am I correct in my calculations that the star $K_{1,n}$ and the complete graph $K_{n+1}$ both realise the upper bound? $\endgroup$ Nov 5 '20 at 12:11
  • 1
    $\begingroup$ A set $X$ of vertices of a graph is an odd dominating set or odd parity cover if for every vertex $v$ of the graph, the number of vertices in $X$ adjacent to or equal to $v$ is odd. There is a small literature on "odd domination" or "parity domination." Unfortunately this is not quite the same as your definition. $\endgroup$ Nov 6 '20 at 1:39
  • $\begingroup$ @TimothyChow Thank you for your comment. At a first glance, I see no immediate connection to our problem, but there are at least some results on the parity of neighborhoods that might be useful. I will have a closer look into that, thanks! $\endgroup$
    – Herimon
    Nov 10 '20 at 9:40
4
$\begingroup$

There is no graph-theoretical argument that the local equivalence class containing the cycle $C_n$ always minimises the value of $\omega$, because it is not true.

My smallest example is on 9 vertices with the following graph, which is just two pentagons merged at a single vertex.

2 pentagons merged at a vertex

This $9$-vertex graph has just 28 valid colourings, whereas $\omega(C_9) = 31$.

I verified this with some naive code in SageMath that simply tests each subset of the vertices of graph to see whether it can be the black vertices of a valid colouring - i.e., whether each vertex outside the subset is adjacent to an odd number of vertices in the subset.

def isValid(g,black):
    for v in g.vertices():
        if v not in black:
            val = len([w for w in g.neighbors(v) if w in black])
            if val % 2 == 0:
                return false
    return true    

def validSetList(g):
    return [s for s in Subsets(g.vertices()) if isValid(g,s)]

(I can't figure out how to enable syntax highlighting.)

Then the next couple of lines create the graph, call the function to return the list of valid sets, and determine how many there are:

h=Graph('HPXP?E@')
len(validSetList(h))

So I think the actual minimiser is going to be something like a bunch of 5-cycles merged at a single vertex, but I need to experiment some more.

$\endgroup$
1
  • $\begingroup$ Thank you Gordon for the great (and correct) observation. I was mistaken in my first post, when I claimed that we tested all graphs up to 10 vertices, as we only tested up to 8. It seems that your counter example suggests that the real minimizing graphs are more complicated than expected, which makes me a bit pessimistic that it can be constructed in all generality for arbitrary $n$, not to mention finding a proof... $\endgroup$
    – Herimon
    Nov 22 '20 at 12:45
4
$\begingroup$

@Gordon Royle: Yes, it is correct that $\omega(K_{1,n})=\omega(K_{n+1})$.

More generally, $\omega$ is invariant under local complementation (inverting the neighborhood of a vertex).

Also note that both the cycle graph $C_n$ and the line graph $L_n$ fulfill the recursive formula $\omega(C_n)=\omega(C_{n-1})+\omega(C_{n-3})$ and $\omega(L_n)=\omega(L_{n-1})+\omega(L_{n-3})$. However, the initial values are different:

$\omega(C_3)=4$, $\ \ \omega(C_4)=5$, $\ \ \omega(C_5)=6$

$\omega(L_3)=4$, $\ \ \omega(L_4)=5$, $\ \ \omega(L_5)=8\ \ $ (and $\omega(L_1)=1$, $\ \ \omega(L_2)=3$)

This shows $\omega(C_n)<\omega(L_n)$ for all $n \ge 5$.

You can find the proof of the recursion formula in Sec. 6.2.3 of my Master's thesis. (Sorry about the copy-paste typo in Corollary 14; the subscript should read "line" and not "star".)

$\endgroup$
1
  • $\begingroup$ Note to other readers (because I just got confused): "Local complementation" means picking a vertex $v$ and inverting each edge whose both endpoints are adjacent to $v$. ("Inverting" means removing the edge if it exists and adding it if it doesn't.) Edges incident with $v$ are not inverted. $\endgroup$ Nov 22 '20 at 14:14
0
$\begingroup$

Let me sketch a proof why $\omega$ is invariant under local complementation. (It is the quantum information scientist's point of view and can probably be avoided.) I use Bourbaki notation as it might be more convenient to read for people outside of physics; all tensor products should be understood as Kronecker products; I do not distinguish between a graph and its adjacency matrix.

  1. To each n-vertex graph $\Gamma$, there is an associated n-qubit state. This is nothing else but a normalized vector $v \in \mathbb{C}^2 \otimes_\mathbb C \mathbb{C}^2 \otimes_\mathbb C \ldots \otimes_{\mathbb C} \mathbb{C}^2 \cong \mathbb C^{2^n}$. We use the dyadic basis $\mathbf{e}_{0,\ldots,0,0},\ \ \mathbf{e}_{0,\ldots,0,1}, \ \ \mathbf{e}_{0,\ldots,1,0}, \ \ \ldots, \mathbf{e}_{1,\ldots,1}$ of $\mathbb C^{2^n}$. That is, the basis $\{\mathbf{e}_\mathbf{r } \ \vert \ \mathbf{r} \in \mathbb F_2^n \}$. Now, let $\Gamma = (\gamma_{i,j})_{i,j} \in \mathbb F_2^{n \times n}$ be the adjacency matrix of the graph. Then, the corresponding vector is defined as $$ v = \frac{1}{\sqrt{2^n}} \sum_{\mathbf{r} \in \mathbb F_2^n} (-1)^{\sum_{i=1}^n\sum_{j=i+1}^n \gamma_{i,j}r_i r_j }\mathbf e_\mathbf r .$$ That is, all entries are the same, except for, possibly a sign.

  2. The $n$-qubit Pauli group $G=\langle X_i,Y_i,Z_i \ \vert \ \ i\in\{1,\ldots,n\} \rangle $ is a group of $4^{n+1}$ matrices of size $2^n \times 2^n$. Thereby, the $X,Y,Z$ are the $2\times 2 $ Pauli matrices, and, given a $2\times 2 $ matrix $A$, we write $$A_i = eye({2^{i-1}}) \otimes A \otimes eye(2^{n-i}) $$ for the $2^n \times 2^n$ matrix that has matrix $A$ at position $i$ and the identity matrix $eye(2)$ at the other positions.

  3. We have a group action $G\times \mathbb C^{2^n} \rightarrow \mathbb C^{2^n}$. As it turns out, the stabilizer subgroup $$ H = \{ g\in G \ \vert \ g v = v \ \}$$ of $v$ (defined in 1.) is an elementary Abelian $2$-group of order $2^n$, i.e., $H\cong \mathbb F_2^n$, where the operation in $H$ is matrix multiplication and the operation on $\mathbb F_2^n$ is vector addition. The group $H$ is generated by the following $n$ matrices: $$ g_i = X_i \prod_{j=1}^n Z_j^{\gamma_{i,j}}, $$ where $i\in\{1,\ldots, n\}$. That is, for each vertex $i$, there is a stabilizer generator $g_i$ that has an $X$ at vertex $i$ and an $Z$ at each neighbor of $i$. Thus, the stabilizer group of $v$ can be parameterized as $$ H= \{ X^\mathbf{r} Z^{\Gamma \mathbf r}\ \vert \ \mathbf r \in \mathbb F_2^n \} $$ where $\Gamma \mathbf r $ is a matrix-vector product over $\mathbb F_2$.

  4. The number of b/w colorings correspond to the binary vectors $\mathbf r = (r_1,\ldots, r_n) \in \mathbb F_2 ^n$, where $r_i=0$ means vertex $i$ is white and $r_i=1$ means vertex $i$ is black. The number $$\omega(\Gamma) = \vert \{ \mathbf r \in \mathbb F_2^n \ \vert \ \forall i\in\{1,\ldots, n\}: r_i=1 \vee \sum_{j=1}^n \gamma_{i,j}r_j =1 \}$$ is the number of colorings for which each white vertex ($r_i=0$) has an odd number of black neighbors.

  5. The weight $ \mathrm{wt}(g)$ of an $n$-qubit operator $g = A_1\otimes \ldots \otimes A_n$, where $A_i$ are $2\times 2$ matrices is defined as $\mathrm{wt}(g):= \vert \{ i\in \{1,\ldots,n \} \ \vert \ A_i \neq eye(2) \}\vert$. It is well defined and for a unitary of the form $U= U_1\otimes \ldots \otimes U_n$, we have $\mathrm{wt}(g)=\mathrm{wt}(UgU^\mathrm H)$. The coloring problem can be rephrased as $$ \omega(\Gamma) = \vert \{ \mathbf r \in \mathbb F _2^n \ \vert \ \mathrm{wt}(X^\mathbf r Z^{\Gamma \mathbf r}) \} \vert = \vert \{ g \in H \ \vert \ \mathrm{wt}(g)=n \} \vert . $$

  6. If the graph $\Gamma$ is changed into a graph $\Gamma'$ via local complementation, the corresponding vectors $v$ and $v'$ differ by a unitary matrix $U$ of the form $U=U_1\otimes\ldots\otimes U_n$ for a particular choice of $2\times 2$ matrices (see Eq.(170)). This is remarkable as not every matrix in $GL(\mathbb C, 2^n)$ is of that form. Because of $v' = Uv$, we obtain $$ H' := \{ g'\in G \ \vert \ g' v' = v' \ \} = \{ UgU^\mathrm H \ \vert \ g \in H \}.$$ (See Lemma 2 for details.)

  7. The solution of the coloring problem is invariant under local complementation: \begin{align*} \omega(\Gamma' ) &= \vert \{ g' \in H' \ \vert \ \mathrm{wt}(g')=n \} \vert \\ &= \vert \{ UgU^\mathrm H \ \vert \ g\in H , \mathrm{wt}(g) =n \} \vert \\ &= \vert \{ g \in H \ \vert \ \mathrm{wt}(g) =n \} \vert \\ &= \omega(\Gamma) \end{align*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.