Imbalance in a Signed Graph

Question

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?

Thanks.

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.