Non-trivial mutual friends

Suppose we have a set of n people, and we want to encapsulate a particular relation which holds between them. For instance, the people who have featured on the cipher solvers page can be represented by a directed acyclic graph. We have a directed edge A → B if person A dominates person B, that is to say that A solved a proper superset of the ciphers solved by B. There is also the transitivity property: A → B and B → C together imply A → C. I have removed these extraneous edges from the digraph to improve clarity.

digraph-2013-01-18

Sam Cappleman-Lynes and Joseph Myers are known as maximal elements, as no-one dominates either of them. The entire graph is an example of a partially ordered set, or poset.

For more symmetrical relationships, it is better to use an undirected graph. For instance, we can connect two people (vertices) with an edge if they are friends with each other. There is no convenient way to analyse the entire global friendship graph, although social networks provide good approximations. There has been a paper examining this graph and revealing certain interesting properties; for instance, the largest connected component of a particular network features about 700 million people, whereas the second largest contains roughly 2000 people.

From graphs to hypergraphs

Vishal Patil and I realised that an ordinary graph is insufficient to embody certain concepts in social communities. For instance, if A, B and C are mutual friends, they would be represented by the cycle graph C_3. However, we can make a more subtle distinction: do the three people know each other merely pairwise, or have they all met simultaneously? By using something called a hypergraph, we can distinguish between non-trivial and trivial mutual friends:

mutual-friends

Trivial mutual friends are far more common, and are just three people who know each other having been together simultaneously. Non-trivial mutual friends (NTMFs, a term originally coined by Vishal, which has later passed into widespread use) are much rarer; the canonical example provided by Vishal was that someone he met at school later encountered James Aaronson on a tour of Israel. An analogy is that 6, 10 and 15 are pairwise non-coprime, but are coprime when considered together.

The set of hypergraphs which can arise is far smaller than the powerset of the powerset of the number of people. In particular, certain constraints must be obeyed:

  • If A is an element of the hypergraph, and B is a subset of A, then B is also an element of the hypergraph (obviously);
  • For every vertex v, the singleton set {v} belongs to the hypergraph (people vacuously know themselves).

Hypergraphs obeying this restriction are known as abstract simplicial complexes. The number of abstract simplicial complexes on n labelled vertices is given by {1, 2, 9, 114, …} (sequence A006126 in the OEIS). Equipped with this new idea of considering abstract simplicial complexes, Vishal and I considered more complicated structures that could arise.

If A, B and C are non-trivial mutual friends (i.e. {A, B}, {B, C} and {C, A} belong to the hypergraph, but {A, B, C} does not), then we can describe them as being either unique non-trivial mutual friends (UNTMFs) or non-unique non-trivial mutual friends (NUNTMFs). A set of three NTMFs are described as unique if there is no person D such that {A, D}, {B, D} and {C, D} belong to the hypergraph. Our first example was a set of three UNMTFs, as no-one else knows Vishal, James and their mutual friend.

Non-unique non-trivial mutual friends

An example of non-unique non-trivial mutual friends includes me, Vishal, Jovan and Katya. The simplical complex corresponding to our acquaintancy is given below:

non-unique

As with all NUNTMFs, the situation is represented by a hollow tetrahedron with between zero and four faces (a solid tetrahedron would correspond to a set of four trivial mutual friends). The possibilities are shown below:

NUNTMFs

Below each of these simplicial complexes is a number called the encounter count. This is the minimum number of encounters necessary for this relationship to be satisfied, i.e. the number of maximal elements in the partially ordered set of simplices under inclusion. Trivial mutual friends have an encounter count of 1.

Counter-unique configurations

The extremal cases of either zero or four triplets of TMFs in a set of four NUNTMFs are very symmetrical, so Vishal decided upon a new name. Rather than describing the configurations as the tongue-twisting ‘encountercountextremal non-unique’, he decided upon the much more manageable ‘counter-unique’. I don’t know of any real-life examples of counter-unique NTMFs, although I have been in a partial tetrahedron where five of the edges and none of the faces were established:

almost-counter-unique

