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 (Milićević 2017, Conjecture 1). Erdős, Gyárfás, and Pyber record the equivalence of this covering formulation with the intersecting case of Ryser’s conjecture (Erdős et al. 1991, sec. 3, after Theorem 2). The standard transfer gives the following consequence of Theorem 1.

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 \[(q-4)+1+4=q+1.\] 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.

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 (Loh and Sudakov 2007, sec. 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 (Erdős and Lovász 1975, sec. 4); Kahn subsequently developed the random-line approach further (Kahn 1992). 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 (Szőnyi and Weiner 2012), also stated by Héger and Nagy (Héger and Nagy 2017), 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 8 supplies three elementary estimates in a form independent of the construction; these are also the precise inputs used by the companion article.

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 \[\mathcal M=\{M_g^s:g\in\mathcal G,\ s\in\{0,1\}\}.\] 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 \[ u_i=M_{d_i}^{\sigma_i}\cap M_{d_{i+1}}^{1-\sigma_{i+1}}. \tag{2}\] The intersections exist uniquely because consecutive generator directions are different. Call the tuple valid if the following conditions hold:

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

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

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. Neither chosen split line contains a designated point of the other tuple.

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

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 \[ \begin{split} D&=\mathcal S\cup\{M_g^1:g\in\mathcal G\},\\ R_0&=A\setminus\bigcup_{\ell\in D}\ell, \qquad R=A\setminus\bigcup_{S\in\mathcal S}S,\\ X&=R\cup\bigcup_{S\in\mathcal S}F_S. \end{split} \tag{3}\] There are exactly three lines of \(D\) in each direction. Compatibility gives \[ S\cap X=F_S\qquad(S\in\mathcal S). \tag{4}\] 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.

Partitions and intersecting edges

We prove Proposition 3 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.

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 \[ t\leq\rho q/4. \tag{7}\] We treat separately a parallel pencil and a pencil through an affine point.

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 \[ |Z(p)|\leq b. \tag{8}\] 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 3.

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 \[P^{(q)}_{ij}=q^{-2}|\{x\in A:i_D(x)=i,\ j_C(x)=j\}|, \qquad X^\ell_{ij}=q^{-1}|\{x\in\ell:i_D(x)=i,\ j_C(x)=j\}|.\] 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 \[1+\frac{k(q+1)+m-1}{q},\] 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 \[ \frac mq\longrightarrow c,\quad P^{(q)}\longrightarrow P,\quad \nu_D^{(q)}:=\frac1q\sum_{\ell\in D}\delta_{X^\ell} \Longrightarrow\nu_D,\quad \nu_C^{(q)}:=\frac1q\sum_{\ell\in C}\delta_{X^\ell} \Longrightarrow\nu_C. \tag{9}\] 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 \[ \int x_{ij}\,d\nu_D(x)=iP_{ij},\qquad \int x_{ij}\,d\nu_C(x)=jP_{ij}. \tag{10}\] Summing these identities by Tonelli’s theorem yields \[ \sum_{i,j}iP_{ij}=k,\qquad \sum_{i,j}jP_{ij}=c. \tag{11}\] 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.

The three deletion estimates

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 (Erdős and Lovász 1975, sec. 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 (Szőnyi and Weiner 2012, Theorem 4), also reproduced by Héger and Nagy (Héger and Nagy 2017, Result 3.6). If \(q\) is prime and \(B\subseteq\mathrm{PG}(2,q)\) has \[|B|\le\frac32(q+1)-\beta, \qquad \Delta<\frac29(\beta+1)^2,\] 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.

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 \[\theta=1/100.\] 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 \[\begin{array}{c|ccccc} j&0&1&2&3&4\\ \hline f_{\max}&0&0&1&2&4. \end{array}\] 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\).

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 \[\mathbb EH_g=(16+o(1))q.\] 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 10(ii), for both \(H_g\) and \(Y_g\); in particular, \(\mathbb EY_g=O(q)\). Its tail estimate and a union bound give, with probability \(1-o(1)\) simultaneously for every \(g\), \[ H_g\ge8q,\qquad Y_g\le C_1q \tag{20}\] 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 10(i) then supplies the required tail bound.

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. For a fixed target \(g\) and any line \(\ell\), at most \(q^\theta\) successful tuples designate a point on \(\ell\).

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

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

4. 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 10(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 10(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 10(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.

Degrees, codegrees, and initial occupancy

We now translate the incidence estimates into the graph assertions of Proposition 9. For the first compatibility condition, the two ways a conflict can occur are represented by \[B_v=\{w:L_w\cap F_v\ne\varnothing\},\qquad E_v=\{w:F_w\cap L_v\ne\varnothing\}.\] 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 \[\mathbb EU_\ell=q(1-1/q)^q.\] Changing one hit changes \(U_\ell\) by at most one. Apply Lemma 20 to these \(q\) independent trials with \(L=1\), and then Lemma 19 to their exposure martingale. Since \((1-1/q)^q\to e^{-1}>1/5\), there is a fixed \(\delta>0\) such that \(\mathbb EU_\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 \[(1-1/q)^{q+1}=e^{-1}+o(1).\] Intersecting this event with the event of probability \(1-o(1)\) just proved gives the final assertion of Proposition 9.

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: \[\begin{align*} P_*&=4C_*/c_*+4,& \alpha&=P_*/q,& s_{\min}&=\exp(-6P_*),\tag{26}\\ B_*&=2/(s_{\min}c_*),& \rho&=c_0\exp(-6B_*)/4,\tag{27}\\ 0<a&<\min\{1,\rho/2,c_*/(100(C_*+1))\},& h_0&=\lceil aq\rceil,& t_{\max}&=n-h_0. \tag{28}\end{align*}\] 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 \[ L_i(t)=|Q_i(t)|,\qquad s(t)=(1-\alpha)^t,\qquad b(t)=s(t)h(t)/n. \tag{29}\] 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}\), \[ s_{\min}\le s(t)\le1,\qquad s_{\min}a/3\le b(t)\le1. \tag{30}\] 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 \[ L_i(t)<s(t)c_*q/2. \tag{31}\] For every alive vertex \(v\) in a remaining slot define \[ D_v(t)=\sum_{i\in I(t)}|N(v)\cap Q_i(t)|,\qquad r_v(t)=\frac1{h(t)}\sum_{i\in I(t)} \frac{|N(v)\cap Q_i(t)|}{L_i(t)}. \tag{32}\] 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 \[ \lambda_u=\frac{\alpha-r_u(t)}{1-r_u(t)}. \tag{33}\] 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: \[ (1-r_u(t))(1-\lambda_u)=1-\alpha. \tag{34}\]

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\), \[ \mathbb P(Z\ge k)\le \mathbb E\binom Zk\le\mu_*^k/k! \le(e\mu_*/k)^k. \tag{35}\] 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)\).

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 19, the appendix form of the Azuma–Hoeffding estimate (Azuma 1967). For an adapted process \(X_t\) with \(|X_{t+1}-X_t|\le L\) for \(0\le t<T\), put \(d_t=\mathbb E[X_{t+1}-X_t\mid\mathcal F_t]\). Its fixed-time conclusion is \[ \mathbb P\left(\left|X_t-X_0-\sum_{j<t}d_j\right|\ge u\right) \le 2\exp\left(-\frac{u^2}{8TL^2}\right) \qquad(t\le T). \tag{36}\] 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.

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 11. 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 \[ \mathbb P(T(t+1)=T(t)-1\mid\mathcal F_t) \le \frac{B_*T(t)}q, \qquad \mathbb E[T(t+1)\mid\mathcal F_t]\ge(1-B_*/q)T(t). \tag{43}\] 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 \[ c_0 e^{-6B_*}q/2=2\rho q \tag{44}\] 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.

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 (Erdős and Lovász 1975, sec. 2).

