That is, if you have a connected graph of N vertices, and each vertex connects to the other vertices, you will have a total of (N-1)*N/2 = (N**2 - N)/2 edges = O(N**2) edges.
Usually, maintaining a network shaped in a connected graph is tied to the cost of the edges. Thus, the maintenance cost grows faster than linear (O(N)). This is a problem because you can only grow the amount of energy you put into the network linearly if the vertices acted independently.
One such example are societies where the vertices are people and the edges are relationships. The ConnectedGraphSquaringProblem in this context describes why "friendship" doesn't hold a large society together: Since maintaining friendship requires time and (emotional) energy, people cannot maintain an infinite number friendships. Therefore, as the society grows, the fraction of friends each person has decreases.
Clearly the solution is to maintain the network non-independently, thus taking advantage of the O(N**2) connectivity rate. Invert the problem, in other words. But what are good ways to build a maintenance network, especially in the context of CollaborativeHypermedia?
See also MetcalfesLaw, CommunityMayNotScale, LearningExploitationTradeOff
Also note that ReedsLaw takes this even further, into what could be called the "Power set exponentiation phenomenon."
What feature of the network is critical to you in this application?
Maintenance of the minimal spanning tree is computationally cheap, and keeps you connected, provided you don't have to generate all O(N**2) links and discard from that set. So look for a heuristic that gives you an O(N Log N) subset of the O(N**2) links containing "high scoring links" to build your subnet from. You may not find a perfect heuristic, but this is unlikely to matter. Your network is going to need to be resilient in any case. --JamesCrook
Really, you want the O(N^2) power of the graph helping you, and only the O(N) or O(NlgN?) power of subgraphs working against you. For instance, you want the bandwidth cost for broadcasting to be O(N), but once all the nodes have the message, you want that O(N^2) working to solve the problem.
In the case of Wiki, some links happen all on their own, in the form of AccidentalLinking. A good (maybe semantics-aware) AutoLink feature would push that phenomenon even further. -- MichaelSparks?
... O(N**2) cost of maintaining ... In real world systems you never have this situation. E.g. in molecular systems you have short range forces (only towards 3-6 neighbours) while long range forces only apply to special cases (and their calculation can be simplified). So this seems more a theoretical problem than a practical problem.
The reason why atoms destabilize past 168 protons is unrelated to the ConnectedGraphSquaringProblem. It is, however, an example of something else: The attraction between vertices and the repulsion between vertices as a function of N behave differently: For higher numbers of N, the attraction drops and the nucelus becomes unstable.
Here's the physical background:
Such atoms are not unstable from electrical forces between protons and electrons (which are capable of holding large things together with no trouble, for the same reason that the huge number of interacting particles contribute together to the earth's gravity.) The problem with building an atom with more than 200 protons has nothing to do with there being too many proton-electron interactions. The problem is that the nucleus becomes unstable, and that not because of too many attractive forces, but because of too few. Protons repel each other from electrical repulsion. In addition, protons and neutrons all have an attractive force towards each other at sufficiently small scales. Finally, neutrons are inherently unstable; left alone, they decay, but if they are closely bound to other neutrons or protons, then the decay is staved off. So atoms tend to have roughly as many neutrons as protons. More than that, and the neutrons would decay (beta-decay). Fewer than that and the repulsive force between protons blows the nucleus apart (producing either alpha'''Problem: In decay or fission). If you try to get way too many protons in a nucleus, a new problem happens: because the strong nuclear force (which binds the protons and neutrons to each other) operates only at very small scales, and the electric repulsion operates over arbitrarily long distances, it becomes impossible to overcome the electric repulsion once the nucleus gets to big. --ThomasBushnellBSG
So, Protons = Fanatics, Neutrons = Followers, Electrons = Nay-sayers? --WilliamUnderwood