Consider a system of linear equations of variable $x=(x_1,\cdots,x_n)$ where each $x_i\in\{ 0,1,\cdots,L-1 \}$. Clearly, there are $\frac{n(n-1)}{2}$ number of equations in the system.

$$x_i-x_j=0, \ \forall i,j \in \{1,\cdots,n\}, i<j$$

**My question.** For general $n$, what are the possible numbers of satisfied equations for $x\in\{ 0,1,\cdots,L-1 \}^n$? And, for each possible number, which equations can be satisfied?

**Example.** When $n=4$. The possible number $N$ of satisfied equations can be $N=0,1,2,3,6$.

(1) $N=0$. This means no equation is satisfied, i.e. $x_1,\cdots,x_4$ take $4$ different values, thus the number of configurations of $(x_1,\cdots,x_4)$ is $A(L,4)$, where $A(L,4)=C(L,4)\times 4!$.

(2) $N=1$. This mean only one equation is satisfied, then the number of configurations is $A(L,3)\times C(4,2)$. Specifically, since we constraint certain $x_i=x_j$, there are $3$ distinct values. Thus there are $A(L,3)$ ways to choose $3$ **ordered** distinct values from $\{1,\cdots,n\}$. Moreover, there are $C(4,2)$ ways to choose $(i,j)$ such that $x_i=x_j$. Thus overall, there are $A(L,3)\times C(4,2)$ configurations. We could also interprete this as the following graph, where each node represent a $x_i$ and two nodes $(i,j)$ are connected means that $x_i=x_j$:

(3) $N=2$. This means two equations are satisfied, then the number of configurations is $A(L,2)\times C(4,3)+A(L,2)\times C(4,2)$. See the second graph in the case $N=2$.

(4) $N=3$. This means $3$ equations are satisfied. $A(L,2)\times C(4,1)$. We could also think in the way of connecting nodes as follows: given $4$ nodes. We connect $3$ edges since $N=3$, and there are $3$ ways to connect them as follows (the blue solid lines).

The second and third one does not give any configuration, since for example, $E_1$ and $E_2$ means the $x_i$ associated with the connected three nodes are equal, then the dashed red line must exist as well.

(5) $N=4$. This means $4$ equations are satisfied. There is no configuration corresponding to this case, since if there are $4$ equations satisfied, we must have additional equation to be satisfied as well.

(6) $N=5$. This means $5$ equations are satisfied. There is no configuration corresponding to this case.

(7) $N=6$. This means $6$ equations are satisfied which means all $x_i$ are equal. Thus there is $A(L,1)$ configurations.

**From this simple example, it seems that this problem can be transferred as:**

Given $n$ nodes. How to connect $N$ edges such that in the graph there is **no three-vertex induced path** (otherwise there must exist another edge to connect the two end points of the chain). For each way, there will be $A(L,\text{Num of connected components})\times C(n,\text{isolated nodes})$ configurations.

It seems this problem seems quickly unfeasible when $n$ grows larger.. (not sure)

**If this problem is hard,**

- could we expect that considering some special graph structure such that the problem can be solved?** i.e. consider

$$a_{ij}(x_i-x_j)=0, \ \forall i,j \in \{1,\cdots,n\}, i<j$$ where $a_{ij}$ are elements of adjacency matrix of the graph.

**[Update: If consider triangle-free graphs, for example, complete bipartite graph (with $m,n$ nodes), then the number of $a_{ij}(x_i-x_j)=0$ can be $0,1,\cdots,mn$.**

- Or is there any other way to add constraints to make this problem is explicitly solvable?

8more comments