The Setting
The labelling problem in the sensitivity and block sensitivity construction concerns a finite tournament and the labels attached to its directed edges. For natural numbers and , write for the vertex set and for the label set. A tournament on is a directed graph with no loops and exactly one directed edge between each pair of distinct vertices, as in (1); write for its adjacency relation.✦ (1)
A tournament with natural parameter is regular if it has vertices and every vertex has exactly outgoing neighbours.✦ For a natural number , the cyclic tournament is the tournament on whose edges are given by (2), where is the least nonnegative residue of .✦ (2) The regular cyclic tournament with natural parameter is defined by .
Good Labellings
Fix . A good labelling of a tournament on with labels is a map satisfying (3).✦ For a tournament on , is the set of good labellings of with labels. (3)
The Claim
Theorem 1. Let be a natural number, and put and . For the regular cyclic tournament , (4)✦ More generally, let and be natural numbers satisfying , and let be any tournament on vertices. Then (5)✦ Let be a tournament on , let , and let have . For every map , (6)✦
In the paper, the result reads: with the stated parameters and regular tournament, the edges admit labels such that no set of size admits choices , , satisfying for every edge within .
What Is Checked
The existence assertions (4) and (5) concern finite tournaments with , using respectively and any with ; the subset assertion (6) concerns a good labelling and a prescribed label map on a sixteen-vertex subset.