Let $G=(V,E)$ be an $n$-vertex simple undirected graph. A signing of the graph is a function $s:E \to \{1,-1\}$, and $(G,s)$ is a signed graph. That is, we label each edge of the graph with $1$ or $-1$. The sign function, defined on edges, can be naturally extended to paths; the sign of a path is the product of the signs of the edges on the path. A path is said to be balanced if its sign is $1$. In other words, the path has an even number of $-1$-labelled edges.

The signed graph $(G,s)$ is said to be balanced if every closed path is balanced, and is called imbalanced otherwise. For instance, the trivial signing where we label each edge by $1$ is clearly a balanced signed graph. However, there are non-trivial signings that can be balanced too; for example, a bipartite graph where all edges are labeled $-1$.

There is much literature on balanced signed graphs and ways to balance them. However, I am curious about the polar opposite: "horribly imbalanced graphs", say (though this notion too is a different kind of "balance"). Let us call a graph "horribly imbalanced" if half the closed paths are balanced. More precisely, define:

A signed graph $(G,s)$ is said to be "horribly imbalanced" if for every $k$, exactly half the number of closed paths of length $k$ are labeled $1$.

Now it is possible that the total number of closed paths of length $k$ is odd, so maybe exactly "half the number" is hoping for too much. This looks related to discrepancy theory, so lets say the avg label of closed walks of length $k$ is $0$, with some error. My questions:

Is such a notion meaningful? Has it been studied anywhere already?

Lets assume, for simplicity, that the graph is regular. Then is there some bound on the error margin in terms of $n$, $k$ and the degree?

Given a regular graph, can we appropriately sign the edges so that the resulting signed graph becomes horribly imbalanced this way?


  • $\begingroup$ Closed paths are just cycles with repeated vertices allowed, yes? $\endgroup$
    – futurebird
    Jul 3, 2017 at 14:15
  • $\begingroup$ And if closed paths are cycles with repeated vertices then there are not a finite number in a graph with finite vertices so talking about half of them having any property becomes difficult I think? $\endgroup$
    – futurebird
    Jul 3, 2017 at 14:17
  • 1
    $\begingroup$ @futurebird I have noticed that there seems to be ambiguity in what "path","walk","cycle" etc refer to, and different contexts use slightly different definitions. But in this case, yes. A closed path is simply a sequence of adjacent edges starting and ending at the same vertex. $\endgroup$
    – BharatRam
    Jul 3, 2017 at 14:18
  • $\begingroup$ @futurebird That is why I graded them in terms of length. There are only finitely many closed paths of a given length $k$. In fact, this number is precisely $Tr(A^k)$ where $A$ is the adjacency matrix. $\endgroup$
    – BharatRam
    Jul 3, 2017 at 14:19
  • $\begingroup$ Ah that makes more sense. Thanks for clarifying the question. $\endgroup$
    – futurebird
    Jul 3, 2017 at 14:20

1 Answer 1


This is not quite an answer, but may be too long for a comment.

A signed graph corresponds to a $2$-cover or $2$-lift of the original (unsigned) graph: given a signed graph $G$, construct a graph $\widetilde{G}$ with two vertices $v_0, v_1$ for each vertex $v$ of $G$, and connect either $v_0,u_0$ and $v_1,u_1$ or $v_0,u_1$ and $v_1,u_0$ for any edge $\{u,v\}$ of $G$, depending on the sign of the edge $\{u,v\}$.

The graph $\widetilde{G}$ is clearly a $2$-cover of $G$ in the topological sense. Walks in $G$ lift uniquely to walks in $\widetilde{G}$ once a starting point is chosen in the appropriate fiber, and the "balanced" property of closed paths translates into whether or not the closed path lifts to two disjoint closed paths or a single one of double length.

In particular, the statistics of the number of balanced paths is controlled by the eigenvalues of $\widetilde{G}$, since $\text{Tr}(A^k)=\sum \lambda_i^k$ where the $\lambda_i$ are the eigenvalues of the adjacency matrix $A$. The eigenvalues of $\widetilde{G}$ are easily seen to comprise of the eigenvalues of $G$ along with a set of new eigenvalues, and the balancing requirement seems to require that these new eigenvalues be "small" in some sense, so the covering graph has few short cycles.

The new eigenvalues can't be too small due to known bounds (Alon-Boppana, Ramanujan Graphs). A paper of Bilu and Linial (Lifts, Discrepancy and Nearly Optimal Spectral Gap) shows how to use random signings, or random $2$-lifts, to create graphs with nearly optimal eigenvalues. I'm not entirely sure but I think it comes close to answering the question.

  • $\begingroup$ Hello @alon-amit ! In fact, this is exactly the path I took to reach this question in the first place. My (over-ambitious and foolhardy) aim is to make some headway with the Bilu-Linial conjecture, with inspiration from Lubotzky-Phillips-Sarnak type constructions. Especially since the existence seems almost established using the interlacing theory of Marcus-Spielman-Srivastava. You seem to have worked on this topic. What, in your opinion, is the barrier in adapting a riemann hypothesis from another context here? Are you aware of any interpretation of a d-regular graph as a curve/surface/etc? $\endgroup$
    – BharatRam
    Jul 17, 2017 at 16:43
  • $\begingroup$ @BharatRam: Re "Are you aware of any interpretation of a d-regular graph as a curve/surface/etc?": one such interpretation are ribbon graphs. Not sure whether this is even remotely an interpretation useful to you. $\endgroup$ Sep 2, 2017 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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