Balanced counterexamples to Ryser’s conjecture at prime orders

1 Introduction

A vertex cover of a finite hypergraph H is a set of vertices meeting every edge. Its minimum possible size is the covering number \tau(H). The matching number \nu(H) is the maximum number of pairwise disjoint edges. For an integer r\ge2, an r-partite r-uniform hypergraph has disjoint vertex parts V_1,\ldots,V_r, and each edge contains exactly one vertex from each part. Here balance refers to equal sizes of the vertex parts. Ryser’s covering conjecture proposes that every such hypergraph satisfies

A hypergraph with at least one edge is intersecting if every two distinct edges meet. In this case \nu(H)=1, and the proposed bound is r-1. A cover may use vertices from any of the parts, so making each individual part large does not by itself obstruct a small cover.

For r=2, inequality (1) is Kőnig’s matching theorem for bipartite graphs. Henderson’s 1971 thesis contains an equivalent formulation of the general conjecture [13]; Best and Wanless [5] discuss its attribution to Ryser and separate it from his Latin-square transversal conjecture. Aharoni proved the full tripartite case [3]. In the intersecting case, Gyárfás proved the conjecture through rank four and Tuza proved rank five; see Király and Tóthmérész [15] for the historical account. For linear intersecting hypergraphs, in which every two distinct edges meet in exactly one vertex, Francetić, Herke, McKay, and Wanless established the conjecture through rank nine [9]. For each of r=4,5, Haxell and Scott proved a bound \tau(H)\le(r-\varepsilon_r)\nu(H) with a positive constant \varepsilon_r [10]. More recently, White proved \tau(H)\le6 for four-partite four-uniform hypergraphs with \nu(H)=2 [20]. These results concern the covering inequality itself. Lovász proposed the stronger assertion that, in every r-partite r-uniform hypergraph with at least one edge, deleting r-1 vertices can reduce the matching number. Clow, Haxell, and Mohar disproved that assertion at r=3 [6]; Abiad, Garbe, Povill, and Spiegel subsequently gave an infinite family at r=3 and examples at r=4 [1]. Those examples do not contradict (1).

Finite planes explain why the bound r-1 is natural. In the affine plane \F_q^2, make one part for each of the q+1 directions, with one vertex for each line of that direction. An affine point determines an edge consisting of the labels of the lines through it. Two such edges meet at the label of their joining line. Each parallel class is a cover of size q, and fewer than q lines cannot cover q^2 points. Thus this hypergraph is intersecting and has covering number q. It is the usual truncated-projective-plane example, expressed through affine duality.

Abu-Khazneh, Barát, Pokrovskiy, and Szabó exploit the rigidity of minimum covers in a truncated plane and add a new part and exceptional edges. For every prime power q\ge3, their construction yields an intersecting (q+2)-partite (q+2)-uniform hypergraph with covering number q+1 [2, Theorem 1.2, Lemma 1.3, Corollary 1.4]. Haxell and Scott use affine planes to construct intersecting r-partite r-uniform hypergraphs with covering number at least r-4 for every sufficiently large r, and at least r-3 when r is even [11, Theorem 6].

Equal part sizes alone do not force a large covering number: Francetić, Herke, McKay, and Wanless constructed a linear intersecting 13-partite hypergraph with 13 nonisolated vertices in each part, and reported that its covering number is nine by computation [9, Section 3.1]. Here we modify the affine-plane example while keeping q+1 parts, one for each direction. The modification raises both the covering number and each part size to q+1.

Since \nu(H)=1, this gives counterexamples to (1). The value \tau(H)=r, where r=q+1, is the largest possible for an intersecting r-uniform hypergraph, since any edge is a cover. The nonisolated vertices in each part also form a cover, so a hypergraph with \tau(H)=r must have at least r such vertices in every part. Our construction attains this minimum simultaneously in all parts.

The argument produces an example for each prime beyond one fixed threshold; that threshold is not numerical. The companion article [18, Theorem 1.1] treats a different range of field orders: for every sufficiently large prime s\equiv2 \pmod3, it gives counterexamples of order q=s^n for every sufficiently large odd n, with the threshold for n depending on s. Its theorem does not assert balance. The proof here is independent of that construction.

1.1 Monochromatic tree covers

An r-edge-coloring assigns one of r colors to each edge of a graph. A monochromatic tree cover is a family of monochromatic trees whose vertex sets cover the graph; overlaps and singleton trees are allowed. Gyárfás’s tree-cover conjecture asks for at most r-1 such trees in every r-edge-colored complete graph [17, Conjecture 1]. Erdős, Gyárfás, and Pyber record the equivalence of this covering formulation with the intersecting case of Ryser’s conjecture [7, Section 3, after Theorem 2]. The standard transfer gives the following consequence of Theorem 1.1.

1.2 Balance, intersection, and the cover obstruction

The affine-plane example starts with q blocks in each parallel class. We replace those line partitions by partitions with q+1 blocks, keeping one vertex part for each direction. In a given direction, merge two parallel lines into one block, and split two other parallel lines into two blocks each. The count becomes

Each split line keeps just four designated points. Writing them in a cyclic order as u_0,u_1,u_2,u_3, its blocks are the opposite pairs \{u_0,u_2\} and \{u_1,u_3\}. All points outside the chosen split lines are retained as well. The choices ensure that designated points lie on no other chosen split line, so these rules really give partitions of one common set of retained points. The blocks label vertices and the retained points label edges.

The splitting operation creates the first difficulty: two points on a split line may now have different labels in that direction. We arrange four merged pairs in four distinct other directions so that each consecutive pair u_{i-1},u_i lies in a common merged block. These are exactly the pairs separated by the opposite-pair partition. Thus every pair of retained points still shares a block somewhere, and the resulting hypergraph remains intersecting. Figure 1 shows the rule; Section 2 states its precise incidence and compatibility requirements.

The harder difficulty is to rule out a cover using labels from several parts. Temporarily remove all split lines and one constituent of each merged pair. On the surviving core, every remaining block is represented by a single ordinary line. Hence a cover with at most q labels gives a cover of the core by at most q lines. We prove that almost all those lines belong to one projective pencil: they pass through one affine point, or are all parallel if the common projective point is at infinity.

Every relevant line also retains a positive proportion of its points. This occupancy forces a hypothetical cover to select every nonsplit member of its pencil. Only a small budget of labels remains for the four-point sets on split lines through the pencil’s center. Compatibility handles the parallel case and pencils containing at most two split lines. For larger pencils, a separate incidence count shows that the remaining budget is insufficient. The deterministic result in Section 2 makes these requirements explicit before we construct data satisfying them.

1.3 Producing the geometric data

The probabilistic argument has to preserve its estimates through several choices. First sample two independent constituent lines in each direction. They generate many candidate four-point tuples on different split lines. An incompatibility graph records choices that cannot coexist. There are two slots per direction, each carrying the candidates for one split line. Choosing one candidate in every slot without an incompatible pair is an independent transversal of this graph.

Section 4 bounds the sizes and degrees of this graph, including the exceptional pairs that can have large common neighborhoods. Section 5 then constructs a random independent transversal while maintaining line occupancy. The procedure first makes random choices and adds thinning to equalize one-step survival; it completes the last slots using the local lemma. Partial random selection followed by local-lemma completion also appears in the locally sparse transversal argument of Loh and Sudakov [16, Section 4]. Here we need an additional quantitative output: prescribing the choices in s slots, jointly with successful return, has probability at most (K_*/q)^s for a fixed constant K_*. This bound controls later incidence counts without assuming that selected tuples are independent.

