3
$\begingroup$

A certain question on graph theory (about the existance of graphs with a certain coloring inherited by perfect matchings) can be translated into the satisfiability problem of a certain set of equations (formulated by Michael Engelhardt).

Let $1\leq i\leq n$, $v_i \in \{ 1,2\ldots ,n \}$ and $x_i \in \{ 0,1,\ldots ,c-1 \}$. We have variables $\omega_{v_i,v_j,x_i,x_j} \in \mathbb{C}$ (with $\omega_{v_j, v_i, x_j, x_i} = \omega_{v_i, v_j, x_i, x_j}$ and $\omega_{v_i, v_i, x_j, x_i} = 0$).

For a fixed $n$ and $c$, we ask whether there is a set of $\omega_{v_i,v_j,x_i,x_j}$ which solves the following set of equation for every value of the varibles $x_i$:

$$ \sum_{\sigma \in S_n} \prod_{j=1}^{n/2} \omega_{\sigma(2j-1), \sigma(2j), x_{\sigma(2j-1)}, x_{\sigma(2j)}} = \prod_{i=1}^{n-1} \delta_{x_i,x_{i+1} } $$

where $S_n$ is the symmetric group.


n=4, c=2: Find a set of $4^2 2^2=64$ values of $\omega_{v_i,v_j,x_i,x_j}$ which satisfying these $2^4=16$ equations:

  • $x_1=0,x_2=0,x_3=0,x_4=0$:

$$\omega_{1,2,0,0} \omega_{3,4,0,0} + \omega_{1,2,0,0} \omega_{4,3,0,0} + \omega_{1,3,0,0} \omega_{2,4,0,0} + \omega_{1,3,0,0} \omega_{4,2,0,0} + \omega_{1,4,0,0} \omega_{2,3,0,0} +\omega_{1,4,0,0} \omega_{2,3,0,0} + \omega_{2,1,0,0} \omega_{3,4,0,0} + \omega_{2,1,0,0} \omega_{4,3,0,0} + \omega_{2,3,0,0} \omega_{1,4,0,0} + \omega_{2,3,0,0} \omega_{4,1,0,0} + \omega_{2,4,0,0} \omega_{1,3,0,0} + \omega_{2,4,0,0} \omega_{3,1,0,0} + \omega_{3,1,0,0} \omega_{2,4,0,0} + \omega_{3,1,0,0} \omega_{4,2,0,0} + \omega_{3,2,0,0} \omega_{1,4,0,0} + \omega_{3,2,0,0} \omega_{4,1,0,0} + \omega_{3,4,0,0} \omega_{1,2,0,0} + \omega_{3,4,0,0} \omega_{2,1,0,0} + \omega_{4,1,0,0} \omega_{2,3,0,0} + \omega_{4,1,0,0} \omega_{3,2,0,0} + \omega_{4,2,0,0} \omega_{1,3,0,0} + \omega_{4,2,0,0} \omega_{3,1,0,0} + \omega_{4,3,0,0} \omega_{1,2,0,0} + \omega_{4,3,0,0} \omega_{2,1,0,0} = 1 $$

Because of $\omega_{v_j, v_i, x_j, x_i} = \omega_{v_i, v_j, x_i, x_j}$ , it simplifies to

$$\omega_{1,2,0,0} \omega_{3,4,0,0} + \omega_{1,3,0,0} \omega_{2,4,0,0} + \omega_{1,4,0,0} \omega_{2,3,0,0} = \frac{1}{8} $$

  • $x_1=1,x_2=0,x_3=0,x_4=0$: $$\omega_{1,2,1,0} \omega_{3,4,0,0} + \omega_{1,3,1,0} \omega_{2,4,0,0} + \omega_{1,4,1,0} \omega_{2,3,0,0} = 0 $$

  • $x_1=0,x_2=1,x_3=0,x_4=0$: $$\omega_{1,2,0,1} \omega_{3,4,0,0} + \omega_{1,3,0,0} \omega_{2,4,1,0} + \omega_{1,4,0,0} \omega_{2,3,1,0} = 0 $$

  • $x_1=1,x_2=1,x_3=0,x_4=0$: $$\omega_{1,2,1,1} \omega_{3,4,0,0} + \omega_{1,3,1,0} \omega_{2,4,1,0} + \omega_{1,4,1,0} \omega_{2,3,1,0} = 0 $$

$\ldots$

  • $x_1=1,x_2=1,x_3=1,x_4=1$: $$\omega_{1,2,1,1} \omega_{3,4,1,1} + \omega_{1,3,1,1} \omega_{2,4,1,1} + \omega_{1,4,1,1} \omega_{2,3,1,1} = \frac{1}{8} $$

One solution is: $\omega_{1,2,0,0}=\omega_{3,4,0,0}=\omega_{1,3,1,1}=\omega_{2,4,1,1}=\frac{1}{\sqrt{8}}$ and all other $\omega_{v_i,v_j,x_i,x_j}=0$.

Another simple solution can be obtained (n=4,c=3).


