2
$\begingroup$

Given odd integers $0<a<b$, I want to know if there exists an $n$ by $n$ real valued square matrix $M$ such that $$ M_{ij} = M_{ji} \quad \forall i,j \in \{1,2\dots n\}$$ $$ \sum_{i=1}^n M_{ij} = 0\quad \forall j \in \{1,2\dots n\} $$ $$\operatorname{Tr}(M^a)\operatorname{Tr}(M^b) = \sum_{i=1}^n \lambda_i^a \sum_{i=1}^n\lambda_i^b < 0 $$ for some finite $n$.

If there always exists such an $M$, this would resolve a case which may lead to improving a result of Locally common graphs by Csóka, Hubai, and Lovász. In the paper's language, I am trying to prove that there always exists a balanced graphon $U$ such that $t(C_a,U)t(C_b,U)<0$. Proposition 4.3 proves a similar special case, where the two cycles are connected. Since they ignored the disconnected case, I suspect my problem may be trivial. I am not too familiar with manipulating the trace function, so I'm not sure.

$\endgroup$

1 Answer 1

0
$\begingroup$

In hindsight this was rather easy. If $G$ is an edge-weighted graph with adjacency matrix $M$, then the count of weighted homomorphisms of $C_k$ onto $G$ is equal to $\operatorname{Tr}(M^k)$.

It is sufficient to be able to construct graphs $G_{k-}$ (resp. $G_{k+}$) such that $C_k$ has only one embedding, which has negative (resp. positive) weight, with all other cycles being arbitrarily long.

To do this, you essentially just need to glue an arbitrarily long path to each vertex of $C_k$, and then glue all the ends of the paths together. The weighting is straightforward to handle afterwards. (give all but one edge of $C_k$ unit weight, and give the last edge weight $k-3$ for the positive case, or weight $-(k-1)$ in the negative case, and then alternate the path weights appropriately)

We have that $C_a$ cannot embed in $G_{b+}$, and $C_{b+}$ can embed only finitely many times into $G_{a-}$. Thus, for $N$ sufficiently large, defining $G$ to be one copy of $G_{a-}$ and $N$ copies of $G_{b+}$, the weighted embeddings of $C_a$ are negative while those of $C_b$ are positive, as desired.

$\endgroup$

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.