The Setting
The combinatorial setting for the Boolean function construction consists of rows with oriented edges and labels on ordered pairs of rows. The labeling condition concerns sixteen rows at a time and compares edge labels with targets attached to their destinations.
For a natural number , let be the row set. For a directed graph on , write for an edge from to . The outneighborhood of a row is the set in (1), and its outdegree is . (1)
For a natural number , identify with the residues modulo and let be the representative of in . For a natural number , write for the label set.
The Claim
Definition 1. A tournament on is a directed graph with no loops and exactly one directed edge between each pair of distinct vertices, as in (2). (2)✦
A regular tournament with parameter is a tournament on satisfying (3). (3)✦
The cyclic tournament on is the tournament whose edges are given by (4). (4)✦ For every natural number and every vertex , its outdegree satisfies (5). (5)✦ The regular cyclic tournament with parameter is the regular tournament defined by (6). (6)✦
A good edge labeling of a tournament on with labels in is a map satisfying (7). (7)✦
In the paper, the result reads: fix integers and , set , , , and , use a tournament on rows that directs exactly one edge between each pair of distinct rows and has outdegree at every row, such as the cyclic tournament, and call a labeling good when it forbids a set of vertices whose incoming edge labels at each destination are all equal to a selected target .
What Is Checked
The definitions range over natural-number parameters and finite row sets, with the labeling in (7) defined on every ordered pair of rows.