The core estimate in Section 3 is designed for the law of these selected lines. Under uniform deletion of a fixed number of lines per direction, with probability tending to one every small core cover also covers almost all of the whole plane. The key counting lemma bounds forbidden profile classes by \exp(-\Omega(q\log q)). After the preliminary density and occupancy restrictions are imposed, this saving pays for both the possible covers and the \exp(O(q)) change of measure introduced by selection; the resulting almost-cover conclusion holds with probability tending to one under the changed law. Random line constructions and the counting of small covers through collinear subsets have precedents in Erdős and Lovász [8, Section 4]; Kahn subsequently developed the random-line approach further [14]. The profile argument here supplies the change-of-measure control needed for our selection law. We then apply the prime-plane stability theorem of Szőnyi and Weiner [19], also stated by Héger and Nagy [12], to turn an almost-cover into a large pencil. This is the step that requires q to be prime.

Finally, Section 6 combines the prescribed-choice bound with the original independent constituent offsets. It counts repeated generator directions and the additional incidences that a small local cover would require. Section 7 intersects the resulting successful events and applies the deterministic construction. Appendix A supplies three elementary estimates in a form independent of the construction; these are also the precise inputs used by the companion article.

Conventions. All logarithms are natural. An event holds with high probability if its probability tends to one along the orders under discussion. Constants in O(\cdot) may depend on parameters fixed before q varies. Every auxiliary constant is fixed independently of q; the final threshold may depend on those constants.

2 From modified line partitions to a hypergraph

The geometric data needed for the theorem have two jobs: preserve the intersection of point-edges after lines are split, and rule out every cover using at most q block labels. We formulate both requirements here and prove that they suffice. The later probabilistic sections will produce the data; all arguments in this section are deterministic and work over any finite field.

Let q\geq4 be a prime power, let A=\mathbb F_q^2, and let \mathcal G be the set of its q+1 directions. For g\in\mathcal G, write \mathcal L_g for the q affine lines of direction g, and put \mathcal L=\bigcup_g\mathcal L_g. The affine line of direction g through p\in A is denoted by p+g. We also use the projective completion \operatorname{PG}(2,q). Thus a common projective point of affine lines means either an ordinary point of concurrence or the point at infinity of a parallel class.

2.1 Merged pairs and four-point split lines

For every direction g, choose two distinct lines M_g^0,M_g^1\in\mathcal L_g. Call their union the merged pair in direction g, and call either of its lines a constituent. Write

If S\in\mathcal L_g\setminus\mathcal M, define a simple graph on the points of S: two distinct points are adjacent if they are the two intersections of S with M_d^0,M_d^1 for some d\ne g. Several directions may give the same adjacency; its multiplicity is irrelevant.

A tuple in direction g consists of four distinct directions d_0,d_1,d_2,d_3\in\mathcal G\setminus\{g\} and four bits \sigma_0,\sigma_1,\sigma_2,\sigma_3\in\{0,1\}. Indices on the tuple are read modulo 4. Define

The intersections exist uniquely because consecutive generator directions are different. Call the tuple valid if the following conditions hold:

1. 1.

   Its four points are distinct and lie on one line S\in\mathcal L_g\setminus\mathcal M.

2. 2.

   Neither \{u_0,u_2\} nor \{u_1,u_3\} is an adjacency on S.

3. 3.

   Every point of S\setminus\{u_0,u_1,u_2,u_3\} is adjacent to at most one of u_0,u_1,u_2,u_3.

We call S its split line and write F_S=\{u_0,u_1,u_2,u_3\}. Each consecutive pair \{u_{i-1},u_i\} is adjacent: the two points lie on the two different constituents of direction d_i. Consequently the two opposite pairs partition F_S, and every pair crossing that partition shares a merged pair.

Figure 1 records the partition and the shared merged blocks. The conditions on opposite pairs and external points will also control covers centered at a point of S.

We need two split lines in every direction. Index these requirements by slots (g,s), where g\in\mathcal G and s\in\{1,2\}, and choose a valid tuple in each slot. Write S_g^s for its split line. The choices are compatible if the following conditions hold for any two different slots:

1. 1.

   Neither chosen split line contains a designated point of the other tuple.

2. 2.

   The two sets of generator directions have intersection of size at most one.

3. 3.

   If the slots have the same target direction, no merged pair contains at least two designated points of one tuple and at least one designated point of the other.

The first condition makes all chosen split lines distinct and makes their designated point sets pairwise disjoint. In particular, there are exactly two split lines in each direction, both different from its two constituents. The second condition will be relevant to constructing such data; the deterministic implication below uses the first and third conditions.

Let \mathcal S be the set of chosen split lines, and define

There are exactly three lines of D in each direction. Compatibility gives

Indeed, R contains no point of S, and no other designated point set meets S.

The inclusion R_0\subseteq R gives two retained sets with different purposes. On R_0, one constituent of each merged block has disappeared, so a block cover becomes an ordinary line cover. The larger set R supplies points on the removed constituents when we later force a cover to choose their merged blocks. The four-point sets supply the final obstruction.

The following three properties express exactly what these sets must do. Fix 0<\rho<1 and an integer B\geq0.

Occupancy.

At most B constituent lines pass through any affine point. Every \ell\in\mathcal L\setminus D satisfies |\ell\cap R_0|\geq\rho q, and every M_g^1 satisfies |M_g^1\cap R|\geq\rho q.

Concentration of core covers.

If C\subseteq\mathcal L\setminus D, |C|\leq q, and the lines of C cover R_0, then at least (1-\rho/4)q lines of C pass through a common projective point.

The local condition.

For p\in A, define

\mathcal S(p)=\{S\in\mathcal S:p\in S\},\qquad b(p)=|\mathcal S(p)|,\qquad F(p)=\bigcup_{S\in\mathcal S(p)}F_S,

and

Z(p)=F(p)\cap \bigcup_{\substack{d\in\mathcal G,\ s\in\{0,1\}\\p\in M_d^s}} M_d^{1-s}. \tag{5}

Whenever b(p)\geq3, the set F(p) cannot be covered by Z(p) and at most b(p)-1 additional sets of the following types: sets of at most two points; affine lines outside \mathcal S(p)\cup\mathcal M; and merged pairs M_d^0\cup M_d^1, with no merged pair used more than once.

All these are properties of a specified finite configuration. In particular, none asserts that such a configuration exists.

2.2 Partitions and intersecting edges

We prove Proposition 2.1 in three stages: construct the balanced partitions, reduce a small cover to one pencil, and test the designated points against its remaining budget.

For each g\in\mathcal G, partition X into these blocks:

• •

  \ell\cap X for every regular line \ell\in\mathcal L_g, where “regular” excludes the two split lines and the two constituents in that direction;

• •

  (M_g^0\cup M_g^1)\cap X;

• •

  \{u_0,u_2\} and \{u_1,u_3\} for each of its two split lines, using that line’s tuple ordering.

Distinct lines of \mathcal L_g are disjoint and partition A, so (4) proves that these blocks partition X. There are (q-4)+1+4=q+1 of them. The split blocks have two points. Every regular block is nonempty by the lower bound on |\ell\cap R_0|, and the merged block is nonempty by the same lower bound for M_g^0.

Let V_g consist of distinct labels for these blocks; choose disjoint label sets for different directions. A point x\in X defines an edge e_x containing, for each g, the unique label of the block containing x. Thus every edge contains exactly one vertex from each of the q+1 parts. Every label occurs in an edge because its block is nonempty.

For different x,y\in X, let \ell be their joining line and let g be its direction. If \ell is not a split line, then x,y are in the same regular or merged block of V_g. If \ell is a split line, both points are designated by (4). They either belong to the same opposite-pair block or form consecutive positions in its four-cycle. In the latter case they share the merged block of the corresponding generator direction. Hence e_x\cap e_y\ne\varnothing.

Repeated edges would not affect the cover argument, but they do not occur here. If e_x=e_y for different x,y, then in every direction h different from the direction of their joining line they lie on different h-lines. Their only possible common block in V_h is therefore the merged block. The point x would lie on a constituent in each of these q directions, contradicting B<q, which follows from (6). Thus x\mapsto e_x is injective.

Selecting labels covers all edges if and only if the corresponding blocks cover X. We will show that at least q+1 blocks are needed. The reverse bound follows because all labels in any one part cover every edge.

