Combinatorics 4: Transitivity Principles

This is the fourth 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

 

As before, "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.

Our transitive principles all involve somebody (person A) sharing with one or more other people, who themselves all share with somebody else (person B). True transitivity would say that person A must share with person B, but this isn't necessarily true.

Although sharing isn't transitive, here is a valid transitive-like principle, which we'll state first for sharing with 5 people, and then in its general formulation:

 
Five-Way Transitive Principle:
If person A shares with 5 other people, and if those 5 people all share with person B, then either:

(a) More commonly — A and B share with each other;

or

(b) More rarely — at least 2 of the 5 other people share fully identically on the region in question.

 
N-Way Transitive Principle:
If person A shares with N other people, and if those N people all share with person B, then either:

(a) More commonly — A and B share with each other;

or

(b) More rarely — at least N/4 (rounding up) of the N other people share fully identically on the region in question.

---

 

We can also state some strengthened transitivity principles for sharing on the X chromosome, but those are in a separate post.