1
$\begingroup$

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 path1 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.

1 'closed path'='graph-theoretic cycle'='circuit'='2-regular subgraph'

$\endgroup$
  • $\begingroup$ The sentence "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." does not make sense (to me), on a purely logical level: first you correctly remark that there are graphs with an odd number of circuits, then you say "maybe". The whole matter you are addressing in this sentence is that (to use your term) 'horribly imbalanced' graphs can exist only if for each $k\in\omega$, the number of $k$-circuits is even. Yes, this is a frighteningly restrictive necessary condition, yet trivially such graphs exist. $\endgroup$ – Peter Heinig Sep 2 '17 at 11:05
  • $\begingroup$ Terminological advice: it would be better to rename 'horribly imbalanced' and call it 'gradedly half-balanced', or something similarly neutral. $\endgroup$ – Peter Heinig Sep 2 '17 at 11:12
  • $\begingroup$ Related is this thread on expected number of circuits of given length. Note that this is mainly about approximate counts though. $\endgroup$ – Peter Heinig Sep 2 '17 at 11:28
  • $\begingroup$ @PeterHeinig You're right about the "half the number" blooper of mine. What I had in mind was an approximate approach where the balance is as close to half as possible, quantified asymptotically in terms of $d, k$ and $n$. And by "maybe", I meant that this deviation being constant might be too much to hope for. But yes, it could have been worded better, and I'll edit it soon. As for my terminology, I just came up with it ad hoc while typing the question, just to reflect my picture of it as some kind of polar opposite of balanced graphs. I'm happy to use more dignified nomenclature. $\endgroup$ – BharatRam Sep 3 '17 at 8:55
1
$\begingroup$

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 conditions1 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.

1 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.)

$\endgroup$
  • $\begingroup$ Thanks for the write-up. I apologize if I was unclear in the OP, so let me clarify what I meant. I am given a $d$-regular finite graph $G$ on $n$ vertices. By a closed walk, I simply mean a walk on the graph (repetitions of vertices and edges allowed), and so a closed walk is not a 2-regular subgraph but much more general than that. What I am looking for is a signing of the edges such that for each length $k$, the number of closed walks of length $k$ of sign $1$ is almost equal to the number of those with sign $-1$. The "almost" here, I'd like to quantify with the best possible error. $\endgroup$ – BharatRam Sep 3 '17 at 9:12
  • $\begingroup$ @BharatRam: Thanks for clarifying. I think that the (union of the edges of) any walk is an edge-disjoint union of 2-regular sugraphs(=circuits), and hence if a walk $W$ has sign $1$, then the number $a$ of $(-1)$-signed circuits 'in' $W$ must be even. However, $a$ must in fact be $0$ then, because each of those hypothetical circuits by itself is a 'walk', too, and you required all walks to have sign $1$. So I think: a signed graph $(G,\sigma)$ is balanced-in-your-sense if and only if it is balanced-in-the-traditional-sense. In short, your notion is the standard one. Do you agree? $\endgroup$ – Peter Heinig Sep 4 '17 at 11:38

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.