Combinatorics 3: A Genetic Pigeonhole Principle

This is the third in a series of 7 posts on sharing combinatorics:

Part 1: Combinatorial Principles for DNA Sharing

Part 2: Non-transitivity

Part 3: A Genetic Pigeonhole Principle

Part 4: Transitivity Principles

Part 5: X-Chromosome Transitivity Principles

Part 6: Mutual Sharing Principle

Part 7: Exceptions

 

In the following, "share" means "share a particular half-identical region with" (all regions are at the same locations).

Sharing "fully identically" means that the two people match on that region on both homologous chromosomes, not just on one.

 

Genetic Pigeonhole Principle:
If a person shares with a number of other people, those other people can be divided into two sets S and T, where everybody in S shares with one another, and everybody in T shares with one another.

[Looking at the raw data, all the people in S share one strand with the original person, and all the people in T share the other strand with the original person.]

It's possible for S or T to be empty, or to have just one person in it. In that case, the other set contains all, or all but one, of the other people.

We can also state the following two consequences to the Genetic Pigeonhole Principle:

 

Three-Way Pigeonhole Principle:
If a person shares with 3 other people, then at least 2 of those other people share with each other. [Looking at the raw data, those two would share a common strand with the original person.]

 

N-Way Pigeonhole Principle:
If a person shares with N other people, then at least N/2 (rounding up if N is odd) of those other people all share with one another.

[Again, all of these N/2 people share a common strand with the original person.]

---

 

Finally, we have a stronger pigeonhole principle for the special case of a male sharing on the X chromosome.

Men have one X chromosome; women have two X chromosomes. This is the reason for analyzing sharing on the X chromosome specially. In the case of a male, there is no difference between half-identical sharing and fully identical sharing when looking at regions on the X chromosome. In the case of a female, "sharing" refers to the usual half-identical sharing.

 

Pigeonhole Principle for Sharing with the Male X Chromosome:
If a male shares on the X chromosome with a number of other people, then they all share with one another; in fact, they all share a common strand.

Note: For a female sharing on the X chromosome, there isn't a strengthened version; the general formulation that applies to all chromosomes is the best we can do.