Can Someone Be Straight?
This piece of graph theory was inspired by a logic puzzle The Sexaholics of Truthteller Planet at the 2009 MIT mystery hunt.
Suppose we have a graph where nodes are people and edges connect two people who ever had sex with each other. Given this graph, I am wondering what we can derive about the gender and sexual orientation of the people involved. To do this I need to make some assumptions.
As these are people from another planet, Truthteller, I can choose any assumptions I please, so let us assume that people are of two genders and two types of sexual orientation. The first type of sexual orientation is strictly straight — people of this type only have sex with strictly straight people of the opposite gender. The second type of sexual orientation is strictly homosexual — people of this type only have sex with strictly homosexual people of the same gender. Whoops! I almost forgot: as I assume simplicity, no threesomes happen on that planet.
My question is: Looking at the sex graph can we say anything about sexual orientation? Given any graph, all the vertices can represent homosexual people of the same gender. Is it possible to say, on the other hand, that a vertex of this graph can correspond to a straight person? Let us consider a connected graph representing sex between strictly straight people. This graph has to be bipartite. Hence, given a graph, the maximum number of vertices that correspond to straight people is the total number of vertices in all bipartite connected components.
Similarly, all vertices in a non-bipartite component of a graph are guaranteed to correspond to homosexuals.
Here I would like to name these graphs. If a graph doesn’t have a bipartite connected component I will call this graph an all-homosexual graph. The sequence for which the n-th term is the number of all-homosexual graphs with n vertices for n > 0 starts as 0, 0, 1, 3, 16, 96, 812… and is sequence A157016 in the Online Encyclopedia of Integer Sequences. The smallest all-homosexual graph is a complete graph with 3 vertices.
I would like to name not all-homosexual graphs as someone-can-be-straight graphs. The corresponding sequence is A157015.
Thank you to the people who helped me to calculate and clean these two sequences. I received more help with these two sequences than all the sequences I’ve tried to submit to the Encyclopedia. And it is definitely not because they are about sex, because I purposefully didn’t tell them that I was going to relate these sequences to sex. Thanks to Max Alekseyev, Edwin Clark, Brendan McKay and Wouter Meeussen.
Share:
Leave a comment