2.3 Forcing the nonsplit members of a pencil

We have obtained an intersecting hypergraph with the required part sizes and no isolated vertices. Its covering number is the minimum number of blocks covering X. We now use R_0 to locate any hypothetical small cover, then use occupancy on R_0 and R to force its nonsplit blocks.

Suppose that a collection \mathcal B of at most q labels covers X. A split block misses R_0. On R_0, a merged block is exactly M_g^0\cap R_0, because M_g^1\in D. Associate to each selected regular block its line and to each selected merged block the line M_g^0. These representative lines are distinct, belong to \mathcal L\setminus D, and cover R_0. Concentration of core covers provides a projective point P lying on at least (1-\rho/4)q selected representatives. Write t for the number of selected labels that do not have a representative through P, including all selected split labels. Then

We treat separately a parallel pencil and a pencil through an affine point.

A point at infinity. Suppose P is the point at infinity of direction g. Every one of the q-3 lines of \mathcal L_g\setminus D must be a selected representative. Otherwise an omitted such line has at least \rho q points in R_0, none covered by the parallel representatives through P, while all remaining representatives cover at most t of them. Split blocks cover none of R_0, and t<\rho q.

The corresponding q-3 selected blocks cover none of the eight designated points on the two split lines of direction g. An additional regular block covers at most one point on each of those lines, and a split block has size two. A merged pair of direction g misses both split lines. A merged pair of any other direction has at most two designated points on each split line; if it had at least three altogether, it would have at least two on one and at least one on the other, contrary to the third compatibility condition. Thus every additional block covers at most two of these eight points. At most three labels remain in the cover budget, so a cover is impossible.

An affine point. Now let P=p\in A. We first show that for each direction g such that p+g is not a split line, the selected labels must include its regular block or, when p+g is a constituent, its merged block.

If \ell=p+g\notin D and its block is omitted, selected representatives through p cover at most the point p on \ell. All other representatives cover at most another t points there. This contradicts

The strict inequality follows from (6).

The only remaining nonsplit case is \ell=p+g=M_g^1. Suppose its merged block is omitted. A selected regular block represented through p meets \ell only possibly at p. A selected merged block represented through p consists of a constituent M_d^0 through p and its partner M_d^1. The former meets \ell at p, and the latter contributes at most one additional point. None of these lines equals \ell, because its own merged block was omitted. There are at most B such partners, by the constituent multiplicity bound at p. Hence all selected blocks represented through p cover at most 1+B points on \ell. Every other selected block covers at most two points on \ell: regular lines meet it in at most one, merged pairs in at most two, and split blocks have size two. Occupancy on R now gives the contradiction

This proves the claimed necessity of the block in every nonsplit direction.

Put b=b(p). The split lines through p have distinct directions, because distinct parallel lines do not meet. The claim therefore requires q+1-b distinct labels, leaving room for at most b-1 more. It remains to check the designated points on those split lines.

2.4 The remaining designated points

For an affine center p, the nonsplit directions have forced q+1-b labels, where b=b(p). The possible cover therefore has at most b-1 labels left. The following cases show that the designated points on its b split lines cannot be covered within that budget.

If b=0, the required q+1 labels already exceed the budget. If b=1, write S for the unique split line through p. Exactly q labels are required, so no additional label is available. On F_S their blocks can cover only p itself, when p\in F_S, and points adjacent to p on S: regular lines through p supply only p, and a merged pair through p supplies only its partner intersection. If p=u_i is designated, its opposite point u_{i+2} is not adjacent to it and is missed. If p\notin F_S, validity allows at most one designated point adjacent to p. In either case F_S is not covered.

Suppose now that b\geq2. Compatibility implies that p is not designated on any split line through it: otherwise that point would lie on a second chosen split line. The designated sets on these lines are pairwise disjoint, so |F(p)|=4b. A required regular block through p meets any such split line only at p and therefore misses its designated points. A required merged block has one constituent through p and can cover designated points only with its partner. Thus the required blocks cover a subset of Z(p).

For each S\in\mathcal S(p), every point in Z(p)\cap F_S is adjacent to the external point p in the graph on S. Validity gives |Z(p)\cap F_S|\leq1, and consequently

If b=2, at most one additional block is available. A regular line meets the two split lines in at most two points, a merged pair in at most four, and a split block has two points. Hence this extra block together with Z(p) covers at most 4+2<8=|F(p)| points.

Finally, let b\geq3. Each of the at most b-1 additional labels is represented on F(p) by one of the sets allowed in the local condition: a split block has two points, a regular line is outside \mathcal S(p)\cup\mathcal M, and a merged block is contained in its merged pair. No merged pair is repeated because it has only one label. The local condition therefore rules out covering F(p). This is the last possible case, completing the proof of Proposition 2.1.

3 Deletion lines and concentration of core covers

The deterministic construction asks for rigidity of line covers of the core R_0. We establish that rigidity in two steps. First, after a fixed number of lines in each direction are deleted, with probability tending to one every cover of the surviving set by at most q other lines also covers almost all of the plane. Second, over a prime field, the Szőnyi–Weiner stability theorem puts almost all lines of such an almost-cover in one pencil.

The deletion law matters. Our eventual split lines come from a constrained selection, so their law is not uniform. We prove the first step for any law whose probability at each deletion set is at most \exp(Kq) times its uniform probability, with K fixed. A qualitative estimate for uniform deletion would not suffice under this change of measure.

Throughout this section, q tends to infinity through prime powers and A=\mathbb F_q^2. Let \mathcal L be its q(q+1) affine lines. Primality will be required only for the final application of projective stability. Fix an integer k\ge1. For q\ge k, let \mathsf U_{q,k} be the uniform law on sets D\subseteq\mathcal L containing exactly k lines in each direction. Define

For probability measures on a countable set, total variation distance is one half of the sum of the absolute coordinate differences.

Part (iii) is the cover statement needed for the construction. The first two parts provide its input: the surviving density and the occupancy of all but a sublinear number of lines. We prove them in that order using one counting principle.

For a proposed witness C of size m, expose the lines of D and C in a carefully chosen random order. For a positive proportion of orders, their point-multiplicity profiles will force more than m exposures at which the next line has atypical occupancy. In the counting experiment, where D and C are themselves sampled, each such step has conditional probability O(q^{-1}). The first m savings pay for the at most q^m\exp(O(q)) witnesses; the remaining positive proportion of steps pays for e^{Kq}. Erdős and Lovász [8, Section 4] count small covers by their collinear subsets in a random-line construction; Kahn [14] subsequently strengthened the random-line result. The profile count below provides the uniform change-of-measure control used here.

3.1 Profiles and incidence identities

Consider disjoint sets D,C with D as above and m=|C|\le q. Put j_C(x)=|\{\ell\in C:x\in\ell\}| and define the plane profile and the profile of a line \ell\in D\cup C by

All indices in these arrays are nonnegative integers. A coordinate with a negative index is understood to be zero.

The mean of i+j in the plane is (k(q+1)+m)/q. On any one of the listed lines it is at most

because every other distinct line meets it in at most one point. Thus all these arrays belong to the space \mathscr P of probability arrays on \mathbb Z_{\ge0}^2 whose mean of i+j is at most M=2k+4. Give \mathscr P the topology of coordinatewise convergence.

This space is compact and metrizable. Indeed the mass outside \{i+j\le B\} is at most M/(B+1), uniformly over the space. A diagonal subsequence of any sequence therefore has total mass one, and its mean bound follows from Fatou’s lemma. The same tail estimate shows that coordinatewise convergence in \mathscr P implies convergence in total variation. In particular every bounded sum of selected coordinates, such as x\mapsto\sum_jx_{0j}, is continuous.

From any sequence of pairs (D,C), we may consequently extract a subsequence such that