Question 1: Does this set of equation have solutions other than $(n,c=2)$ and $(n=4,c=3)$?

It seems likely that the answer to this question is no, because

  • For the special case of $\omega_{v_i,v_j,x_i,x_j} \in \mathbb{R_+}$, Ilya Bogdanov has proved that these are the only solutions, using graph theoretical methods.
  • The number of equations that need to be fulfilled grow as $c^n$, while the number of free variables $\omega_{v_i,v_j,x_i,x_j}$ grow only as $c^2\frac{n(n-1)}{2}$.

Even through, no answer is known for any other case.

Question 2: Have you seen any similar or related equation systems or problem in general before?

$\endgroup$
  • $\begingroup$ The notation is strange. If I said $X_i$ is a variable, and $\omega_{X_i}$ is a variable, then literally what that means is that for each value of $X_i$, I have a separate variable $\omega_{X_i}$. If $X_i = 5$, then there is a variable $\omega_5$. If $X_i = -3$, then there is a variable $\omega_{-3}$. This cannot possibly be what you intended. If you clarify this, I think the whole question might be easier to read. Also: Please consider summing over $\sigma \in S_n$, the symmetric group, and writing $\sigma(j)$ instead of $P^{(m)}(j)$. ... $\endgroup$ – Zach Teitler Apr 20 at 7:29
  • $\begingroup$ ... I don't completely understand why you need $\omega_{X_i,X_j,x_i,x_j}$. Could you just write $\omega_{i,j}$ and have the same information? Or not? I'm sorry to ask such stupid questions, but I just find the notation confusing. Would you be willing to write out the full system of equations for a small case, say $n=c=2$? $\endgroup$ – Zach Teitler Apr 20 at 7:31
  • 1
    $\begingroup$ @ZachTeitler Your understanding of variables notation is correct. An example of a full system (for $n=4$ and $c=2$) on which you ask is provided in this question. $\endgroup$ – Alex Ravsky Apr 20 at 17:27
  • 1
    $\begingroup$ @ZachTeitler Thanks for your comment, i updated the question now, improved the notation according to your suggestion, thank you! Also added the n=4,c=2 example following exactly the notation used here. Does that help? $\endgroup$ – Mario Krenn Apr 21 at 8:30
1
$\begingroup$

My answer concerns Question 2. When I was dealing with the system for $n=4$ I noticed that we can split it as follows (unfortunately, I failed to obtain essential advances from this observation).

Let $m=3$ and $X$ be an $m$-dimensional complex linear space with a basis $e_1, \dots, e_m$. Let $X^*$ be the dual space of the space $X$ (that is, the space of all complex-valued linear functionals on $X$) with the basis $e^*_1, \dots, e^*_m$ which is dual to $e_1, \dots, e_m$, that is satisfying the condition $e^*_i(e^j)=\delta_{i,j}$ for each $1\le i,j\le m$. Given values $\omega_{X,Y,x,y}$ for each $1\le X<Y\le n$ and $1\le x,y\le d$, each coloring $c$ of $[n]$ into $d$ colors provides vectors $x(c)\in X$ and $x^*(c)\in X^*$ such that

$$x(c)=\omega_{12, c(1)c(2)}e_1+\omega_{13, c(1)c(3)}e_2+\omega_{14, c(1)c(4)}e_3,\tag{1}$$

$$x^*(c)=\omega_{34, c(3)c(4)}e^*_1+\omega_{24, c(2)c(4)}e^*_2+\omega_{23, c(2)c(3)}e^*_3, \tag{2}$$

and $x^*(c)(x(c))$ equals $1$, if $c$ is monochromatic, and equals $0$, otherwise.

A next step to solve the system can be to find necessary and sufficient conditions when a family $\{x(c): c:[n]\to [d] \}\subset X$ of vectors can be expressed in the form (1). A necessary condition is that for any natural $k$ and any two sequences $(c_1,\dots, c_k)$ and $(c’_1,\dots, c’_k)$ of colorings $[n]\to [d]$ such that for each $1\le Y\le n$ and $1\le x,y\le d$ holds $$|\{j: c_j(1)=x\mbox{ and } c_j(Y)=y\}|=|\{j: c’_j(1)=x\mbox{ and } c’_j(Y)=y\}| $$

we have $\sum_{j=1}^k x(c_j)=\sum_{j=1}^k x(c’_j)$.

A similar necessary condition is when a family $\{x^*(c): c:[n]\to [d] \}\subset X^*$ of vectors can be expressed in the form (2).

I don’t know whether these conditions are sufficient. On the other hand, maybe based already on these condition it can be proved that in some cases the initial system has no solutions.

I have a weak hope that for bigger $n$ we can similarly split the system using tensor products, but I’m not a specialist in this domain.

PS. I still think that if we find a way to essentially use the symmetry of the system then it can be enlightening. So maybe a book “Symmetry in Physics” (Macmillan, 1979) by J.P. Elliott and P.G. Dawber can be helpful.

| cite | improve this answer | |
$\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.