Return to Question

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_{X_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?

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?

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}=\frac{1}{\sqrt{8}}$ and $\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_{X_i,X_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_{X_i,X_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?

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_{X_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?

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 $X_i $ be indexed by an integer $1\leq i\leq n$, and $x_i \in \{ 0,1,\ldots ,c-1 \}$. We have variables $\omega_{X_i,X_j,x_i,x_j} \in \mathbb{C}$ (with $\omega_{X_j, X_i, x_j, x_i} = \omega_{X_i, X_j, x_i, x_j}$).

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

$$ \sum_{m=1}^{n!} \prod_{j=1}^{n/2} \omega_{X_{P^{(m)}(2j-1)}, X_{P^{(m)}(2j)}, x_{P^{(m)}(2j-1)}, x_{P^{(m)}(2j)}} = \prod_{i=1}^{n-1} \delta_{x_i,x_{i+1} } $$

where $P^{(m)}(k)$ denotes the $k$-th entry in the $m$-th permutation of $1,2,\ldots ,n$.

The only known cases are $c=2$ for each even $n$, and $c=3$ for $n=4$. One solution for $c=3$ for $n=4$ is $$\omega_{X_1,X_2,0,0}=\frac{1}{8}, \omega_{X_3,X_4,0,0}=\frac{1}{8}$$ $$\omega_{X_1,X_3,1,1}=\frac{1}{8}, \omega_{X_2,X_4,1,1}=\frac{1}{8}$$ $$\omega_{X_1,X_4,2,2}=\frac{1}{8}, \omega_{X_2,X_3,2,2}=\frac{1}{8}$$ and all other $\omega_{X_i,X_j,x_i,x_j}=0$.

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_{X_i,X_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_{X_i,X_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?

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}=\frac{1}{\sqrt{8}}$ and $\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_{X_i,X_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_{X_i,X_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?