The last two limits are weak limits of finite measures on \mathscr P. Their masses are k and c. The measure \nu_D is supported on profiles with x_{0j}=0, and \nu_C on profiles with x_{i0}=0; these restrictions are closed. For each fixed i,j, counting incidences before taking the limit gives

Summing these identities by Tonelli’s theorem yields

This argument is necessary: convergence in total variation alone would not justify passage to these unbounded first moments.

The next distinction identifies exactly which line profiles can create an atypical exposure. If a line of type D sampled the surrounding plane without bias, its own contribution would merely add one to the first multiplicity coordinate. The analogous shift for a C-line is in the second coordinate.

Relative to the limiting plane profile P, call a profile of type D invisible if x_{ij}=P_{i-1,j} for every i,j, and a profile of type C invisible if x_{ij}=P_{i,j-1} for every i,j. A profile which is not invisible is called visible. The terminology refers only to the following exposure test.

3.2 The three deletion estimates

3.3 From almost covering the plane to a pencil

The deletion theorem leaves only a geometric question: how can at most q lines cover all but a small proportion of an affine plane? An earlier stability lemma of Erdős and Lovász [8, Section 4, proof of Theorem 10, part II] forces almost all of a set of q projective points onto one line when it has sufficiently few disjoint lines. Over prime fields, Szőnyi and Weiner allow a sufficiently small constant multiple of q^2 disjoint lines. This is the scale needed after our deletion estimate.

The external geometric input is the stability theorem of Szőnyi and Weiner [19, Theorem 4], also reproduced by Héger and Nagy [12, Result 3.6]. If q is prime and B\subseteq\mathrm{PG}(2,q) has

where \beta>0 and \Delta counts the projective lines disjoint from B, then some projective line contains at least q-2\Delta/(q+1) points of B. We use only the following consequence, with explicit constants to fix its quantifiers.

4 Random merged pairs and their candidate graph

The construction in Section 2 calls for two compatible split lines in every direction. We begin by supplying many valid choices for each of these lines. We also record which choices conflict: besides having large sets of candidates, we need their conflict graph to have controlled degrees and, apart from a small specified set, controlled codegrees.

Throughout this section, M_g^0 and M_g^1 are sampled independently and uniformly from \mathcal L_g, independently for different directions g. This sampling law allows the two constituents in a direction to coincide. In that case they create no adjacency between distinct points on a target line. With this convention the tuple validity tests of Section 2 apply throughout the sampling space and agree with the original tests whenever every constituent pair is distinct. We impose distinctness only after obtaining the estimates below.

A successful tuple in direction g is a choice of four distinct generators d_0,d_1,d_2,d_3\ne g and bits \sigma_0,\ldots,\sigma_3 such that

are four distinct points on one g-line. Thus success concerns only alignment and distinctness. A valid tuple must also pass the additional tests in Section 2: its target line is not a constituent, neither opposite pair is adjacent, and no external point on the target line is adjacent to two designated positions.

For each line supporting valid tuples, retain one of them by a fixed deterministic rule. Let Q_g be the resulting set of tuples in direction g. In particular, distinct members of Q_g have distinct target lines. Each of the two slots (g,1),(g,2) carries a copy of Q_g. These copies form the vertices of a graph: two vertices in different slots are joined exactly when their tuples fail a compatibility condition from Section 2; vertices in the same slot are not joined. Choosing one vertex from each slot with no edges among the chosen vertices is therefore precisely a compatible choice of the required tuples. For a vertex v, write L_v for its line, F_v for its four designated points, \Gamma_v for its generator set, and N(v) for its graph neighborhood.

The proof has two counting stages. First we count successful tuples and show that, after the validity tests, they occupy linearly many distinct lines. We then bound incidences among tuples, their designated points, and test lines; these estimates will give the graph bounds. A moment argument supplies the uniform tail estimates at both stages. All counts refer to the independent sampling law above, without conditioning on a later selection of compatible split lines.

4.1 A moment argument for small patterns

When discussing exposure of the random choices, we call a direction a colour; its variable is the pair of random offsets specifying its two constituents. A labelled pattern tests a bounded number of these variables. Although different patterns may share colours, their counts can be controlled if the same expectation bound holds after any bounded exposure. The next lemma states the two forms we need. Constants may depend on the fixed moment order and on the number of exposed colours, but not on q or on the values exposed.

We use part (i) for counts whose expectations remain bounded and part (ii) for counts of order q that must concentrate about their means. Fix

By taking a sufficiently large fixed moment in (i), the probability that such a count exceeds q^\theta is smaller than any prescribed inverse power of q. Part (ii) gives probability O_s(q^{-s}) for a deviation by a fixed positive multiple of q. Both conclusions can consequently be imposed over polynomially many tests.

We now verify the basic conditional counts for tuples. Fix a bounded exposed colour set K. If a tuple has j generators in K, let f count its positions whose two incident generators are both exposed. The cyclic arrangement of the four generators gives

Every other position uses fresh offset variables, disjoint from those used by the other nonfixed positions. Such a position is uniform in the plane or on a fixed constituent whose direction differs from the target. In either case its coordinate specifying a target parallel line is uniform, independently of those of the other nonfixed positions.

For a fixed target direction, alignment therefore has probability at most q^{-3} when f=0, and at most q^{-(4-f)} when f\ge1. There are O_K(q^{4-j}) generator and bit assignments. Summing over j shows that the conditional expected number of successful tuples in a fixed direction is O_K(q), and that the count using an exposed generator is O_K(1). If the target line itself is prescribed, every nonfixed position must lie on that line. We can then use q^{-(4-f)} also when f=0, giving conditional total O_K(1) on the prescribed line.

When all generators are exposed, we must also keep the distinctness requirement in the definition of success. Four distinct fixed positions can succeed in at most one target direction. We use this observation whenever we sum fully exposed tuples over targets; otherwise such a sum would introduce a spurious factor of q.

4.2 Many distinct valid lines

There are two obstacles to obtaining large sets Q_g: several successful tuples may lie on the same line, and some successful tuples may fail validity. We first control the concentration on individual lines, then count the validity failures.

Let H_g be the number of ordered successful tuples in direction g. Before alignment is imposed, the four positions of a tuple are independent uniform affine points: each uses two offsets of different generators, and all eight offsets are used once. There are 16(q)_4 prescriptions, where (q)_4=q(q-1)(q-2)(q-3), so

Let Y_g be the sum over g-lines of the square of the number of successful tuples on that line. Equivalently, Y_g counts ordered pairs of successful tuples with a common target line. After bounded colour exposure, choose the first tuple at expected cost O(q); exposing its colours then makes its target line specified, so the second tuple costs O(1). If the pair is required to use an already exposed colour, start with a tuple having that overlap, at cost O(1), and again count the second on its specified line at cost O(1).

These are exactly the conditional total and overlap bounds in Lemma 4.2(ii), for both H_g and Y_g; in particular, \E Y_g=O(q). Its tail estimate and a union bound give, with probability 1-o(1) simultaneously for every g,

for an absolute constant C_1.

We next show that only O(q^\theta) successful tuples in each direction fail the extra validity tests, with probability 1-o(1) uniformly over directions. For each failure, count the tuple together with a bounded witness of that failure; overcounting is harmless. In each of the three cases below the conditional expected witness count is O(1) after any bounded further colour exposure. Lemma 4.2(i) then supplies the required tail bound.

A constituent target line. First fix the two offsets of g. The target must be one of the two specified constituent lines, and the prescribed-line estimate gives conditional total O(1).

An opposite adjacency. A witness consists of an extra colour and an orientation pairing two opposite positions. This colour is neither the target nor a generator: a generator pairs consecutive positions. If the witness colour is fresh, first expose a successful tuple, at expected cost O(q). The choices for the witness then cost O(q)q^{-2}=O(q^{-1}), giving total O(1).

If the witness colour is already exposed, distinguish whether a tuple generator also overlaps the exposure. With such an overlap the basic tuple count is O(1). With all tuple generators fresh, enumerate the target line instead. The exposed witness forces two exact positions on that line, and the other two positions must lie on it. For fixed labels and line this costs at most q^{-6}, against O(q^5) choices of line and tuple labels. This case also has conditional total O(1).

