Ramsey Theory on Structurally Balanced Graphs
Informally, Ramsey theory is the idea that complete disorder is impossible. As applied to graph theory, it states that for any numbers p and q, there exists a minimal number R(p,q) such that a complete graph(denoted Kn) on R(p,q) vertices, whose edges are colored red or blue, contains either a red complete graph of size p or a blue complete graph of size q. The number R(p,q) is called the Ramsey number. In general, only weak upper and lower bounds exist for these numbers; the exact value is only known for very small p and q (see the table in the Wikipedia page).
Now consider a complete graph Kn that obeys strong structural balance. Its vertices can be divided into two sets A and B such that every edge between nodes in A is (+), every edge between nodes in B is (+) and every edge between the two is (-). This is a 2-coloring of Kn (let (+) be red and (-) be blue). The largest blue complete subgraph is K2, or any single edge, so the Ramsey number isn’t particularly interesting. Intuition tells us that there must be a red Kp with p = floor(n/2); that is, one of the two groups is at least half the total number of nodes.
Weak structural balance, however, is more interesting. We want to find the smallest number n such that a weakly balanced Kn has either a red Kp or a blue Kq as a subgraph. Consider a complete graph with q-1 groups each having p-1 vertices, where every edge inside a group is red and every edge between two groups is blue. This graph is weakly balanced and contains no red Kp and no blue Kq. Now add a vertex. It must either go inside one of our groups, giving us a red Kp, or outside all the groups, forming a new group and therefore making a blue Kq. So R(p,q) = (p-1)(q-1)+1 for weakly balanced graphs. This says that in a group of at least this many people where everyone knows everyone and the relationship network is weakly balanced, there’s either a group of p friends or a group of q enemies. By imposing a single constraint, we have arrived at a simple closed form solution to an otherwise NP-hard problem.
http://en.wikipedia.org/wiki/Ramsey’s_theorem