Graph Isomorphism for non-mathematician

Question

Question: What is a good explanation of the Graph Isomorphism problem, which would be understandable - and hopefully exciting - to a person who has minimal exposition to mathematics? Note that I do not need this application to be realistic - highly idealised fantasy stories are absolutely OK, as long as they make sense as stories. I'm specifically not interested in the actual applications of the Graph Isomorphism, unless they are appealing to non-mathematicians

Example: The Ramsey numbers problem has a very nice "real life" example involving a party, where some people know one another, and others don't. Then one can show, assuming there are at least 6 people, that either three of them are all friends, or some other three of them are all strangers. This is precisely the statement that $R(3,3) \geq 6$, but arguably laymen prefer thinking in terms of groups of friends at parties, but not so much in terms of monochromatic cliques in graphs.

The interpretation of Hall's theorem as a statement about marriages is another example of the type I'm looking for. Note that these two examples are somehow canonical - almost always, when these problems are first introduced, one of these interpretations is used (or a slight variation thereof).

Note also that Smullyan's books give rather more involved examples explaining some fundamental ideas in logic.

Work so far: The idea of representing a graph as a party is promising. One can represent vertices as people and edges as acquaintances. To introduce the isomorphism, one could have two independent ways of referring to people - for lack of a better idea, make it a mask ball, and then refer to people either by names or costumes, but that's perhaps too convoluted. Now, given two descriptions of the two different kinds, the question is: Could these descriptions be the same party? But I think there must be a better way...

Motivation: Given the recent breakthrough of Babai, it would be great to be able to communicate what happened to non-mathematicians, in as engaging a way as possible.

Apology: I'm not sure if this question fits the scope of MSE and if possibly it's too open-ended. Feel free to vote to close if necessary. Because some other problems have an essentially unique "real life" models, I'm hoping that an answer to this question might in principle exist, and not be terribly opinion-based.

P.S. Is there a way to make question CW here? I can't seem to find it, and I would use it if possible.

Answer 1

I'm not sure how much value I'm adding here, but perhaps this example will be interesting to kids of the modern age. Suppose we have the following two graphs of equal size:

• Graph 1: A group of youths with Facebook accounts. Some pairs of people in the group are friends on Facebook, some are not.
• Graph 2: A room full of pre-programmed old-school paging devices that are not re-programmable. In each paging device is a list of contacts of other paging devices that it is connected to. Connections are two-way i.e. if device $A$ has $B$ in its contacts, then $B$ also has $A$ in its contacts.

Now, suppose this group of youngsters are all kidnapped one day and taken to a desert island where all they are provided with is food, water, shelter and these paging devices. To save themselves from death by social-media starvation, they must be able to connect with all of their friends on the island*. They also must avoid at all costs connecting with strangers: we've all seen Catfish and the danger that brings.

The youths are then confronted with the isomorphism problem: is it possible to give each person on the island a paging device such that for every person, they are connected via pager to their Facebook friends on the island, and not to anyone else?

Notes

*I specifically say "friends on the island" as opposed to "Facebook friends" because I'm sure the entire Facebook graph is for the most part connected, and the idea of kidnapping its entire user base and bringing them to a desert island seems a little bit extreme.

Answer 2

The problem of whether there exists a nontrivial graph automorphism reduces to graph isomorphism, and is not known to be any easier. Here is a way I thought of explaining that problem:

Start with a supply of yarn and some jacks. Each jack represents some country in the world. If two countries share a border, tie those two jacks together with a piece of yarn. Now take the whole mess and mix it up. Can you still figure out which jack is associated with which country? This is an instance of the graph automorphism problem. If we have more than one island (jack with no yarn attached to it), the answer is "no" since we can't tell which jack goes with which island. But if the countries are Canada, United States, Mexico, Guatemala, Belize, and El Salvador then the answer is "yes" since the automorphism group if this graph contains only the identity. Not every graph can be embedded on a sphere so the analogy to countries may not properly capture the hardness of the problem (but we can certainly build models with yarn that do).

This Topologist's Map of the United States is another example of graph automorphism:

Can you figure out which polygon corresponds to which one of the $48$ contiguous states plus Lake Michigan? We can also make it a graph isomorphism problem by asking if it there is any correspondence at all without requiring that it be unique.

Also I can try to explain graph automorphism in terms of a party. Somebody spiked the punch and everyone forgot their identity! But everyone can still recognize their friends and the banquet seating is arranged so that only people who know each other sit near each other, and each seat is labelled with the guest's name. Can everyone be sure of their identity after everyone finds a chair where they know all their neighbors? This is analogous to the other example, imagine there are six guests and seats in the positions of those countries, each guest is a jack and each friendship is a piece of yarn. Also there is the same problem that a seating arrangement may be too restrictive a type of graph to encompass the hardest instances.

Answer 3

A very artificial example.

Explain the context of Hall's theorem and how we model it with a bipartite graph. That is, you have $n$ boys and $n$ girls and know which one likes who. Call this the likeness graph.

If you have only two people then the situation is pretty simple. Either they like each other or they dont - you have two non-isomorphic instances $K_2$ and $\overline{K_2}.$

You can wrap this up in the following story.

You work at a company that helps groups of people getting married. You are a counselor that for each group that arrives constructs the likeness graph and counsels them who should they marry based on Hall's theorem.

Since you want to be able to evaluate your work you also store your choice of pairs as well as the underlying bipartite graph. After a while you call these couples to check whether their relationship is still working out and you carry an analysis of how your assignment worked out.

Now each time a new group arrives you can check if their likeness graph correspond to any group that you already covered and if the assignment tried worked out or not. To do so you need to make use of isomorphism testing.

Answer 4

I don't know how much my answer is justified to what you needed but for a non-mathematician, the following example may pull some attention.

A group of four persons (Angelina, Jessica, Bob and Jonty) working in a company have the friendship graph depicted in the first graph, where each of them has exactly two friends of opposite gender. If the company decides to send the male employees in its rural branch, then each one of these four may suffer the isolation syndrome in their working hours as depicted in the second graph.The working efficiency of each of them will certainly be effected but not their friendships. The second graph obtained by twisting and turning the first graph but keeping the edges intact is isomorphic to the first one.