Quantified imbalance in signed graphs

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. This is a more global notion of 'balance', graded by cycle lengths. 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:

1. Is such a notion meaningful?

2. Has it been studied anywhere already?

3. Let's assume, for simplicity, that the graph is $d$-regular. Then is there some bound on the margin of error, in terms of $n$, $k$ and $d$?

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

I must mention that I did post a slightly modified version of this question on stackexchange here https://math.stackexchange.com/questions/2345021/imbalance-in-a-signed-graph

Based on some offline feedback, maybe it is a better fit here. I did flag and contact the mods to inform them of the cross-post, but I apologize in advance if I am missing any etiquette and will rectify it if pointed out.

¹ _{'closed path'='graph-theoretic cycle'='circuit'='2-regular subgraph'}

Answer 1

Ad 1: I take this to ask for whether 'horribly imbalanced' graphs even exist, and, more generally, what can be said about the necessary conditions you imposed on them. This is what this answer/comment of mine addresses.

I take the liberty of renaming your notion to the less obtrusive 'graded half-balanced graph'.

It is known that, if $G$ is a finite undirected simple graph on vertex set $n$ with adjacency matrix $A=(a_{ij})\in\{0,1\}^{n\times n}$, then

• the total number of 3-circuits in $G$ equals

  $\frac16\mathrm{tr}(A^3)$

• the total number of $4$-circuits in $G$ equals

$\frac18\biggl(\mathrm{tr}(A^4)-\sum_{(i,j)\in n\times n} a_{ij} - \sum_{(i,j,\kappa)\in n\times n\times n\colon\ i\neq j}\ a_{i,\kappa}a_{\kappa,j}\biggr)$

Similar counting functions, i.e., polynomials ( with rational coefficients ) in the entries of the adjacency matrix, are known (and can be routinely calculated) for higher cycle lengths.

Let

$\mathsf{GradedHalfBalancedGraphs}_n\subset\{0,1\}^{n\times n}$

denote the set of all adjacency matrices of graded half-balanced graphs on $n$ vertices.

Since in your OP you require that the number of cycles of length $k$ be even for each $k$, we know a necessary condition for a 'graded half-balanced' graph (in your sense) and know the following equational necessary conditions¹ for the set of (adjacency matrices of) 'graded half balanced graphs'

$\mathsf{GradedHalfBalancedGraphs}_n$

$\subset$

${\tiny\{ A\in \{0,1\}^{n\times n}\colon A^{\mathsf{t}}=A\}}\qquad$ (symmetry)

$\cap$

${\tiny\{ A\in \{0,1\}^{n\times n}\colon \sum_{i\in n}a_{i,i}=0\}}\qquad$ (tracelessness)

$\cap$

${\tiny\{ A\in \{0,1\}^{n\times n}\colon \frac16\mathrm{tr}(A^3) \quad \equiv\ 0\ (\mathrm{mod}\ 2)\}}\qquad$ (even number of 3-circuits)

$\cap$

${\tiny \{ A\in \{0,1\}^{n\times n}\colon \frac18\biggl(\mathrm{tr}(A^4)-\sum_{(i,j)\in n\times n} a_{ij} - \sum_{(i,j,\kappa)\in n\times n\times n\colon\ i\neq j}\ a_{i,\kappa}a_{\kappa,j}\biggr)\quad\equiv\ 0\ (\mathrm{mod}\ 2)\}}\qquad$ (even number of 4-circuits)

Of course, this inclusion is very strict. And of course, the intersections go on and on, and the equations defining the sets get ever more complicated. This is not a characterization of your notion. And we haven't even begun to talk the signings into account. I am only giving you some relevant partial information.

¹ _{Only sort of 'purely equational': 'parity' statements like the one used here 'enlarge the signature of discourse', and are known to be 'usually' not definable by more primitive logic. (I am speaking vaguely here. Model theory knows much about 'parity quantifiers', which you might find useful to look into.)}