The Setting
The constructed complex has vertices , , , and for a natural number its edges from to carry a label , a line of the data described below, and two indices running over . The labels are lines of the affine space , for a prime , each with a marked point on it, and a label is incident to the points of its line other than its mark. The question is how to choose the lines so that the incidence graph between points and labels has no short cycles while almost every point lies on many lines.
Punctured Lines and Marked Line Data
Let be a finite-dimensional vector space over a finite field , and let be its projective space, whose points, the directions, are the one-dimensional subspaces of ; a nonzero vector spans the direction . The line through a point in a direction is the set of points (1)โฆ A point is incident to the mark in direction when it lies on the punctured line, the line with its mark removed: (2)โฆ The incidence graph of a relation between two sets and is the simple graph on the disjoint union in which and are adjacent when they are related, and no two vertices of the same set are adjacent.โฆ
Let be a prime and a natural number. Given labels with marks and directions , write and let be the set of labels incident to a point , those with . Marked line data for and consist of a set of scalars, a finite set of labels whose marks are distinct points of the grid of points of with all coordinates in , a direction for each label, and a set of exceptional points, such that (3) every cycle of the incidence graph of the relation between points of and labels has length greater than , and, with the number of labels, (4)โฆ
Directions and Deletion
Fix a set of marks and a choice of directions . The degree of a point is the number of marks to which is incident in direction .โฆ The mean degree of a point with respect to is the number (5)โฆ
Let . A cycle candidate of length is a sequence of distinct points of , indexed cyclically, together with scalars , such that the points (6)โฆ on the lines joining consecutive points are distinct marks in . The direction of a cycle candidate at is , and a cycle candidate occurs under a choice of directions when for every .
A mark is deleted under when it is one of the marks of a candidate of length at most that occurs under , and retained otherwise. The number of retained marks is written . For a natural number , the exceptional set is the set of points of degree less than together with the points of the lines through deleted marks: (7)โฆ The retained incidence graph is the incidence graph between points of and retained marks in which is adjacent to when . The set of retained incidences of a point is the set of retained marks adjacent to in .โฆ
The Claim
Theorem 1. (a) There are a prime and a natural number that admit marked line data (8)โฆ
(b) Let , let be a prime with and , and let be a set of scalars. Then the grid in has a choice of directions with (9)โฆ
Let be a finite-dimensional vector space over a finite field , a set of marks and a natural number.
(c) For every choice of directions , every cycle of the retained incidence graph has length (10)โฆ
(d) For every choice of directions , every point has (11)โฆ
(e) Let be a natural number and and real numbers with and , such that for every , the number of deleted marks averaged over all choices of directions is at most , and (12) Then some choice of directions satisfies (13)โฆ
In the paper, the result reads: with , , a natural number with , , and of size , for all sufficiently large primes there are affine lines , indexed by a set , with distinct marked points , and a set such that (i) the bipartite graph on with when has no cycle of length at most , (ii) for , and (iii) , so that in particular such data can be fixed with and .
What Is Checked
The claim is stated over marked line data, with incidence on punctured lines (2) and the incidence graph of points and labels, and, for a set of marks in a finite vector space or the grid in , over the degree and the mean degree (5) of a point, the cycle candidates (6) that occur under a choice of directions, the deleted and retained marks, the exceptional sets (7) and the retained incidences.