## 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 K_{n}) 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 K_{n} 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 K_{n} (let (+) be red and (-) be blue). The largest blue complete subgraph is K_{2}, or any single edge, so the Ramsey number isn’t particularly interesting. Intuition tells us that there must be a red K_{p} 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 K_{n} has either a red K_{p} or a blue K_{q} 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 K_{p} and no blue K_{q}. Now add a vertex. It must either go inside one of our groups, giving us a red K_{p}, or outside all the groups, forming a new group and therefore making a blue K_{q}. 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