2 ms·

If you try, you'll find that you can't think of a configuration for which neither is true. (Maybe it's not "obvious" but it's easy to arrive at that conclusion

If you try, you'll find that you can't think of a configuration for which neither is true. (Maybe it's not "obvious" but it's easy to arrive at that conclusion after some thought.) This comment from the other linked discussion describes what was actually proved; the narrow case of facebook friends is just a given example. https://news.ycombinator.com/item?id=23028299 https://news.ycombinator.com/item?id=23028299

01HNNWZ0MV43FF 2y ago
Correct my math if I'm wrong 6 people have 6 * (6 - 1) / 2 = 15 possible connections. If you toggle those off and on you have about 2 ^ 15 = 32,768 combinations. Some of those are surely redundant but I don't know stats well enough to de-dupe them. Either way I feel like it's higher than I can count in my head while also doing anything else mathematical
- bongodongobob 2y ago
  All that is completely irrelevant, you're overcomplicating it. Each person has 1 of 2 states, connected or not. If 4 are connected, 2 aren't, if 4 aren't 2 are, etc.
  - kevinwang 2y ago
    No, each edge in the graph has 2 states. There are 15 edges between the 6 people.
    - bongodongobob 2y ago
      But the edge states don't matter, the node states do. They're either connected friends or they aren't. What's the third state?
      - 01HNNWZ0MV43FF 2y ago
        2 groups of 3 mutual friends is a different graph than 3 pairs of friends
      - lmm 2y ago
        No, the connections are what matters. A may be friends with both B and C, but that doesn't mean that B is necessarily friends with C.
        bongodongobob 2y ago
        I understand that. That's the encoding of being "connected".
        lmm 2y ago
        Where did you get "connected" from? We're talking about whether they are "a trio of mutual friends" or not; that requires them all to be friends with each other, not merely "connected".
      - sixfiveotwo 2y ago
        In this encoding of the problem, the graph is fully connected, the edges indicate the state of a connection (ie. friendship) between 2 users, and the goal is to check that there is either a chain of 2 "connected" edges (A to B and B to C for any A,B,C in the nodes) or 2 "disconnected" edges, which indeed isn't easy to do the tedious way. The crucial property here is the symmetry between connected and disconnected edges: for any given configuration, if it's difficult to check it on one hand, then it should be easy to do it on the other.
- Izkata 2y ago
  The simple version: Among 6 people, to avoid a trio of friends, no sub-group can be 3 or more. Maximize the size of the sub-groups to minimize the number of non-friends: 2 + 2 + 2. One from each sub-group is a trio of non friends. So either you have enough sub-groups to create a trio of non-friends, or there's a sub-group large enough to create a trio of friends.

01HNNWZ0MV43FF 2y ago

Correct my math if I'm wrong 6 people have 6 * (6 - 1) / 2 = 15 possible connections. If you toggle those off and on you have about 2 ^ 15 = 32,768 combinations. Some of those are surely redundant but I don't know stats well enough to de-dupe them. Either way I feel like it's higher than I can count in my head while also doing anything else mathematical

bongodongobob 2y ago
All that is completely irrelevant, you're overcomplicating it. Each person has 1 of 2 states, connected or not. If 4 are connected, 2 aren't, if 4 aren't 2 are, etc.
- kevinwang 2y ago
  No, each edge in the graph has 2 states. There are 15 edges between the 6 people.
  - bongodongobob 2y ago
    But the edge states don't matter, the node states do. They're either connected friends or they aren't. What's the third state?
    - 01HNNWZ0MV43FF 2y ago
      2 groups of 3 mutual friends is a different graph than 3 pairs of friends
    - lmm 2y ago
      No, the connections are what matters. A may be friends with both B and C, but that doesn't mean that B is necessarily friends with C.
      - bongodongobob 2y ago
        I understand that. That's the encoding of being "connected".
        lmm 2y ago
        Where did you get "connected" from? We're talking about whether they are "a trio of mutual friends" or not; that requires them all to be friends with each other, not merely "connected".
    - sixfiveotwo 2y ago
      In this encoding of the problem, the graph is fully connected, the edges indicate the state of a connection (ie. friendship) between 2 users, and the goal is to check that there is either a chain of 2 "connected" edges (A to B and B to C for any A,B,C in the nodes) or 2 "disconnected" edges, which indeed isn't easy to do the tedious way. The crucial property here is the symmetry between connected and disconnected edges: for any given configuration, if it's difficult to check it on one hand, then it should be easy to do it on the other.
Izkata 2y ago
The simple version: Among 6 people, to avoid a trio of friends, no sub-group can be 3 or more. Maximize the size of the sub-groups to minimize the number of non-friends: 2 + 2 + 2. One from each sub-group is a trio of non friends. So either you have enough sub-groups to create a trio of non-friends, or there's a sub-group large enough to create a trio of friends.