The waste product of my document scanning project is a slag heap of extracted staples:
The other day I made a discovery: If you grab one of the discarded staples and lift it, the whole ball of tangled, mangled metal comes along, leaving behind only a few stragglers in the bottom of the bowl.
When I noticed this, my first thought was “Hmm, that’s funny.” My second thought was “Oh, of course: Erdős-Rényi.” And my third thought–well, I’m still working on my third thought, as well as thoughts four, five and six.
Erdős and Rényi are Paul Erdős and Alfréd Rényi, who wrote a big paper on “The Evolution of Random Graphs” 50 years ago (Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 1960, 5:17–61). Their paper wasn’t quite the debut appearance of random graphs in the mathematical literature, but it’s usually cited as the theory’s point of origin.
In one version of the Erdős-Rényi process, you start with a set of n isolated vertices and then add random edges one at a time; specifically, at each stage you choose two vertices at random from among all pairs that are not already connected, then you draw an edge between them. It turns out there’s a dramatic change in the nature of the graph when the number of edges reaches n/2. Below this threshold, the graph consists of many small, isolated components; above n/2, the fragments coalesce into one giant component that includes almost all the vertices. “The Birth of the Giant Component” was later described in greater detail in an even bigger paper–it filled an entire issue of Random Structures and Algorithms (1993, 4:233–358)–by Svante Janson, Donald E. Knuth, Tomasz Luczak and Boris Pittel.
What made me think of a connection between Erdős-Rényi graphs and my hairball of staples? What I had in mind was something like this: The long, straight, middle part of a staple corresponds to an edge of a graph, and the bent end pieces, which can grab on to each other, are the vertices. Thus a single staple is a graph consisting of two vertices connected by one edge. When two staples hook up, two of their vertices merge and we’re left with a connected graph of three vertices and two edges. Since each staple contributes one edge and at most two vertices to the graph, the number of edges must be at least half the number of vertices. Thus the graph is always over the threshold for forming a giant component, according to Erdős and Rényi.
The counting part of this analysis seems okay, but I’m afraid the rest of it doesn’t hold up very well. Whatever is going on in the staple ball, the evolution of the system is not well modeled by the Erdős-Rényi process of adding edges to a fixed set of vertices. Instead, each staple brings both an edge and two vertices. The crucial event that makes the cluster hang together is the merging of vertices when staples link hands; this merging has no counterpart in the Erdős-Rényi process.
The underlying problem here is that Erdős-Rényi graphs are purely topological–there’s no concept of distance, and any two vertices are equally likely to have an edge joining them. But the staple graph has important geometric constraints. Two vertices can be joined by an edge only if the distance between them is approximately equal to the length of a staple.
The geometric structure suggests trying a different kind of model–perhaps the kind that describes the molecular structure of liquids and solids. Water molecules, for example, are linked together by a network of hydrogen bonds; each hydrogen atom in one molecule can bond to the oxygen atom in another molecule. But the bonds cannot extend over arbitrary distances; they reach only between neighboring molecules. In the resulting three-dimensional structure the basic motif is a tetrahedron with an oxygen atom at its center and hydrogen atoms at the four corners. (There’s also a schematic two-dimensional model known as square ice.) We might imagine something similar going on with the staples, where the two bent ends can form hydrogen-bond-like links to other nearby staples.
But there’s a problem with such chemical models as well. Atoms have a fixed valence (more or less–let’s not quibble); 
in water, for example, each hydrogen atom can form a hydrogen bond with only one oxygen atom. But we have no reason to suppose that the hooked ends of a staple can attach to only one other staple. As a matter of fact, if such a restriction were enforced, then the staples could form only chains and rings, not dense clusters. In a close look at the actual clusters, it’s easy to find places where three or more staples are all hooked together at the same point. By carefully teasing apart the cluster, I have spotted vertices that appear to have a degree of at least six.
Yet another physical process that might provide a model for the staple graph is diffusion-limited aggregation. This is the mechanism responsible for the filigree pattern in the banner at the top of the bit-player web page. It is generated by sticky particles that drift at random until they wander onto the substrate or touch another particle that is already in contact (directly or indirectly) with the substrate. For staples, I suppose the drifters would be tumbling dumbbells with sticky ends–somewhat harder to simulate.
Another factor to keep in mind is that spatial dimensions are surely important here. For one thing, there’s just more room to maneuver in three dimensions, with more opportunities to glom onto a neighbor. But in the specific case of staples, there’s another reason: Confined to a plane, they have a hard time linking up:
Dispersed on a flat plate, they refuse to coagulate even when swirled vigorously. The reason, presumably, is that secure links form only when the staples can turn 90 degrees and interlock.
In this connection it would seem significant that these are used staples, somewhat varied in shape, with hooked ends that had been bent approximately 180 degrees in the process of stapling and that mostly retained an angle greater than 90 degrees after being pried out the papers. I wondered how shiny new staples would behave, and so I tried the experiment. (Materials and methods: 630 Stanley Bostitch chisel-point staples, model SBS191/4CP, freshly dispensed from an open-jaw Swingline stapler.)
I was mildly surprised at the result. Although the aggregation was somewhat looser and more delicate, it really wasn’t that much different. Again we witness the birth of a giant component.
It might be worth repeating the shiny-new-staple experiment, pausing periodically as you add staples (say every 10 or 20 staples), giving a shake to what you’ve got in the bowl, and then seeing how large an aggegration comes with it when you pick up one of the staples. (It might be well to repeat the shake and aggegate step several times and look at the statistics of what you get.) My guess is that the (average) percentage of staples that lift with the tangle will be pretty small until the total number of staples in the bowl gets to a hundred or so, and then will start increasing toward something pretty close to 100%. Will it follow some sort of logistic curve? And if so, how steep?
In any event, it’s a wonderful observation!
Very beautiful work.
I wonder if the shape of the bowl plays a role.
I do understand flat plate experiment… but did you add the staples on top of each other (which gets kind of enforced when you add them in a bowl)?
Also I wonder what would happen if we add them in a more constrained container, say a test tube.
I guess you should look at the possibility of doing this with different office equipment, say paper clips. Also, does the staple size matter? Mix and match different types to form “alloys”. If you consider them as impurities in the ice, there might be a certain noticeable effect on the structure (is there an analog of the freezing point in ice? What are the changes in density?)
Necessarily, the size of the bowl has a role to play. It might even be possible to make the giant component in a nonconvex shape.
As for the structure itself, you might want to consider actually mapping it out as a graph, to study properties like subgraphs and cycles, as well as things like vertex density. Some glue might be added to preserve the structure, to make it easier to observe. Do the graph properties change if some other method is used to create the giant component, like using a magnet or magnetised scissors to stir up the mixture? How would this change if the staples are submerged in oil? What if they are heated or cooled in the middle of the process? What about vibration at different frequencies?
In terms of the size of the component, you might want to keep adding staples to see how far it can grow. Is it possible for two components to merge? And what applications might that have toward chemistry, or physics?
It may also be possible to recreate this experiment in the context of a social network. Similar effects will then be observable on different scales, or perhaps it will be totally different.
Thanks to Barry, to Yonkou, and to unekdoud for raising several interesting questions and suggesting further avenues to explore.
Before saying anything further, I would like to note that this is one of those rare instances in experimental science where anyone can play. The materials are readily available. You don’t need an NSF grant to finance the research (although I suppose we might seek funding from Staples, the office-supplies store). By all means: Grab the stapler and join in. In the spirit of scientific collaboration and zealous pursuit of the truth, I’m willing to share my stock of used staples.
Barry asks about the emergence of clustering in small populations of staples. I don’t know how that goes. With Erdos-Renyi graphs, the known results are strictly valid only in the limit of infinite n, but in practice infinity seems to be a pretty small number in graph theory.
unekdoud asks about the largest attainable clusters. Again I don’t know, but of course there must be a physical limit. At some point the weight of the cluster exceeds the strength of the single staple from which it’s suspended.
As for open questions about the shape of the bowl, the manner of stirring, the size of the staples, etc.: To the extent that these factors are important, we don’t really have a system that lends itself to clean analysis. I’d prefer to get out of this messy world of real metal staples and retreat into the tidier realm of a model we can simulate computationally or solve mathematically. But of course I don’t have such a model.
Finally, about paper clips. Those are the province of my American Scientist colleague Henry Petroski. He wrote the book on them, and I’m going to stay off his turf.
I think this kind of “research” is deeply cretinous, however I am truly grateful that some people engage in it, the same way I am grateful to video games addicts for boosting the development of high performance CPU chips.
The first thing I thought of when you started talking about random graphs was that the *flat* part of the staple should be a vertex, and the *ends* should be the edges - after all, the edges form the “bonds” you describe when discussing water molecules. The links between edges form randomly as the staples are deposited into the bowl, or as they’re stirred around in the bowl or something. Then, the change from two to three dimensions, from the surface to the bowl, changes the probability that a random bond forms between any two vertices. How exactly would require some thought, but presumably on a surface, the expected number of bonds is less than n/2, while in a bowl, it is greater.
My thought is that the staple as a whole is a vertex and an edge is formed when two staples get hooked on each other. That seems simpler than the proposed “merging” process. Wouldn’t we expect the concept of edge to be more about the relation between two objects than some crude physical analogue?
Pingback: Thanksgiving weekend miscellany — The Endeavour
I guess that a sort of entropic ratchet mechanism is (at least partly) responsible for the formation of the giant component:
there are many ways how two staples can hook up, but it requires a coordinated move to separate a pair of linked staples.
And I think that the same argument applies to the power cords in your drawer that always form a giant knot.
Pingback: Carnival of Mathematics #60 « ?idiot's Blog
I asked a friend of mine about whether people had studied this sort of phenomenon before and he pointed me to a recent American Physical Society March Meeting talk by Christopher LaSota (then at Kenyon College, now at Gonzaga).
http://meetings.aps.org/Meeting/MAR08/Event/78234
As far as I can tell he hasn’t published yet, but apparently he’s speaking about this again at this year’s March Meeting:
http://meetings.aps.org/Meeting/MAR10/Event/120147
concept is very interesting. I got the idea of giant component very easily.