An external point adjacent to two positions. Here the witness consists of two distinct extra colours, their orientations, and their common external point w on the target line. Tuple generators cannot witness this condition. If both witness colours are fresh, expose a successful tuple first. There are then O(q^2) colour choices and q choices for w, each with probability at most q^{-4}. Their total cost is O(q^{-1}), against the O(q) cost of the tuple.

If a witness colour is exposed, first specify that colour and its orientation. For a tuple overlapping the exposure, the tuple costs O(1), and w is forced after the tuple’s offsets are exposed. The other witness costs O(1) if it is exposed and O(q^{-1}) if it is fresh. If instead all tuple generators are fresh, enumerate the target line: the exposed witness prescribes w and one exact tuple position. For fixed labels and line the tuple costs at most q^{-5}, against O(q^5) choices. The remaining witness still costs at most O(1).

These witnesses exhaust the extra validity failures. Subtracting their counts from H_g in (20) leaves linearly many valid tuples. Cauchy–Schwarz, together with Y_g\le C_1q, shows that these tuples occupy at least c_*q distinct lines. Retaining one tuple on each such line gives |Q_g|\ge c_*q; the upper bound |Q_g|\le q follows from the number of lines in a parallel class. This proves Proposition 4.1(i).

4.3 Incidence estimates for candidates

We have obtained enough candidates in every direction. To control their conflicts, we now count tuples with prescribed point and line incidences. All counts in this subsection include every successful tuple before retention. They therefore bound the corresponding retained counts, and their two slot copies change the bounds by at most a factor of two.

The following assertions hold simultaneously with probability 1-o(1):

1. (a)

   For a fixed target g and any line \ell, at most q^\theta successful tuples designate a point on \ell.

2. (b)

   For any nonconstituent line \ell, at most C_2q successful tuples, over all targets, designate a point on \ell.

3. (c)

   For any two distinct specified generators, at most q^\theta successful tuples, over all targets, use both.

4. (d)

   Each of the following counts, over all targets, is at most q^\theta: tuples designating a specified point y; tuples whose line passes through y and which designate a point on a specified line K not containing y; and tuples having two different designated positions on two specified distinct nonconstituent lines, one on each.

Assertions (a) and (b) control point-on-line conflicts within a slot and over all slots, respectively. Assertion (c) controls conflicts from shared generators. The more constrained incidences in (d) will control common neighborhoods. To obtain simultaneous bounds, we verify the conditional counts required by the moment lemma for each assertion.

For (a), a tuple with no exposed generator has probability at most 4q^{-4}: alignment costs q^{-3}, and a designated hit on the fixed line costs a further q^{-1}. This remains true whether the hit forces the target line or one point on it. Tuples overlapping the exposure have conditional total O(1) by the basic fixed-target bound. Thus the bounded-total estimate of Lemma 4.2(i) applies.

For (b), let h be the direction of \ell and first condition on the offsets of h avoiding \ell, as required for \ell to be a nonconstituent. Target direction h itself is covered by (a). For the other targets, let j count generators in a bounded exposed set that includes h. When j=0, the expected total is O(q). When j=1, there are O(q^4) assignments including the target, and the hit probability is at most 4q^{-4}. To see the additional factor needed here, condition on the common target-line coordinate. A fresh position hits \ell with probability q^{-1}, while a position on an exposed constituent can hit \ell for at most one common coordinate, since that constituent is not \ell.

For j=2,3, the crude success probabilities q^{-3},q^{-2} suffice against O(q^3),O(q^2) assignments. For j=4, the distinct fixed positions allow at most one target. Hence all overlap counts are O(1). Tuples using h satisfy the bounded-total estimate of Lemma 4.2(i). Those not using h satisfy its centered estimate under the initial conditioning on h, with mean O(q) uniformly. This proves (b), including a union bound over test lines and the possible fixed offsets of h.

For (c), initially condition on the two specified generators. The across-target estimates for j\ge2 in the preceding paragraph did not use the requirement of a hit on \ell. They therefore give conditional total O(1) after any bounded further exposure, as required by Lemma 4.2(i).

For either of the first two tests in (d), choosing the target direction prescribes the target line and one exact position on it. With j=0 the probability per assignment is at most 4q^{-5}, and with j=1 it is O(q^{-4}). In the latter case, even when the exact position is constrained to an exposed constituent, specifying it costs at least q^{-1}; each of the other three positions must lie on the prescribed target line. The across-target bounds for j\ge2 suffice as before.

For the last test in (d), condition on the offsets in the direction or directions of the two test lines, avoiding those lines. For a target different from these directions, requiring two different positions to meet the two lines costs two further factors q^{-1} when j=0, and at least one further factor when j=1. Use the crude success bounds when j\ge2. If the target equals a test direction, its line must be the specified test line; the prescribed-line estimate then suffices. Thus every test in (d) has conditional total O(1).

There are only polynomially many tests in (a)–(d). Arbitrarily high fixed moments and a union bound prove the assertions. All estimates made after initial conditioning are uniform in the allowed fixed offsets, so averaging over those offsets preserves the bounds.

4.4 Degrees, codegrees, and initial occupancy

We now translate the incidence estimates into the graph assertions of Proposition 4.1. For the first compatibility condition, the two ways a conflict can occur are represented by

The one-per-line retention rule gives |B_v|=O(q) and at most four members of B_v in any slot. Since a valid tuple’s line L_v is not a constituent, (b) gives |E_v|=O(q); (a) gives at most q^\theta members of E_v in any slot.

The other compatibility conditions contribute fewer conflicts. Two shared generators give O(q^\theta) vertices by (c). For the condition on slots with the same target direction, every merged pair witnessing a conflict meets F_v. Once the constituent multiplicity estimate below holds, there are at most 4\lceil\log q\rceil such pairs. Assertion (a), applied to their constituents in the other slot of this direction, bounds the candidates they meet. These conflicts contribute O(q^\theta\lceil\log q\rceil) vertices. Together the three types give the required degree bounds.

For codegrees, the exceptional set has a direct geometric description. Define J(v) to consist of vertices on the same line as v or sharing a designated point with v. The retention rule and the first test in (d) give |J(v)|=O(1+q^\theta). Every member is either in v’s slot or adjacent to v, as asserted in part (iii).

Fix w\notin J(v). Then L_v,L_w are distinct and F_v,F_w are disjoint. We first bound common neighbors arising from the first compatibility condition, by considering the four intersections of their B and E sets. A member of B_v\cap B_w has a line joining a point of F_v to a point of F_w. There are only a bounded number of such lines, hence a bounded number of candidate vertices by retention.

For B_v\cap E_w, choose y\in F_v on the candidate line. If y\notin L_w, the point-line test in (d) applies. If y\in L_w, the candidate line is either L_w, or its designated point on L_w must be y. The one-per-line rule and the point test in (d) handle these two possibilities. The same argument bounds E_v\cap B_w. Finally, a member of E_v\cap E_w either has two different designated positions on L_v,L_w, or designates their intersection. The last or first test in (d), respectively, applies.

The remaining conflict types add at most O(q^\theta\lceil\log q\rceil) to these common-neighbor bounds, by the bounds already used for degrees. Since \theta<\beta=1/8, the exceptional-set size, codegree bounds, and within-slot degree bounds are all at most q^\beta for sufficiently large q. This proves parts (ii) and (iii), subject only to the multiplicity estimate we now establish along with the rest of part (iv).

The number of constituents through a fixed affine point has distribution \operatorname{Bin}(2(q+1),1/q), counting multiplicity. Its tail at \lceil\log q\rceil is q^{-\omega(1)}, so a union bound over the q^2 affine points proves the multiplicity estimate.

For the uncovered-point estimate, fix a line \ell of direction h. The q lines M_g^1 with g\ne h hit \ell at independent uniform points. If U_\ell counts points missed by these hits, then

