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?

literallywhat that means is that for each value of $X_i$, I have aseparatevariable $\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 '20 at 7:29