Out of a group of 10 people, what is the maximum number of FST's that exist?
|
03-24-2014, 04:16 PM
Post: #2
|
|||
|
|||
If we have one person who is friends with the other 9,
and no friendships exist amongst these other 9, then a FST exists between each of the C(9,2) = 36 pairings of 2 of these 9 people along with the original (popular) person. So I think that 36 is the maximum number of FSTs. Edit: Yes, I was way off. I believe the maximum is 100. Divide the 10 people into 2 groups of 5. In each group, no one knows anyone else, but each of them knows every member of the other group. So each of the 10 people act as the 'primary vertex', (by which I mean the person who knows each of the other two in the FST), to C(5,2) = 10 FSTs. (The C(5,2) term comes from choosing 2 of the 5 people in the other group.) Since there can only be one 'primary vertex' in any FST, each of these 10*10 = 100 FSTs will be unique. I'm not sure how to prove that this is the maximum, but I can't find any configuration that results in more FSTs. Edit #2: In general, for n = 2m people there is a maximum of (m^2)*(m - 1) FSTs, and for n = 2m + 1 there is a maximum of (m/2)*(2m - 1)*(m + 1) FSTs. So, for example, with n = 10 = 2*5, we have m = 5, and thus a maximum of 5^2*(5 - 1) = 100 FSTs. For n = 9 = 2*4 + 1, we have m = 4, and thus a maximum of (4/2)*(2*4 - 1)*(4 + 1) = 2*7*5 = 70 FSTs. As m gets very large, the maximum number of FSTs goes roughly as m^3. Ads |
|||
« Next Oldest | Next Newest »
|
Messages In This Thread |
Out of a group of 10 people, what is the maximum number of FST's that exist? - Don Leon - 03-24-2014, 04:16 PM
[] - Brian - 03-24-2014 04:16 PM
|
User(s) browsing this thread: 1 Guest(s)