For every history passing (42), choose the tail according to the conditioned law in Lemma 12. 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).

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 \[\frac{2}{s_{\min}c_*q}.\] 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 12 bounds the tail prescription by \[\left(\frac{2e^{1/2}}{s_{\min}c_*q}\right)^{s_{\rm t}}.\] Taking conditional expectations backwards from the tail and then through the prescribed main steps gives \[\mathbb P(\mathcal A,\hbox{ all prescriptions}\mid\pi) \le\left(\frac{2}{s_{\min}c_*q}\right)^{s_{\rm m}} \left(\frac{2e^{1/2}}{s_{\min}c_*q}\right)^{s_{\rm t}}.\] Average over \(\pi\) and take \[ K_* =\max\{1,2e^{1/2}/(s_{\min}c_*)\}. \tag{47}\] This proves (24) and completes Proposition 11. 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.

Application to the deletion lines

We now apply the graph result to the geometric construction. Proposition 9 supplies the domain and degree bounds, the codegree bound, and the exceptional sets required by Proposition 11. 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 \[T_\ell= \begin{cases} \ell,&\ell\in\{M_g^1:g\in\mathcal G\},\\ \ell\setminus\bigcup_g M_g^1,&\text{otherwise}. \end{cases}\] 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 9 and (23), there is a fixed \(a_0>0\) such that \[ \mathbb P(\mathcal A)\ge a_0 \tag{48}\] for all sufficiently large \(q\). For every fixed offset outcome \(M\), \[ \mathbb P(\mathcal A,\hbox{ prescribed choices in }s\hbox{ slots}\mid M) \le(K_*/q)^s. \tag{49}\] 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.

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 \[\kappa=4b-|\Gamma|=\sum_{d\in\Gamma}(t_d-1).\] 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 \[\mathbb P(\mathcal A,\ b(p)\ge B\mid M) \le \binom{2(q+1)}B(K/q)^B \le \left(\frac{C}{B}\right)^B.\] The last expression, multiplied by \(q^2\), tends to zero.

The aligned law for at most two reuses

Lemma 15 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 \[ (q+1)^{5b-\kappa} \tag{54}\] 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, \[ \mathbb P_M(\text{alignment})=q^{-4b}. \tag{55}\] Conditional only on alignment, the offsets and positions can be generated as follows; we refer to this distribution as the aligned law.

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

2. 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. 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.

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.

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.

Summing over all selected pencils

We now combine the selection estimate with the geometric estimates to prove Proposition 14. 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 \[ \frac{b^{O(1)}}{b!}\,32^b(q+1)^{5b-\kappa} (K/q)^b q^{-4b} \le \frac{b^{O(1)}C^b}{b!}q^{-\kappa}. \tag{58}\] 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 16. For \(\kappa=2\), Lemma 17 provides the factor \(O(b^3/q)\) after summing direction assignments. Hence the total probability at \(p\) for these values of \(b,\kappa\) is \[O(B^3/q^3),\] because \(\sum_{b\ge3} b^a C^b/b!<\infty\) for every fixed \(a,C\). Lemma 15 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 14: a violation of the local condition occurs with probability \(o(1)\), jointly with successful return of the selection procedure.