Queer polycule graphs ("polygraphs")

You may already know that every true love triangle contains a queer person. This is because there are two genders in this fictional world: by the pigeonhole principle, whenever you have three people, at least two have matching gender. If they all like each other (hence the love triangle ¹), then those two people like each other. So they're both queer, actually, and in fact every love triangle contains two queer people—the feeling is mutual.

We can generalize this result in various ways, using the combinatorics of connected graphs. Here's one way, generalizing on the number of genders:

If there are G genders, then every group of G+1 people who all like each other (a G+1 "love simplex") contains at least two same-gender-compatible people.

This is a straightforward application of the pigeonhole principle that we used for the specific case of G=2.

What about relationship shapes that aren't triangles? We can formalize these relationship shapes as connected graphs, with vertices denoting people and edges denoting relationships between people. Connectivity means that every person has some meaningful (however distant) chain of relationships with every other person in the relationship shape.

The shape of the graph imposes some constraints on the participants' genders and orientations. For example, we've seen that the triangle graph must have at least two queer people in it—they can't all be straight. In contrast, the two-suitors graph •—•—• can consist solely of straight people, with the person at the middle vertex having a different gender than the other two.

The property that a graph must have in order to allow all-straight participants is called bipartiteness or two-colorability. The idea is that you should be able to color every vertex in the graph either red or blue such that none of the same-color vertices are linked together. If the graph allows such a two-coloring, you can have an all-straight polycule by associating all the red vertices with one gender and all the blue vertices with the other. (To generalize, if you have G genders, the graph must be G-colorable in order to allow all-straight participants. The more colors you have, the less restrictive the condition.) The love triangle graph is not two-colorable, while the two-suitors graph is.

It turns out that bipartite graphs are very rare. We can show that the fraction of graphs (connected or not) that are bipartite is at most 2^(-n2+6n-4)/4. To give you an idea, this is less than 6.25% when n=6, less than .04% when n=7, and less than 10^-6 when n=8. Because most large graphs are connected anyways (see: Béla Bollobás, Random Graphs), this is a good estimate of the fraction of bipartite graphs. Hence

Theorem: Random large polycule shapes are exponentially unlikely to support all-straight participants.

In other words: like the love triangle, the overwhelming majority of relationship shapes necessitate at least one queer person.

Here's the proof.

• We generate a relationship shape at random (say, by considering each possible pairing and flipping a coin to decide if they're related), and we ask what is the probability that the resulting graph is bipartite?

• This is the probability that there is some way to color the nodes red and blue such that the same-colored nodes aren't linked. (There are nominally 2ⁿ such colorings of n nodes, but of course we have symmetry from exchanging red and blue, so there are actually half as many partitions: 2^n-1.)

  Therefore, to compute the probability that the graph is bipartite, we can take the union over all possible colorings, of the event that the coloring successfully bipartitions the graph.

  \[\Pr_{g \in G_n} g \text{ is bipartite} = \Pr_{g \in G_n} \bigcup_{p \in \mathcal{P}_n} p\text{ is a bipartition of }g\]

• To estimate the probability, we can replace the probability of the union with a sum of probabilities. This will always yield an overestimate, since (by subadditivity) the union is only equal to the sum if the events are disjoint—and these events are not.

  \[\Pr_{g \in G_n} \bigcup_{p \in \mathcal{P}_n} p\text{ is a bipartition of }g \leq \sum_{p \in \mathcal{P}_n} \Pr_{g \in G_n} p\text{ is a bipartition of }g\]

• There's a particular partition p^* that divides the nodes into two ~equal groups. This partition is special because it has the highest probability of successfully bipartitioning a random graph. Therefore, if we're looking for a probability overestimate, we can replace "p is a bipartition of g" in our formula with "p* is a bipartition of g":

  \[\sum_{p \in \mathcal{P}_n} \Pr_{g \in G_n} p\text{ is a bipartition of }g \leq \sum_{p \in \mathcal{P}_n} \Pr_{g \in G_n} p^*\text{ is a bipartition of }g \]

  And we can compute that probability directly: the probability that p^* succeeds as a bipartition for a random graph is the probability that there are no edges within the first group of n/2 nodes and no edges within the second group of n/2 nodes. That sequence of coin flips succeeds with a probability of

  \[2^{-{n/2 \choose 2}} \cdot 2^{-{n/2 \choose 2}}\]

• Now we're in a position to calculate the precise value of our rough estimate. The probability that a random graph on n nodes is bipartite is at most \[\sum_{p \in \mathcal{P}_n} \Pr_{g \in G_n} p^*\text{ is a bipartition of }g \]

  This is a sum of a constant whose value is \(2^{-{n/2 \choose 2}} \cdot 2^{-{n/2 \choose 2}}\), and the sum has \(2^{n-1}\) terms in it corresponding to the 2ⁿ/2 distinct ways of partitioning the nodes into two groups. Therefore the probability upper bound is:

  \[\Pr_{g\in G_n}g \text{ is bipartite} < 2^{n-1} \cdot 2^{-{n/2 \choose 2}} \cdot 2^{-{n/2 \choose 2}} = 2^{-\frac{1}{4}[n^2-6n+4]}\]

• P.S. Although we did not impose the constraint that the graph be connected, disconnected graphs are rare, and so this probability bound is good enough.

Every relationship shape supports all-gay (or all-bi) participants: just assign the same gender and orientation to every node in the graph. In this way, the requirement that the participants all be gay (or all be bi) imposes no constraint on the shape of the polycule.