# Queer polycule graphs ("polygraphs")

## Table of Contents

Note: This article assumes an artificially simple world with two genders and three orientations (same-attracted, other-attracted, and bi).

## 1. Love triangles always contain queer people

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 ^{1}), 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.

## 2. All-straight polycules are vanishingly rare

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^{n}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

^{n}/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.

## 3. All-queer polycules are universal

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.

## Footnotes:

^{1}

In contrast to the incomplete trope where one person has two suitors who don't like each other.