1
$\begingroup$

Assume a complete undirected graph $G'=(\mathcal{V}',\mathcal{E}')$ and the partirion function:

$$\sum_{\boldsymbol{x}\in \{-1,+1\}^n} \prod_{\left(i,j\right)\in \mathcal{E}'} \left[1+x_{i}x_{j}\theta_{i,j}\right],\quad \theta_{\emptyset}=0$$ I would like to expand the product and then sum to find the expanded form of the partition function and I noticed that the only terms which will not sum up to zero after the summation are those for which $$\prod_{(i,j)\in \epsilon }x_i x_j \theta_{i,j}=\pm \prod_{(i,j)\in \epsilon }\theta_{i,j} \quad \forall x_i x_j \in\{-1,+1\} $$ for all the subsets $\epsilon \subset \mathcal{E}$, otherwise the corresponding product will sum up to zero after the summation. Then I tried to solve the equation above and we have the following: find the relationship between $i,j$ for all the pairs $(i,j)$ such that $$\prod_{(i,j)\in \epsilon }x_i =\pm \prod_{(i,j)\in \epsilon } x_j\quad \forall x_i x_j \in\{-1,+1\}$$. It seems like for each $x_i$ which participates to left handside $m$ times should appear $m$ times to the right as $\pm x_{i}$. My intuition is that the graph which is formed from all the edges of each set $\epsilon \subset \mathcal{E}$ such that the above equation is satisfied is a graph with (disconnected) cycles (two regular). To solve this I think it is sufficient to solve the following:

Let $G=(\mathcal{V},\mathcal{E})$ be an undirected graph with $\mathcal{E}=\{(i_r,j_r)$: for $r\in\{1,2.\ldots,R\}\}$. Assume that the sequence of indicies $i_1,i_2,\ldots,i_R\in\mathcal{V}$ is a permutation of $j_1,j_2,\ldots,j_R\in\mathcal{V}$ and not all the permutations are allowed since : it can not exist an edge of the form $(i,i)$ and $(i,j)\equiv(j,i)$. Is it always true that the Graph $G$ is a Hamiltonian cycle or a collection of (disjointed) hamiltonian cycles?
Since I can not find a counterexample I am trying to prove it as follows: Consider the permutation mapping $M:I \rightarrow J$ then for any $(i_k,j_k)\in \mathcal{E}$ we have $(i_k,j_k)=(i_k,M(i_k))$ and we can write the edges in the following order:$$(i_k,M(i_k)),(M(i_k),M(M(i_k))),(M(M(i_k)),M(M(M(i_k)))),\ldots, (M^{R}(i_k),i_k)$$. Is this sufficient?

$\endgroup$
5
  • $\begingroup$ Am I missing something? It seems to me that $M(M(i))=i$ for every $i$, as the graph is supposed to be undirected. $\endgroup$ Mar 17, 2018 at 22:35
  • $\begingroup$ for example: $i_1\rightarrow j_1 \equiv i_{10}$ , $i_{10} \rightarrow j_{10} \equiv i_3$, $i_3 \rightarrow j_3 \equiv i_5$ and we have $M(i_1)=i_{10}$, $M(M(i_1))=i_3$ notice that the mapping is from i's to j's and you can not have $M(M(i))=i$ since $(i,j)\equiv (j,i)$ $\endgroup$
    – Cauchy
    Mar 19, 2018 at 0:51
  • $\begingroup$ you can walk the other direction by applying $M^{-1}(j)$ where $M^{-1}:J \rightarrow I$ $\endgroup$
    – Cauchy
    Mar 19, 2018 at 2:03
  • $\begingroup$ What does "fully connected" mean? (This is not a usual technical term.) $\endgroup$ Mar 19, 2018 at 7:59
  • $\begingroup$ Sorry, I mean complete thank you for pointing that out. $\endgroup$
    – Cauchy
    Mar 19, 2018 at 15:59

1 Answer 1

1
$\begingroup$

Note that every $2$-regular finite simple graph is a collection of disjoint cycles so it is sufficient to show that the graph is $2$-regular.

$\endgroup$
4
  • $\begingroup$ Can you explain to me how to do this? $\endgroup$
    – Cauchy
    Mar 19, 2018 at 0:57
  • $\begingroup$ Actually, you cannot get the conclusion you want unless you demand that $i_k$ equals $j_l$ => $j_k$ is not equal to $i_l$. Otherwise, the chosen pair of permutations spans fewer edges than desired and at least one vertex has degree less than $2$. $\endgroup$ Mar 19, 2018 at 19:02
  • $\begingroup$ yes, I think that I have assumed that since not all the permutations are allowed. I am not sure what exactly you mean. $\endgroup$
    – Cauchy
    Mar 19, 2018 at 19:11
  • $\begingroup$ With the additional hypothesis you can prove the statement as follows: For any appropriate choice of two permutations $i$ and $j$, the edge set of graph $G$ has $R$ elements : {$i_1, j_1$}, ... , {$i_R, j_R$}. Observe that for every positive integer $k$ smaller than or equal to $R$ , $i_k$ is different from $j_k$ so none of these pairs is actually a singleton. Now let $l$ be any positive integer smaller than or equal to $R$. How many times does l occur in our collection of pairs ? $\endgroup$ Mar 19, 2018 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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