Changing one hit changes U_\ell by at most one. Apply Lemma A.3 to these q independent trials with L=1, and then Lemma A.2 to their exposure martingale. Since (1-1/q)^q\to e^{-1}>1/5, there is a fixed \delta>0 such that \E U_\ell-q/5\ge\delta q for all sufficiently large q. Taking deviation u=\delta q, a fixed positive multiple of q, gives probability \exp(-\Omega(q)) that U_\ell<q/5. If \ell\ne M_h^1, the remaining parallel line M_h^1 does not meet it. A union bound over all lines therefore proves the uncovered-point assertion in (iv).

All failure probabilities above sum to o(1) in the independent sampling model. Independently across directions, the probability that each constituent pair is distinct is

Intersecting this event with the event of probability 1-o(1) just proved gives the final assertion of Proposition 4.1.

5 Selecting split lines

The candidate graph supplies many choices in each slot; we must now choose one vertex from every slot without creating a conflict. We need two further properties of this choice. First, an event prescribing the chosen vertices in several slots must have small probability. Such an event is called a cylinder, and its bound will allow us to count exceptional pencil configurations. Second, the chosen split lines must leave a positive proportion of the initially available points on every affine line.

We prove these properties together in a graph statement whose bounds are uniform over all inputs satisfying the hypotheses. The cylinder bound includes the event that the procedure succeeds; we do not condition the individual choices on eventual success.

The selection has two stages. In the main stage we repeatedly choose a slot and a vertex, delete conflicts, and thin the remaining choices so that every vertex has the same survival probability. Domain sizes then decrease at a common rate. Remaining degrees decrease faster, because the chosen slot also disappears. We show that this difference leaves a sparse enough graph to complete the last slots by the local lemma. Partial random selection followed by local-lemma completion also appears in Loh and Sudakov [16, Section 4]. Here we additionally track occupancy on each affine line and prove a cylinder bound for the complete returned transversal.

The main technical issue is concentration of the remaining degrees. A choice in J(v) can delete many neighbors of v, but it also kills v or removes its slot. We will use this implication to stop tracking v after such a choice, without losing any degree estimate needed for a subsequent step.

5.1 The main selection process

We first specify the main stage, including the events on which it aborts. Choose the constants P_*,s_{\min},B_*,\rho,a in the displayed order, and define the q-dependent parameters \alpha,h_0,t_{\max} alongside them:

All subsequent assertions concern sufficiently large q. The main stage runs for at most t_{\max} steps, leaving h_0 slots if it reaches completion. At time t, before the next step, let I(t) be the remaining slots, h(t)=n-t, and Q_i(t) their domains of vertices still alive. Put

Initially all slots and vertices are present. The factors s(t) and b(t) will be the respective scales for domain sizes and remaining degrees. Throughout 0\le t\le t_{\max},

Indeed n\le3q, h(t)\ge aq, and \log(1-P_*/q)\ge-2P_*/q for large q.

Each main step begins with two checks. First, abort if some remaining domain satisfies

For every alive vertex v in a remaining slot define

Here r_v(t) is the probability that a uniform choice from a uniformly chosen remaining slot is adjacent to v. The second check aborts if any such r_v(t)>\alpha.

If both checks pass, choose a uniform slot G\in I(t) and then a uniform vertex W\in Q_G(t). Record W as the choice for G and delete all its neighbors. For every vertex u alive before this step and not adjacent to W, independently delete it with probability

Compute all rates before choosing G,W. The pre-step checks ensure 0\le\lambda_u\le\alpha<1. For the estimates below, perform this thinning hypothetically in slot G as well: the recorded choice W is retained regardless of its hypothetical deletion. Finally remove slot G. Thus, before slot removal, every previously alive vertex has the same conditional survival probability:

A final check takes place after the step. Count the thinning deletions in each domain present at its start and in each set N(v)\cap\bigcup_{i\in I(t)}Q_i(t) then counted by a D_v(t). Abort if any such count exceeds q^\beta, including hypothetical thinning in G. This check limits the size of the increments used in the concentration argument.

The probability of a post-step abort is small uniformly over all histories that pass the pre-step checks. Conditional on such a history and on G,W, each tested count is a sum of independent Bernoulli variables with total mean at most \mu_*=P_*\max\{1,C_*\}. For such a sum Z and any integer k\ge1,

The middle inequality follows by expanding the factorial moment and bounding the sum of products of k distinct success probabilities by \mu_*^k/k!. With k=\lfloor q^\beta\rfloor+1, the final bound, denoted \varepsilon_q, is smaller than q^{-m} for every fixed m once q is sufficiently large. There are O(q^2) tested sets per step and at most 3q steps. Thus any post-step abort has probability O(q^3\varepsilon_q)=o(1).

5.2 Concentration with stopping and censoring

We now show that the main stage reaches the last h_0 slots with large domains and small remaining degrees. Let \mathcal F_t be the original history just before the next random slot and vertex are chosen. All conditional expectations in this subsection use this filtration; in particular, the next slot is still uniform among the remaining slots.

We use auxiliary processes that agree with the quantities of interest until they are stopped. Stopping means holding the last value fixed. A pre-step abort produces no increment. A performed step contributes its specified increment before any post-step stop. When a large decrement is censored below, only the auxiliary update is replaced; the actual selection procedure is unchanged.

The concentration tool is Lemma A.2, the appendix form of the Azuma–Hoeffding estimate [4]. For an adapted process X_t with |X_{t+1}-X_t|\le L for 0\le t<T, put d_t=\E[X_{t+1}-X_t\mid\mathcal F_t]. Its fixed-time conclusion is

The stopped auxiliary processes satisfy the same increment hypothesis. For domain sizes we will bound the absolute accumulated drift; for degrees an upper bound suffices, and for occupancy we will use a lower bound.

Domain sizes. For each initial slot i, begin an auxiliary process at L_i(0) and track L_i(t)/s(t) while the slot remains present. In a performed step, let L_i^+ be its size after conflicts and thinning but before removing G. This definition includes the hypothetical update when G=i. Equal survival in (34) gives

If this domain’s thinning count exceeds q^\beta, replace the numerator L_i^+ by L_i(t), update the auxiliary value to L_i(t)/s(t+1), and then stop it. Otherwise update to the true value L_i^+/s(t+1) and stop after this update if G=i or if the whole process aborts. Until such a stop, the auxiliary process agrees with L_i(t)/s(t).

The replacement changes the conditional expectation of the numerator by at most q\varepsilon_q. Consequently the conditional drift of this rescaled track has absolute value at most q\varepsilon_q/s_{\min}. Its increments are O(q^\beta): there are at most q^\beta conflict deletions in a slot by (21), and at most q^\beta thinning deletions on a step without replacement. The scaling change contributes only O(1), by (30). On a replaced step the scaling change is the only contribution.

Remaining degrees. For each initial vertex v, begin at D_v(0) and track D_v(t)/b(t) while v is alive and its slot remains present. The faster scale b(t) accounts for the removal of the chosen slot. To verify the required drift, let \widetilde D_v be the true updated neighbor count after a performed step, including removal of G, whether or not v itself survives. For each currently counted neighbor u, its probability of surviving before slot removal is 1-\alpha. If u’s own slot is chosen, it cannot conflict with W, because there are no within-slot edges. Therefore

Subtracting this slot-removal probability from 1-\alpha and summing over the currently counted neighbors gives

We next bound the increments. When W\notin J(v), conflicts remove at most q^\beta counted neighbors by (22), and slot removal costs at most q^\beta by (21). If instead W\in J(v), or if the thinning count in the current neighbor set exceeds q^\beta, censor the auxiliary update: replace \widetilde D_v by D_v(t), update to D_v(t)/b(t+1), and then stop the track. In every other case update to \widetilde D_v/b(t+1), and then stop if v has died, its slot has been removed, or the whole process has aborted.

