Skip to main content



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

Comments

Leave a Reply

Blogging Calendar

September 2012
M T W T F S S
 12
3456789
10111213141516
17181920212223
24252627282930

Archives