I have a question about the math of self-sorting behavior in groups.
Let’s say I have a high school band of 60 kids. All band kids are introverts who only know x number of other kids from their own band - to start with, we’ll say that *x *= 10. I take the band to a band convention in the big city, where they mingle with 29 other bands to form a superband of 1800 kids. At the end of the day, the superband breaks up. A band kid will spot one of the 10 people she knows and move toward that person, who is moving toward one of the 10 people he knows, who is moving toward one of the 10 people she knows, etc. There may be other rules needed which I’m kind of ignoring. But by this process the original 30 bands reform.
I’m curious about the math of this sort of process. Naively, it seems that if x is 60, the bands will easily reform perfectly. If x is 1, there will probably be a some pairs forming that don’t know what band they belong to, as well as a distribution of subgroups with up to 60 members. Somewhere in between those extremes is a magic x where, say, half of the bands reform properly. What branch of mathematics addresses this type of situation, and is the magic number closer to 1 or 60?
The other problem is - how do you guarantee that in the band all subsets of 10 (or is it 11?) intersect? At the end of the day, a band of 60 might end up as two separate groups where nobody from group A knows anyone from Group B or vice versa?
Now in a group of 1800, what geographical restriction makes all the sub-groups eventually find each other, you don’t end up with half the band by the south entrance and half by the north entrance? Presumably everyone converges to roughly the same point at the end of the day?
Definition of problem needs to be better…
(I.e. with friends=x, group=60 what are the odds of distinct not-overlapping subgroups?)
Assuming that we’re not considering any kind of line-of-sight issues, and all band members can see all the people they know (maybe they all have GPS sharing on their phones with their x friends), this is a graph theory/combinatorics problem.
You have a graph with 60 nodes (students) each of which have 10 edges connected (know-relationship). Depending on whether you want the “knows” relationship to be symmetrical (if Alice knows Bob, does Bob know Alice), then the edges may be directional. It sounds like you’re thinking it’s asymmetric, because if it’s symmetric, then n=1 will always leave you with 30 2-person pairs.
Then there’s a combinatorics problem: What fraction of such graphs are fully connected. I don’t have a neat closed-form solution to this but it’d be easy enough to do a Monte Carlo simulation. WAG: It’s way closer to 1 than 60.
Let’s assume that the ‘knows’ are random, so if Alice knows Bob, there is an x/60 chance that Bob also knows Alice.
The 1800 students mill around a common area until the group that each person is in contains all the people that that person knows; then each group stops looking for friends and looks for a bus ;). People do not leave groups once they are in them. Perhaps the group moves toward the closest person not yet in-group that at least one member of the group recognizes.
The good news: This sort of stuff is studied in Ramsey Theory. The bad news: there are problems in this field that are really, really, amazingly, gawd-awful hard. 60 people and subsets of 10? That’s very far off the chart of what is known.
And this is a preliminary sub-problem to the OP’s question.
No, lots of the OP’s question isn’t nearly that hard. It’s trivially easy to answer by the description in your link “Problems in Ramsey theory typically ask a question of the form: “how many elements of some structure must there be to guarantee that a particular property will hold?”” The answer is 30. If each person knows 30 other people, then the band is sure to reform, and if each person knows 29 others, then it might not.
The second claim is easy to show. If persons 1-30 know each other and no one else, and persons 31-60 know each other and no one else, you will get a terminal 2 groups. There’s no way to construct such a division if each person knows 30 others.
The specific question the OP asked about how large N has to be for half such bands to reform isn’t that hard either, and is easily simulated. The math is left as an exercise to the reader or until I have an hour of free time and the desire to hack something together.
I hadn’t thought of it in terms of everyone needing, at most, to know just over half of the members of their group in order to self-assemble with 100% reliability. Neat!
I was thinking about it more along the lines of probability after giving some more thought - if A has a bond with 10 others picked randomly from 60; and each of those has a bond with 10 others, picked randomly… Then B knows A and 9 others (I presume these are 2-way bonds). for each of those 9, there’s a 5-in-6 chance that the person is not known to A. This becomes the 6-degrees-of-separation game, where A is Kevin Bacon.
Count bonds, not groups. There are N(N-1)/2 possible bonds in a group. So in 60 people, 6059/2=1770 bonds. In 30 or less, a max of 3029/2= 435 bonds. What are the odds when picking a set of bonds for a group of 30 that none of them were picked from the pool of 60? I’m guessing it’s in the neighbourhood of 30!/60! off the top of my head. That’s a factorial guess if ever there was one.
Yes, if the number of acquaintances was 29, there’s what - 60 possible arrangements out of 60! where the band will not congregate. (Coagulate?)
There are way more than 60 ways to have a group of 60, each of whom knows 29 others (asymmetrically) not reform. There are 60C30 ways, or approximately 1.2e17 ways to choose 30 people to be in a subgroup from 60.
For those not familiar with nCk, it’s read “n choose k” and it is the number of ways to choose k objects from n distinct objects without replacement, and is n!/(k!*(n-k)!).
To know the probability, we have to know how many total ways there are to choose the bonds. There are 6059=3540 bonds, but we can’t just choose 6029=1740 of them, because that would just make the average number of known people be 29, not the exact number for each person.
I believe the correct number here is (59C29)^60. That is, for each of 60 people, choose 29 of their possible 59 bonds. Wolfram Alpha tells me that that’s 2e1006.
In general, the number of ways to have n people who know k other is (n-1 choose k)^n. So that’s our denominator for a probability calculation.
It feels like that should get us close to a general closed form solution, but I haven’t figured out the numerator.
I just spent an hour making graphs of smaller groups in which each person only knew one other, and finding interesting things about closed subgroups vs. groups with ‘tails’, when I realized that I was assuming that everyone was known by at least one person. So much for that.:smack:
I think it’s useful to think about the N=6 K=1 case.
It’s the smallest case where you can do more than just split the group into two even fully connected groups to end up with a disjoint group.
The possibilities are:
Fully connected 6
2 groups of 3
3 groups of 2
A group of 2 and a group of 4.
The total (denominator) possible ways they can be linked is (5C1)^6.
The numerator is (6C3) + (6C2)*[(4C2)+(4C4)]. That is, the number of ways to end up with a disjoint graph is the number of ways to choose 3 people from the 6 + the number of ways to choose 2 people from the six multiplied by the number of ways to do something with the remaining 4 people (either choose all 4 for a group or choose 2 for a group).
Crap, no, that’s not right. You have to then multiply the groups larger than 2 by the number of ways you could distribute the links within that subgroup. Ugh.
FWIW, I consider 2[sup]80[/sup] to be infinity for all practical purposes when it comes to computing. If anything requires that number of: steps, bits, gates, whatever; forget it and work on something else.
Something which is more than the 12th power of that is a Really Big Number.
Yeah, for a group of 3 with k=1, I count eight unique connection patterns, depending on whether there’s a ‘double bond’ somewhere. But for a group of 4, that number shoots way up.
Yeah, but since we’re discussing probability, there’s going to be some really big numbers to balance them out.
For N=60, there’s going to be some k where the other side of the equation is like 1/3 that ginormous number, so you can’t just handwave away numbers as really big in this case. Both numbers are going to be really big, and we want one where their ratio is 1/2
Like, imagine we’re playing poker with 9 card hands from a deck with 40 suits with 27 values each. The numbers involved are going to be trans-astronomical, but the odds that you’re going to get a hand with 1 pair aren’t going to be.