The exceptional choice has conditional probability at most

Since D_v(t)\le C_*q, censoring increases the numerator’s conditional expectation by at most O(q^{\beta-1})+C_*q\varepsilon_q. By (38) and (30), the rescaled track thus has conditional drift at most O(q^{\beta-1}). Its increments have absolute value O(q^\beta). Without replacement the raw decrement is at most 3q^\beta; with replacement it is zero. The relative change of b(t) is O(1/q), uniformly because h(t)\ge aq, so its scaling contribution is again O(1).

This is the point at which we use the location of the exceptional set J(v), not just its size. If W\in J(v), then W is adjacent to v or belongs to its slot. After this step v is therefore dead or its slot has been removed. A track stopped for this reason can never be needed at a later barrier check.

Simultaneous estimates and absence of aborts. The domain and degree processes now have the bounded increments and drift estimates needed for (36). Apply that fixed-time bound with deviation q^{4/5}/2 separately to each track and each time. There are O(q^2) tracks and O(q) times. The individual exceptional probability is at most

The total absolute drift of a domain-size track is o(1) and the total upper drift of a degree track is O(q^\beta). It follows, by a union bound and by s(t),b(t)\le1, that with probability 1-o(1),

at every time when the auxiliary values still agree with the true rescaled quantities.

We can now rule out aborts. Exclude the post-step abort event, whose probability was already bounded by o(1). At a putative first pre-step abort, every remaining slot and every alive vertex still has a track agreeing with its true rescaled quantity. A previous thinning censorship would have caused a post-step abort, and a previous exceptional choice would have killed the vertex or removed its slot. Thus (40) applies at this abort check itself. Its first inequality rules out (31) for large q. The second gives

The error is uniform for s(t)\ge s_{\min} and h(t)\ge aq. Thus no pre-step abort occurs on this event.

To prepare the completion, make one final check at t=t_{\max}. Abort unless the remaining minimum domain size L_{\min} and maximum degree \Delta satisfy

The same estimates imply

Therefore the main process reaches and passes its final check with probability 1-o(1), uniformly in its input graph.

5.3 Keeping points on every line

The preceding estimates control the available vertices. We next control the points left on affine lines, under the additional geometric hypotheses of Proposition 5.1. Fix a line \ell, start with T_\ell, and remove its intersections with the main selected lines other than \ell. Write T(t) for the number of points still present. Each step decreases T(t) by at most one.

Consider a slot whose direction differs from that of \ell. Conditional on the current history, at most T(t) candidate lines in that slot meet a remaining point: each such line is determined by its intersection with \ell, and the assignment of lines within a slot is injective. A line in the same direction as \ell makes no deletion under our convention. The size barrier therefore gives

Track T(t)/(1-B_*/q)^t, freezing on an abort and including a performed step’s increment before a post-step freeze. For t\le3q its denominator is at least e^{-6B_*}. Its conditional drift is nonnegative, and its increments have bounded absolute value independently of q: the raw size changes by at most one and T(t)\le q controls the change of scale.

Apply the lower-tail consequence of (36) to these stopped processes and take a union bound over the q(q+1) affine lines. The probability that the main stage completes while some line has final main size below

is o(1). Any completion on the remaining h_0 slots removes at most h_0 further points from any one line. By a<\rho/2 and h_0=\lceil aq\rceil, the terminal sizes are at least \rho q for large q. Thus the required occupancy estimate will hold for every successful tail completion on these histories.

5.4 Completing the last slots

After (42), the remaining graph is sparse enough for the Lovász local lemma. We need both an independent transversal and a bound on prescribed choices under the law used to choose it. The following conditional form supplies both, using the local-lemma argument of Erdős and Lovász [8, Section 2].

For every history passing (42), choose the tail according to the conditioned law in Lemma 5.2. Its hypotheses hold for large q, since the check also gives L_{\min}\ge s_{\min}c_*q/2\ge3. The tail choices are mutually compatible, and the earlier neighbor deletions make them compatible with every main choice. There is no further failure. We have proved (23); the occupancy estimate, which allowed any successful completion of the last h_0 slots, also proves (25).

5.5 Cylinder probabilities for the whole selection

The remaining claim is (24). We must bound the probability of prescribed choices jointly with success, without conditioning a main choice on the later success of the procedure. For this purpose, realize the random slot order by sampling a uniform permutation \pi of all slots at the outset and using its first n-h_0 entries. Choose \pi independently of all randomness for vertex choices and thinning. This is the same process as before: the rates and abort decisions use no unexposed part of \pi, and its next entry is uniform among the remaining slots in the original filtration.

Only now, for the cylinder calculation, condition on the entire permutation. This divides the prescribed slots deterministically into s_{\rm m} main slots and s_{\rm t} tail slots, with s_{\rm m}+s_{\rm t}=s. At any prescribed main slot reached before abort, the vertex is still uniform in its current domain when \pi is fixed. The pre-step size barrier therefore bounds the probability of its prescribed value by

Multiplication of these conditional upper bounds at the specified main steps bounds the probability of reaching and satisfying them all. An intervening abort only lowers that probability. Given any completed history passing the tail check, Lemma 5.2 bounds the tail prescription by

Taking conditional expectations backwards from the tail and then through the prescribed main steps gives

Average over \pi and take

This proves (24) and completes Proposition 5.1. The two uses of the slot order are distinct: all drift estimates were taken in the original filtration, where the next slot remained uniform. Fixing the full permutation was used only to multiply the cylinder bounds. No drift identity was asserted or used under that conditioning.

5.6 Application to the deletion lines

We now apply the graph result to the geometric construction. Proposition 4.1 supplies the domain and degree bounds, the codegree bound, and the exceptional sets required by Proposition 5.1. Its retained candidates are injective in their lines within each slot, and an independent transversal is a compatible collection of split tuples. For the occupancy statement, take

The same graph proposition gives |T_\ell|\ge c_0q. Recall from (3) that R_0 avoids the deletion lines, whereas R avoids only the selected split lines. If \ell is neither a selected split line nor one of the M_g^1, its final tracked set is exactly \ell\cap R_0. For \ell=M_g^1, the final set is \ell\cap R, because a constituent cannot be a candidate split line. Hence (25) gives the line occupancy required by the deterministic construction.

To describe the resulting deletion-line law, include the constituent sampling in the experiment. Sample the two offsets in each direction independently and with replacement, as in Section 4. Abort if the data fail the candidate graph conditions or if any constituent pair coincides; otherwise run the selection procedure. Write \mathcal A for the event that this entire experiment returns a collection. By Proposition 4.1 and (23), there is a fixed a_0>0 such that

for all sufficiently large q. For every fixed offset outcome M,

These prescriptions may be chosen as functions of M, but are fixed once M is fixed. If the initial check fails for that offset outcome, the left side is zero. This estimate lets us compare the law of the returned deletion set with a uniform law without changing the initial offset distribution.

6 Excluding small covers at affine pencils

The deterministic reduction leaves a specific obstruction at an affine point p. If b selected split lines pass through p, a hypothetical cover has already spent q+1-b of its labels on the other directions. Only b-1 labels remain to cover the 4b designated points, beyond those covered by partner lines of constituents through p. For b\ge3, the local condition in Section 2 excludes precisely this possibility. We prove that the selection procedure returns a collection violating this condition with probability o(1).

The input from selection is an upper bound for prescribed choices, conditional on fixed offsets. We first apply that bound and then average geometric events under the original independent offset law. In particular, successful return remains part of the event being estimated; we do not condition the offset law on successful return.

Throughout this section the offsets M_d^0,M_d^1 have the independent, with-replacement law used in the construction. Let \mathcal A be the event that the selection procedure returns a compatible collection. The conditional estimate (49), obtained from Proposition 5.1, says that for any fixed offset configuration M and any s prescribed tuple choices in distinct slots,

