The Setting
The labelling problem asks whether the edges of a fixed tournament can be labelled so that no set of sixteen vertices has a common incoming label at each vertex.
Write for a nonnegative integer . A tournament on is a directed graph with no loops and exactly one directed edge between each pair of distinct vertices.✦ Write for an edge from to . For a positive integer , a labelling of a tournament on is a map from to . The probability space gives all these labels independently and uniformly; write for its probability measure.
For a nonnegative integer and maps and , the prescribed incoming label event requires distinct listed vertices and label on every internal edge ending at , as in (1): (1) A bad labelling for size is a labelling belonging to for some maps and ; the set of all such labellings is defined in (2): (2) Set and .
The Claim
Theorem 1. Let be a tournament on , and let be a positive integer. For an injective map and any assignment , (3)✦ If , then (4)✦ If , , and , then (5)✦ For and , the numerical estimate is (6)✦
In the paper, the result reads: for a fixed set of vertices and an assignment , independent uniform labels satisfy all internal edge equalities with probability , and the probability of any violation is at most for , , and .
What Is Checked
The statements (3) and (4) concern arbitrary finite tournaments with independent uniform labels on all ordered vertex pairs, with an injective vertex list in (3) and in (4); (5) uses and at , while (6) concerns the choice .