The way in which this peculiar object formed was quite surprising. Radley and I knew each other ab initio, as did Suzy and Miranda. Slightly later, but still ages ago, Suzy met me (thus creating a path graph on four vertices). Radley subsequently met Miranda at their college (Homerton), thus completing a 4-cycle. The fifth edge was completed when Radley met Suzy at the Cambridge Union Society, and we were tantalisingly close to becoming counter-unique non-trivial mutual friends. However, when three of us went to a formal (evening dinner) at Trinity, a face was created and thus the opportunity destroyed.

If you’ve been affected by any of the issues in this blog post, please mention so in the ‘comments’ section below. I would particularly like to hear if you know any real-life examples of counter-unique non-trivial mutual friends, and ideally how they became established.

This entry was posted in Uncategorized. Bookmark the permalink.

0 Responses to Non-trivial mutual friends

  1. Andrew Carlotti says:

    Non-trivial mutual friends are easy to think of – perhaps the most interesting one I can think of is:
    Andrew Carlotti Stephen Pearson Robin Battacharyya Andrew Carlotti

    I think I have come up with two possible sets of counter-unique non-trivial mutual friends. The first one, consisting of six pairs, has two unconfirmed links, one meeting still in the future and some information I am not currently allowed to tell you (sorry).
    The other consists of four triples. The members are:
    1. Andrew Carlotti
    2. Sam Cappleman-Lynes
    3. Adam Goucher
    4. James Rickards

    1, 2 and 3 have met at several maths, 1, 2 and 4 met at IMO 2012, 1, 3 and 4 met at IMO 2011 and 2, 3 and 4 have built a snowman together at Trinity.

    • Andrew Carlotti says:

      The unconfirmed one is now confirmed as not an example.

      Also, I’ve just noticed that my angular brackets above appear to have been interpreted as formatting. The first example should read:
      Andrew Carlotti -(Uncle)- Stephen Pearson -(something to do with quizzing)- Robin Bhattacharyya -(RMM + other maths stuff)- Andrew Carlotti
      All the other examples I have so far thought of are either three people who live locally or three people related through maths. In this case the three links are completely unrelated.

    • apgoucher says:

      Okay, I like your second example of counter-unique NTMFs, and am intrigued to see the first example. Also, I have complete knowledge of the information you’re not allowed to reveal to me.

      • Andrew Carlotti says:

        Really? Perhaps you could tell me what it is then (perhaps on Facebook). I’d be surprised if you do know it.

        I think I may have an example for 6 pairs, though I certainly can’t guarantee its correctness:
        Graham White and Ceri Fiddes may have met at IMO 2006 (as contestant and deputy leader).
        Graham White and David Vasak probably met at some Australian training camp.
        Ceri Fiddes and David Vasak met at IMO 2010 (as deputy leader and contestant).
        Graham White and Paul Russell met at the Pre-IMO camp 2011 (Paul Russell gave a lecture and Graham was deputy leader).
        Ceri Fiddes and Paul Russell met at the Trinity camp last year (2012), and probably at other camps too.
        David Vasak and Paul Russell have presumably met at Cambridge (they are Facebook friends).

        There are a few ways this could go wrong, and it would be very hard to confirm without consulting one or two of them.

        I think two examples (if indeed this is one) are enough, so I’ll stop looking at the EGMO participants list, the UK, AUS and CAN participants on the IMO official site and the list of people at Trinity and Hungary last year (these, along with Facebook and my memory, were my main sources).

        • apgoucher says:

          If your example does turn out to be counter-unique, then well done. James Aaronson prefers more interesting examples, where the edges are for more different reasons (such as my partial tetrahedron, where the five edges were completely different). Sam Cappleman-Lynes provided an example of a five-edge partial tetrahedron which hasn’t yet been ruined by any faces, involving him, someone he met at school called Evie, a person who happened to meet Sam and Evie at *separate* music concerts, and Ed Godfrey (who has met Evie, but not the elusive concert acquaintance whose name is unknown). We just need unknown guy to meet Ed Godfrey in some contrived situation that’s been deliberately engineered.

          James, however, remarked that these partial tetrahedra (more accurately known as ‘diamond graphs’) are not too surprising, since they’re just a pair of people with two NTMFs who haven’t met each other.

          Vishal remarked how NTMF triples and counter-unique quadruples are special cases of the general idea of a set of n people such that every k-set has met but no (k+1)-set has met (where 1 < k < n, for non-triviality).

          • Edward says:

            I’m afraid I don’t remember which Evie Sam means…

            Another “almost” tetrahedron involving me (and possibly a full tetrahedron, I’m not sure) is Me – Hunter Spink – Jordan Millar – Yunwoo Lee. There may be others.

          • Andrew Carlotti says:

            What shape should that give Ed, and what are the circumstances causing it? The only bits I know of are an edge for you and Jordan, and a possible face for Hunter, Jordan and Yunwoo (all three were at IMO 2011, but may not have met together at any stage).

        • Graham White says:

          All of the elements of that involving me are correct – all three edges exist and none of the three faces do. (I do not specifically remember meeting Ceri at that particular IMO, but agree that I probably did).

          • apgoucher says:

            Perfect! The other edges are certain based on the evidence given by Carlotti, so we need only verify that the face {David Vasak, Ceri Fiddes, Paul Russell} does not exist. I’ll go ahead and ask him…

    • Andrew Carlotti says:

      I am now allowed to tell you my idea for where another CUNTMF may be found. My original set of people doesn’t work, but I expect that it may be modifiable so that it does work. It is based around maths stuff, and cipher challenge prize-giving ceremonies.
      Graham Niblo (head of maths at Southhampton, and organizer (I think) of the cipher challenge), has met (Florence Salter/Natalie Behague/Vishal Patil) at the prize-giving ceremony last year, and will meet (Daniel Hu/Andrew Carlotti) at the ceremony this year. A fourth person can probably be found who has met him either at a prize-giving ceremony or who knows him through university, and who has met two of the other people above, on separate occasions.
      I had been considering the set Graham Niblo, Andrew Carlotti, Florence Salter and Alex (Luke) Betts, but Luke, while invited to the ceremony four years ago, did not actually go, and I didn’t bother to find out whether he had met Florence, or whether he had met us both at the Royal Society this year.

      • Andrew Carlotti says:

        Also, despite having “complete knowledge of the information you’re not allowed to reveal to me”, Adam seems to have in fact known nothing about it.

      • apgoucher says:

        Florence Salter has almost certainly met Lex Betts at TCC, and not in the presence of Carlotti or Graham Niblo, so I can confirm that this tetrahedron exists. Well done.

        • Andrew Carlotti says:

          Did you not read it properly? The tetrahedron does not exist because neither Luke nor I (as it happens) have met Graham.

  2. ggendler says:

    Here is a wireframe tetrahedron I can almost confirm, where the edges are quite different. I will use initials:
    EA and GG are schoolmates
    EA and AW were at a debating competition
    AW and AM are schoolmates
    AM and GG met in Israel
    GG and AW met at a party

    I can say with 90% certainty that EA and AM know eachother; although they are not friends on Facebook I know that their set of very close friends have a huge intersection.

    With even more certainty I can say that AM, EE and AW do not form a face as EE and AW have only met at a debating competition, but again I am not completely certain.
    Everything involving GG is definite for obvious reasons.

    • ggendler says:

      That should read EA

    • apgoucher says:

      That’s much more interesting than Carlotti’s example, as the meetings are for different reasons. Impressive!

    • Andrew Carlotti says:

      I think I’ve just found a good example a good example. All four people live in Kent and are a similar age, but that’s the only thing linking all four. The people are Andrew Carlotti, Billy Severn, Heather Dower and Andrew Lancaster
      AC and BS both went to Ripple School for Year 1 to 3.
      AC and HD went to Explorer Scouts together.
      AC and AL both go to Sir Roger Manwood’s School.
      BS and HD both went to both Walmer Science College and Canterbury College.
      BS has met many members of a group of friends including AL, but I can’t guarantee that they’ve met.
      HD’s boyfriend is AL’s brother.

  3. Anonymous says:

    here are a few examples/quasi-examples. most of them are pretty boring since they involve situations like myself + 2 people from trinity that i’ve seen individually but never together though i can check they’re facebook friends. i’m guessing that is allowed. personally i have a wide but shallow network of acquaintances so it’s not hard to think of some of these. (i would NOT recommend this. a large amount of diluted friendships simply don’t add up.)

    all relevant friendships have been confirmed by excessive facebook stalking except in rare cases where it’s obvious

    last names have been omitted

    (formerly) example uno:

    1 myself
    2 sophia
    3 alex m
    4 aneesh

    12 trinity
    13 sending me weird freaky texts (ok, here’s the context. there’s this guy called alex from corpus in my year who 13 months ago got a hold of my number via aneesh and started sending me these freaky texts. i didn’t know him at the time. i kept replying to his strange texts trying to out-freak him, thinking phone rape, but turns out it wasn’t, he just felt like doing it. we later met and became friends. also all the corpus people sat at the back row in lectures in the cockcroft and secretly stalked everybody, that’s how they knew me beforehand. don’t ask why.)
    14, 23 school (different schools obviously)
    24 facebook rape, they don’t know each other
    34 corpus
    (triples 123 and later 134 have since been formed. this was the most clearcut example)

    example dos:

    1 myself
    2 sophia
    3 ingram
    4 aneesh

    12, 13, 23 trinity (i’ve never seen the other two at the same time)
    14 school
    24 facebook rape
    34 cambridge union

    example tres:

    1 myself
    2 horace
    3 alex r
    4 nick

    12, 23, 24 school
    13 maybe i think i met him once at school or something but i can’t remember
    14 online community and later real life in a graph theory lecture
    34 same online community, never real life (in fact they didn’t know each other by real name until i found this out)
    (134 not an online triple because 3 left it before i joined)

    example cuatro:

    1 myself
    2 ram
    3 greg
    4 john

    12 birmingham maths 2007
    1->3 i followed the directions on alex’s texts and somehow unintentionally ended up in his room. he recognised me, because:
    3->1 lecture stalking
    14 trinity
    23 corpus
    24 no idea
    34 school
    (234 might be a triple. not sure. can’t say)

    example cinco:

    1 myself
    2 francesca
    3 joe
    4 matt

    12 varsity ski trip (we probably met before at school, but forgot each other)
    13 school
    23 probably school, they were a year apart
    14 trinity
    24 trinity a year apart i guess
    34 no idea but 3 is a pembroke fresher so something cambridge related

    example seis:

    1 myself
    2 alasdair r
    3 alasdair p
    4 ben

    12 he supervised me for vectors and matrices
    13, 14, 34 trinity, i’ve never seen the other two at the same time
    23 rowing
    24 they live next door

    quasi-example siete: (not involving myself)

    1 charlie
    2 you
    3 david
    4 vishal

    12 that time when charlie shouted your name out in front of the whole magpie and stump audience 😛
    13 trinity
    14 magpie and stump (unless charlie knows that you and vishal know each other, but i might have to check with him.)
    23 imo 2011
    24 some random maths camp presumably. you tell me
    34 now we just need to get david and vishal to meet each other; maybe they already have done? and you can’t be there with him. tell me how this plan goes

    to be honest, the two peoples’ examples directly above this post probably beat all of these for elegance, but i feel this is worth sharing anyway

    • apgoucher says:

      Hmm, it appears that wireframe tetrahedra are more common than I imagined. Hence, it could be possible that there exists a K_5 somewhere. I can’t help but notice that Vishal seems to feature frequently in these tetrahedra, so he might be a good place to begin.

      By the way, it has been mentioned that there are ‘boring’ examples of wireframe simplices arising when people on sports teams meet each other in matches.

  4. Anonymous says:

    correction: you and david didn’t meet at imo 2011 (doh) but i’m pretty sure you know him anyway

  5. apgoucher says:

    Anyway, I neglected to mention that I’m now part of a wireframe *disphenoid*, i.e. opposite edges of the wireframe tetrahedron are for similar reasons. Specifically, we have:

    VPP — APG: Met at Trinity College, Cambridge
    SEE — PB: Met at Downing College, Cambridge

    VPP — PB: Attended the same school in Birmingham
    SEE — APG: Attended the same maths camp in Birmingham

    APG — PB: Charity blind date in a pub in Cambridge
    SEE — VPP: Conversed whilst queueing outside a club in Cambridge

    None of the faces have been created yet, and they are unlikely to form in the foreseeable future.

  6. Pingback: Pairwise versus overall | Complex Projective 4-Space

Leave a Reply to apgoucherCancel reply