where K is the fixed constant in that estimate. The prescriptions may depend on M, provided they are fixed once M is fixed. An unavailable tuple has probability zero, so they may range over all generator and bit labels. On \mathcal A, M_d^0\ne M_d^1 for every direction d, no selected split line is a constituent, and constituent multiplicity at every point is at most B=\lceil\log q\rceil.

The estimate at a fixed point must save three powers of q, since we will sum over q^2 affine points. We obtain those savings from two sources: repeated generator directions and additional incidences forced by a cover. Three generator reuses already cost O(q^{-3}). With zero, one, or two reuses, we will extract respectively three, two, or one further incidence costs. The resulting bound at a fixed point is O(B^3/q^3), apart from the separately controlled event of a large pencil.

6.1 Generator reuse in a selected pencil

Fix p\in A. Write b for the number of selected split lines through p. Compatibility implies that their target directions are distinct and, when b\ge2, that their 4b designated points are distinct and different from p. Let \Gamma be the union of their generator directions and let t_d be the number of tuples using d\in\Gamma. Define the reuse count

Thus \kappa counts generator occurrences after their first use. Compatibility says that two tuples share at most one generator.

We first remove large pencils, so the later enumeration only has to handle 3\le b\le B. The number of selected lines through any point is at most B except on an event of probability o(1), jointly with \mathcal A. Indeed, for a specified slot there is at most one retained candidate on the line of its direction through p. Conditional on M, the cylinder estimate and a union bound give

The last expression, multiplied by q^2, tends to zero.

6.2 The aligned law for at most two reuses

Lemma 6.2 handles all pencils with at least three reuses, regardless of their size. After also removing the large-pencil event, it remains to consider 3\le b\le B and \kappa\in\{0,1,2\}. We first describe the offset law for a prescribed list whose tuple points lie on lines through p. This law will supply the independent variables and prescribed projections used in the remaining incidence estimates.

We enumerate ordered lists of b prescribed tuples through p. A pattern of equality among their 4b generator entries with \kappa reuses has 4b-\kappa generator classes. There are only b^{O(1)} such patterns: choose the at most two entries that repeat a previous class and their earlier representatives. We retain only patterns compatible with at most one common generator per tuple pair.

For a fixed pattern there are at most

assignments of target and generator directions: there are b target entries and 4b-\kappa generator classes. Call an assignment eligible if its targets are distinct, its distinct generator classes have distinct directions, and no tuple has its own target as a generator. Bits and slot choices contribute a factor 16^b2^b=32^b.

For these patterns we may process the tuples as roots and children, each child sharing exactly one generator with an earlier root and having its other three generators new. With one reuse there is one linked pair. With two reuses there are two disjoint linked pairs, a chain of three tuples, or one generator direction shared by three tuples. For a chain take the middle tuple as root; for a direction shared by three tuples take any of the three as root. Other tuples are roots. This processing order depends only on the equality pattern, not on the direction assignment or offsets.

Write g_i for the target direction of tuple i and put L_i=p+g_i. We call the list aligned if all four positions of each tuple i lie on L_i. This event imposes neither distinctness of the positions nor any other validity condition. For every eligible direction assignment,

Conditional only on alignment, the offsets and positions can be generated as follows; we refer to this distribution as the aligned law.

1. (i)

   At a root, choose four independent uniform points of L_i and set the generator offsets to the prescribed lines through their endpoints.

2. (ii)

   At a child, the two positions involving its shared generator are the intersections of that generator’s already fixed constituents with L_i. Choose the other two positions independently and uniformly on L_i, and set the new generator offsets accordingly.

3. (iii)

   All offsets in directions outside \Gamma retain their original independent law.

For a root, before alignment its four positions are independent uniform plane points, giving the factor q^{-4}. At a child, the two positions on the shared generator’s constituents each involve one fresh offset. Each lands at its required intersection with probability 1/q. The other two positions are independent uniform plane points, each costing 1/q to lie on L_i. These use disjoint fresh offset variables. The factor q^{-4} is independent of the earlier values, so later alignment does not bias an earlier generation. This proves both (55) and the stated law. A target of one tuple may equal a generator of another; that does not affect this argument.

The aligned law deliberately leaves the remaining geometric restrictions as events to be tested. Call a list admissible if it is aligned, all its positions are distinct and external to p, none of its L_i is a constituent, and the constituent multiplicity is at most B at every point. Every list selected on \mathcal A through p, with b\ge3, satisfies these necessary conditions.

To express a violation of the local condition for a prescribed list, let F be the union of its designated points and define Z(p) by (5), with F in place of F(p); throughout these counts Z(p) refers to this prescribed list. A bad cover of this list covers F by Z(p) and at most b-1 additional sets: sets of at most two points, affine lines outside \{L_1,\ldots,L_b\}\cup\mathcal M, or merged pairs, with no merged pair used more than once. An admissible bad cover means that both this cover and the preceding admissibility conditions occur. In the following estimates we bound a bad cover jointly with admissibility, rather than conditioning the point variables on it.

For a used direction d\in\Gamma, its 2t_d prescribed endpoint indices will be called its purposeful endpoints. Neither constituent of d passes through p on an admissible list. Indeed, it contains a purposeful point external to p on a target line through p, and its direction differs from that target. Consequently the set Z(p) of points already covered by partner lines uses only directions outside \Gamma; we call this precoverage.

6.3 Additional incidence costs for zero or one reuse

For zero or one reuse, we can estimate each eligible direction assignment separately. Even after allowing the purposeful endpoints covered by used merged pairs, a cover by b-1 additional sets must create further incidences. We will extract 3-\kappa of these incidence conditions whose variable dependencies permit successive integration.

6.4 One additional incidence when there are two reuses

Two reuses already contribute two powers of q^{-1} in the final prescription count. It remains to gain one further power from the bad cover. Here we average over direction assignments as well as aligned positions. Each incidence estimate will reveal a direction after the geometric data prescribing its required value are known.

6.5 Summing over all selected pencils

We now combine the selection estimate with the geometric estimates to prove Proposition 6.1. The former costs one factor K/q per selected tuple; the latter supplies the alignment probability and the additional incidence costs. For fixed p,b,\kappa with 3\le b\le B and \kappa\le2, count ordered prescriptions that occur as selections on \mathcal A and have an admissible bad cover using the precoverage defined by that list. An actual violation with exactly these parameters yields all b! orders of its selected tuples. The count need not require that there are no further selected lines through p: dropping that restriction only increases it.

For each prescription, condition on M first to obtain the factor (K/q)^b from (51). All necessary geometric tests then depend only on the independent offset model and that prescription. The patterns, slots, bits, direction assignments, and alignment contribute, after division by b!, at most

Here C and the polynomial exponent are independent of b and q; we use b\le\lceil\log q\rceil. For \kappa=0,1, multiply by the additional factor from Lemma 6.3. For \kappa=2, Lemma 6.4 provides the factor O(b^3/q) after summing direction assignments. Hence the total probability at p for these values of b,\kappa is

because \sum_{b\ge3} b^a C^b/b!<\infty for every fixed a,C. Lemma 6.2 adds O(q^{-3}) for all cases with \kappa\ge3. Summing over the q^2 affine points gives O(B^3/q)=o(1). The earlier large-b estimate is also o(1). This proves Proposition 6.1: a violation of the local condition occurs with probability o(1), jointly with successful return of the selection procedure.

7 Completion of the construction

We now put the three probability estimates on the same experiment. The candidate graph and selection procedure give compatible tuples and line occupancy; deletion domination gives the core-cover condition; the local incidence estimate gives the last condition of Proposition 2.1.

A Elementary incidence and concentration estimates

The statements in this appendix do not depend on the construction. The incidence identity holds over every finite field and for every set of points, including a set obtained from earlier random choices. The two probability estimates apply to a specified filtration or to independent trials; their applications must still supply the relevant stopping rules and union bounds.

The next estimate is the bounded-increment exponential-moment argument of Azuma [4], stated for a process with a predictable drift. We retain a constant that accommodates centering each increment.