Among children of a certain age, everyone has a best friend—and exactly one. Ideally, the best-friend relationship is symmetric: If I am your best friend, then you are my best friend, too. But symmetry is not guaranteed, and it can happen that I like you best, but you have someone else you like better than me. Sad, but life is like that sometimes.
We can model best-friendship geometrically by letting distance—or, rather, nearness—stand for intensity of affection. Sprinkle a bunch of points at random on a plane, and then draw an arrow from each point to its nearest neighbor, which we take to be the point’s best friend. When the best friends are mutual, a bidirectional arrow links the two points. In other cases, a chain of arrows points from a to b to c and so on. Here is a best-friend graph constructed in just this way:
There are 100 dots in the diagram, which have spontaneously formed 30 constellations, or connected clusters. Some 40 of the dots represent disconsolate children who feel an attachment for someone who’s attached to someone else. (Note that some of the dots are so close that the arrows are obscured.)
Questions.
- In general, what proportion of the children in this model are stuck in unrequited best-friendships?
- How many clusters form, on average?
- How do these quantities vary as a function of the overall number of children?
- Adding a new child to the class or the neighborhood could disrupt some existing friendships: If a new point is inserted at a random position, how many existing bonds are likely to be broken or rearranged?
- What about the geometry and topology of the model? Would it make a difference if the points were plotted on the surface of a torus? Would the results be different in one dimension (with all the points arrayed along a line) or in three dimensions (with the points distributed throughout a volume of space)?
Note that the best-friend problem is not equivalent to the well-known stable-marriage problem (on which there is an extensive literature). In the stable-marriage situation, matchings are always two-by-two: If I like you best but you prefer someone else, then I simply have to find another partner.
For a rather different perspective on the mathematics of friendship (and also enmity) see Dynamics of Social Balance on Networks, by T. Antal, P. L. Krapivsky, and S. Redner.
The one-dimensional version should translate into a problem about random permutations. Once n + 1 numbers x0 ,…, xn have been chosen, say in [0,1], all that really matters is the ranking of the n distances x1 - x0, x2 - x1 ,…, xn - xn - 1, which will be a permutation of 1, 2 ,…, n. If 1 corresponds to the shortest distance and n to the largest, then each best-friend pair corresponds to a number in the permutation that is smaller than the numbers on either side of it.