FAQ 
Calendar 


#1




Group selfsorting: a math question
I have a question about the math of selfsorting 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? 
#2




I think this question is related to percolation theory.

#3




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 subgroups 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 notoverlapping subgroups?) Last edited by md2000; 11062019 at 02:16 PM. 
#4




Quote:
You have a graph with 60 nodes (students) each of which have 10 edges connected (knowrelationship). 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 2person pairs. Then there's a combinatorics problem: What fraction of such graphs are fully connected. I don't have a neat closedform solution to this but it'd be easy enough to do a Monte Carlo simulation. WAG: It's way closer to 1 than 60. Last edited by iamthewalrus(:3=; 11062019 at 02:24 PM. 


#5




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 ingroup that at least one member of the group recognizes. 
#6




Quote:
And this is a preliminary subproblem to the OP's question. So, have a nice day. Ta. 
#7




Quote:
The second claim is easy to show. If persons 130 know each other and no one else, and persons 3160 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. Last edited by iamthewalrus(:3=; 11062019 at 05:57 PM. 
#8




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 selfassemble with 100% reliability. Neat!

#9




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 2way bonds). for each of those 9, there's a 5in6 chance that the person is not known to A. This becomes the 6degreesofseparation game, where A is Kevin Bacon.
Count bonds, not groups. There are N(N1)/2 possible bonds in a group. So in 60 people, 60*59/2=1770 bonds. In 30 or less, a max of 30*29/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?) 


#10




The bonds don't have to be twoway, though: A can know B, with only an x/60 chance of B knowing A in return.
I think that means that there are (N)(N1) possible oneway bonds in a group if everyone can remember (N1) bonds. 
#11




Quote:
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!*(nk)!). To know the probability, we have to know how many total ways there are to choose the bonds. There are 60*59=3540 bonds, but we can't just choose 60*29=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 (n1 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. 
#12




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.

#13




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: 1. Fully connected 6 2. 2 groups of 3 3. 3 groups of 2 4. 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). 
#14




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.



#15




Quote:
Something which is more than the 12th power of that is a Really Big Number. 
#16




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.

#17




whoops double post
Last edited by brossa; 11082019 at 02:16 PM. Reason: double post 
#18




Quote:
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 transastronomical, but the odds that you're going to get a hand with 1 pair aren't going to be. 
Reply 
Thread Tools  
Display Modes  

