This Forum has been archived there is no more new posts or threads ... use this link to report any abusive content
==> Report abusive content in this page <==
Post Reply 
 
Thread Rating:
  • 0 Votes - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
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

Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
[] - Brian - 03-24-2014 04:16 PM

Forum Jump:


User(s) browsing this thread: 1 Guest(s)