A counterexample to Ryser’s covering conjecture

Proof. Take the hypergraph H from Theorem 1.1, with parts V_1,\ldots,V_r. For e\in E(H), let x_i(e) be the unique vertex in e\cap V_i. Form the complete graph K with vertex set E(H). For each pair of distinct hyperedges e,f, choose one index i with x_i(e)=x_i(f) and color the edge ef by i. Such an index exists because H is intersecting. Only one color is chosen even when the two hyperedges meet in several parts.

Along a color-i path, the value of x_i is constant. Thus every connected color-i subgraph determines a vertex of V_i belonging to every hyperedge indexed by that subgraph. For a singleton, choose any color and the corresponding vertex of its hyperedge. If t connected monochromatic subgraphs cover the vertices of K, the at most t hypergraph vertices so chosen meet every edge of H. Hence t\ge\tau(H)=r.

Conversely, fix a vertex of K. The r monochromatic stars centered there, one for each color and allowing singleton stars, cover all vertices of K. They give a tree cover of size at most r. The lower bound applies to trees and to maximal monochromatic components as well, and the stars can be enlarged to maximal components. This proves all three stated minima.□

Proof. For the triangle inequality, choose one representation d=x_d-y_d for each d\in X-Y. The map

from (X-Y)\times Z into (X-Z)\times(Z-Y) is injective: summing the two coordinates recovers d, after which the chosen representation recovers z. This proves (5).

For the covering statement, take a maximal set T\subseteq X for which the translates t-Y, t\in T, are pairwise disjoint. Their union is contained in X-Y, so |T|\le M. Maximality implies that for every x\in X some x-Y intersects t-Y with t\in T, whence x\in t+(Y-Y).

For the multiple-sum bound, the minimizing-subset argument of Petridis [28] lets us iterate a one-step growth estimate. Put Q_0=-Y and choose a nonempty W\subseteq Y minimizing

Then \mu\le M, and every W'\subseteq W, including the empty set, satisfies |W'+Q_0|\ge\mu|W'|. We claim that for every finite set E_0,

The assertion is immediate if E_0 is empty. Otherwise order its elements as e_1,\ldots,e_k. When the translate W+e_i is added to the preceding translates, let

It contributes exactly |W|-|W_i'| new elements. Moreover, W_i'+Q_0+e_i is contained in the union of the preceding enlarged translates W+Q_0+e_j. Thus the contribution of W+Q_0+e_i is at most

Summing proves (7). Iterating this estimate gives |W+jQ_0|\le\mu^j|W| for every nonnegative integer j. We now remove the auxiliary set W by applying (5) to uQ_0,vQ_0 with intermediate set -W:

Negation preserves cardinality, so |uQ_0-vQ_0|=|uY-vY|. Since |W|\le|Y| and \mu\le M, this is (6).□

Proof. We first find a large set of vertices such that every ordered pair is joined by many walks of length four. Counting the possible edge labels of these walks will then bound both differences and quotients of the endpoints.

Regard G as a bipartite graph, and put \tau=(512V^8)^{-1}. Call an ordered pair (a,a_2)\in A^2 bad if it has fewer than \tau n common neighbors in B. To find a neighborhood with few bad pairs, first note that vertices of B with fewer than n/(2V^2) neighbors account for at most |B|n/(2V^2)\le n^2/(2V) edges. Since every vertex of B has at most Vn neighbors, the set of vertices with at least n/(2V^2) neighbors has size at least n/(2V^2).

Summed over all b\in B, the number of bad ordered pairs in the neighborhood of b is at most

Averaging over the large neighborhoods just identified, one obtains a neighborhood A_0 of size at least n/(2V^2) in which the number of bad ordered pairs is at most

Let S consist of those a\in A_0 having at most |A_0|/4 bad partners in A_0. At most |A_0|/4 elements are discarded, so |S|\ge3|A_0|/4, proving (9).

The choice of S ensures that, for every a,a'\in S, at least |A_0|/2 elements a_2\in A_0 form nonbad pairs with both endpoints. Each such a_2 gives at least (\tau n)^2 ordered walks

whose four edges belong to G. Repeated vertices are allowed. Consequently each ordered endpoint pair in S^2 has at least

such walks. This lower bound now converts the limited number of edge labels into a bound on endpoint differences.

For one of these walks, write its edge differences, always taking the A coordinate minus the B coordinate, as

They satisfy a-a'=d_1-d_2+d_3-d_4. For a fixed endpoint pair, the four differences determine the walk uniquely: starting from a, one recovers successively b_1,a_2,b_2,a'. Choose one ordered endpoint pair for each element of S-S. The resulting collections of difference quadruples are disjoint for different differences, because their alternating sums differ. Counting in D^4 and using (11) gives

The same walks give the quotient bound on the same set S. Put

All are nonzero, and a/a'=j_1j_3/(j_2j_4). From a fixed initial a and these four quotients one recovers b_1=a/j_1, a_2=j_2b_1, b_2=a_2/j_3, and a'=j_4b_2. Choosing one endpoint pair for each element of S/S and counting in J^4 therefore proves the other bound in (10).□

Proof. Put H=B-B, so H=-H and 0\in H. In the remainder of this proof, integer multiples of B or H inside sumsets denote iterated sums. We prove the covering assertion by induction on expression length. To combine coverings at an induction step, we will need a fixed covering of 2H by translates of H. By Lemma 2.2,

The covering statement of that lemma consequently supplies a set T_*\subseteq F with |T_*|\le K^5 such that

Every e\in E has a covering eB\subseteq T_e+H with |T_e|\le2K^3\le K^4, by (12) and the covering lemma. The scalars 0 and 1 also have coverings by one translate of H: use \{0\}\subseteq H and B\subseteq b_0+H for any b_0\in B. This proves the case m=0.

We now check how the number of translates changes under each allowed operation. Suppose that

Negation replaces T by -T. For addition and subtraction,

so the number of translates is at most K^{a+b+5}. For a product,

This uses at most K^{b+2a+5} translates and is valid even if \lambda=0. Finally, if \lambda\ne0, then

Scaling by \lambda^{-1} and then negating gives |\lambda^{-1}B-B|\le K^{a+3}|B|. The covering lemma now covers \lambda^{-1}B by at most K^{a+3} translates of H.

These bounds give the claimed uniform induction: in an expression with at most m+1 operations, each immediate subexpression has at most m operations, so every resulting covering uses at most K^{3C_m+5} translates. This proves the covering assertion with (13).

To deduce the sumset bound from the covering, let \lambda B\subseteq T+H be the covering just obtained. Then

again by Lemma 2.2. Since E\subseteq B, this also bounds |E+\lambda E|.□

Proof. Suppose that such a sequence exists. We first use multiplicative overlaps to obtain sets satisfying the scalar-covering hypotheses. Ratios of differences in a large subset will then form a subfield. The proper-subfield hypothesis will force that subfield to be the whole field, where averaging will contradict the scalar-covering bound.

Extracting scalar-covering hypotheses. Put s=|S|. The s sets S/a, a\in S, each have size s, and their union is contained in S/S. Cauchy–Schwarz gives

Thus some b\in S satisfies \sum_{a\in S}|S/a\cap S/b|\ge s^2/K. Since every summand is at most s, at least s/(2K) values a\in S have |S/a\cap S/b|\ge s/(2K): otherwise the sum of the large summands would be less than s^2/(2K) and that of all the other summands at most s^2/(2K).

Let E be the set of e=a/b for these values of a, and put B=S/b. Then

The last inequality follows by multiplying S/a\cap S/b by a. For Z=S\cap eS, the triangle inequality and the containments Z\subseteq S,eS imply

After scaling by 1/b, we have

Thus Lemma 2.4 applies to B and E. We have obtained uniform control for every scalar expressible using a bounded number of operations on elements of E.

Ratios of differences form a subfield. Write t=|E|. By (18) and (16), t=q^{1/2+o(1)}. In particular, t\ge2 for all sufficiently large fields in the sequence. Define

To prove closure under addition and multiplication, we apply the scalar-covering bound to the result of either operation. Every member of R_0 has an expression in E with at most four operations. Consequently, for r,r'\in R_0, each of r+r' and rr' has an expression with at most nine operations. For either candidate \lambda, Lemma 2.4 gives

for all sufficiently large q, uniformly over r,r'. Indeed, the ratio of this upper bound to t^2 is at most 4K^{C_9+5}/s, which tends to zero. Therefore the map (x,y)\mapsto x+\lambda y from E^2 is not injective. A collision between distinct pairs satisfies y\ne y', since otherwise also x=x', and gives

It follows that R_0 is closed under addition and multiplication. It contains 0 and 1 and, directly from its definition, is closed under negation and reciprocals of nonzero elements. Thus R_0 is a subfield of \F_q.

The size of E now prevents this subfield from being proper. Choose distinct e_0,e_1\in E. The map

injects E into R_0, so |R_0|\ge t>q^{1/3} for large q. The proper-subfield hypothesis forces R_0=\F_q.

A scalar with a large sumset. Every field element consequently has a four-operation representation using elements of E. The scalar-covering estimate therefore bounds |E+\lambda E| for every scalar. To reach a contradiction, we average over the field and find a scalar for which this sumset is too large.

For \lambda\in\F_q, let N_\lambda be the number of ordered quadruples (x,y,x',y')\in E^4 satisfying x+\lambda y=x'+\lambda y'. There are t^2 identical pairs, which give a collision for every \lambda. If y\ne y', exactly one value of \lambda gives a collision; if y=y' but x\ne x', none does. Hence

For some \lambda, Cauchy–Schwarz applied to the fibers of (x,y)\mapsto x+\lambda y therefore yields

But R_0=\F_q, so this particular \lambda itself has a four-operation representation in (19). Lemma 2.4 bounds its sumset by K^{C_4+3}s=q^{1/2+o(1)}, contradicting (21). The expression length here remains bounded; no iteration of field generation is being used.□

Proof of Theorem 2.1. We argue by contradiction, allowing all quantitative losses to be subpower factors along a sequence of fields. Suppose the theorem is false. For a sequence of positive exponents \kappa_j\to0 in (0,1/10), choose admissible counterexamples with q_j\to\infty. Such choices are possible because the failure of the theorem says that for each fixed exponent there are arbitrarily large counterexamples. Along this sequence, put U=\max(2,q_j^{\kappa_j}) and suppress the index j. We have

All bounds below use absolute constants. Every assertion made for sufficiently large q is along this sequence. Our goal is to construct from these counterexamples sets of the size and small-expansion form excluded by Lemma 2.5.

Pruning the incidence graph. We first retain many incidences while putting both an upper and a lower bound on every remaining degree. Consider the bipartite graph on P and \mathcal L whose edges are incidences. If d(v) denotes a degree on either side, then counting ordered pairs on the opposite side and using the unique join of two distinct projective points, or the unique intersection of two distinct projective lines, gives

Here \sum_vd(v)(d(v)-1)\le U^2q^2, and \sum_vd(v)=I(P,\mathcal L)\le U^2q^2.

Set

Delete every vertex whose initial degree exceeds H. By (23), the total number of incidences lost, counting both sides, is at most

Next, iteratively delete vertices whose current degree is less than d. Each of the at most 2Uq original vertices is deleted at most once, so this stage loses at most 2Uq\,d=q^{3/2}/(4U) incidences. Denote the surviving sets again by P,\mathcal L. They satisfy

The size lower bounds follow by dividing the surviving incidence count by the maximum degree H.

The pruning also controls the intersection of P with every projective line, including lines not in \mathcal L. We will need this stronger form of control when discarding points on a few lines chosen later. Fix a projective line \ell. Each point of P\cap\ell is incident with at least d-1 lines of \mathcal L different from \ell. These lines are distinct for different points of P\cap\ell. Since d\to\infty, for large q we obtain

Four anchors with many common witnesses. We seek four points, three collinear and the fourth off their line, together with many points joined to each of them by lines of \mathcal L. We obtain the four points by first counting such configurations around each possible common point and then averaging.

For x\in P, let N(x) consist of the points in P\setminus\{x\} joined to x by a line of \mathcal L. Distinct lines through x have disjoint point sets away from x, so

for large q. Put t_\ell=|N(x)\cap\ell|. Summing degrees of the points of N(x) gives

Lines with t_\ell\le2 contribute at most 2Uq. Because U=q^{o(1)}, for sufficiently large q this is at most half of the displayed lower bound. Consequently

For every integer t\ge3, one has t(t-1)(t-2)\ge(2/9)t^3. Hölder’s inequality therefore shows that the number of ordered triples of distinct points of N(x) lying on a line of \mathcal L is at least

By (26) and (27), each such triple admits at least

choices of a fourth point in N(x) outside its line, once q is large enough. Summing over x and using (25), we obtain at least

ordered choices (x,p_1,p_2,p_3,p_4) with p_1,p_2,p_3 distinct and collinear on a line of \mathcal L, with p_4 outside that line, and with all four p_i in N(x).

We now reverse the count to fix the four anchor points while retaining many choices of the common point x. The number of possible ordered quadruples (p_1,p_2,p_3,p_4) in this count is at most

Some quadruple thus has at least

Discard the witnesses on the common line of p_1,p_2,p_3 and on the joins of p_1,p_4 and of p_2,p_4. The cap (26) discards at most 3H witnesses. Since U=q^{o(1)}, this is eventually less than c_0q/(2U^{39}). At least that many witnesses remain. Their joins to the four anchors will supply the graph and the four small sets required by Lemma 2.3.

The four pencils as coordinates. Choose projective coordinates in which

This is possible over \F_q: representatives of p_1,p_2 span their line, the representative of the distinct third point has both coefficients nonzero and permits rescaling of the first two, and a representative of p_4 completes a basis. The discarded lines are precisely the coordinate line at infinity and the two coordinate axes through p_4. Hence every remaining witness has coordinates (a:b:1) with a,b\ne0.

Let G be the set of these pairs (a,b), and let A,B be its coordinate projections. Define D and J from G as in Lemma 2.3. The chosen coordinates make the roles of the four pencils explicit: for a witness (a:b:1), the joins to p_2,p_1,p_3,p_4, respectively, have equations

Each join is a member of \mathcal L, by the witness property. Each anchor belongs to P and has degree at most H. Distinct values of the corresponding parameter give distinct lines in its pencil. Thus

With

we have V\ge2, V=q^{o(1)}, and all the hypotheses (8) hold.

The incidence configuration now meets the extraction hypotheses. Lemma 2.3 gives S\subseteq\F_q^* satisfying

In particular |S|=q^{1/2+o(1)}, and, on setting K=2^{23}V^{24}, we have K\ge2, K=q^{o(1)}, and |S-S|,|S/S|\le K|S|. This contradicts Lemma 2.5.

We have excluded every sequence of counterexamples of the form (22). The negation of the theorem would have produced such a sequence, so some absolute \kappa\in(0,1/10) and Q satisfy the stated conclusion.□

Proof. For |z|\leq1 we have e^z\leq1+z+z^2. Consequently, if |\theta|\leq M^{-1}, the conditional mean-zero property gives

Iteration and Markov’s inequality bound the upper tail by \exp(\theta^2V-\theta u) for 0<\theta\leq M^{-1}. Take \theta=\min\{u/(2V),1/M\}. If u\leq2V/M, the exponent is -u^2/(4V); otherwise it is at most -u/(2M). Applying the same argument to -Z_i proves (33).□

Proof. We first establish a simultaneous lower bound on surviving cross-intersections for every admissible pair of short line lists, ignoring any deletion shape equal to one of those lines. After fixing such a realization, we show that any cover lacking an almost full pencil contains an admissible pair with too few surviving cross-intersections. This second step samples only within the fixed cover, with separate arguments according to its maximum concurrency.

Fix the absolute constant \kappa\in(0,1/10) of Theorem 2.1, and put \epsilon=\kappa/10. All constants below may depend on the fixed parameters, but not on q, the particular deletion distributions, or a subsequently chosen cover.

Uniform point and line counts. Expose the independent trials one at a time. Changing one trial changes |X| by at most 2D^2q, because the old and new lists contain at most 2D shapes in total and each has at most Dq points. The exposure observation in [27, Lemma A.3] therefore bounds the absolute martingale increment by L=2D^2q. There are T\le Dq trials, and \E|X|=\delta_q q^2. The fixed-time concentration estimate in [27, Lemma A.2], with u=q^{3/2+\epsilon}, gives

If there are no trials, the count is deterministic and this bound holds as well. Equivalently, we may add a dummy trial of zero change.

For the line count |X^\ell\cap\ell|, the rule ignoring exact copies of \ell is applied separately to each trial. Changing one trial then changes the count by at most 2D^2: each of its at most 2D old or new shapes meets \ell in at most D points. With L=2D^2 and u=q^{1/2+\epsilon}, the same two elementary estimates and T\le Dq give

Moreover, a point restored by ignoring \ell can be restored only if some trial lists \ell exactly. The probability of this event is at most D/q, by the third deletion hypothesis. Therefore

There are q(q+1) affine lines. The superpolynomial tails and a union bound consequently show that, with probability tending to one,

The lower line estimate proves the first conclusion of the lemma. For the pencil conclusion we will also need to bound overlaps in an alleged cover. The same estimates give the uniform upper bound

because X\subseteq X^\ell.

A simultaneous event for small line samples. The counts just proved control a single line but do not yet restrict how a cover’s lines meet. We now obtain a stronger test on short lists of lines: provided their intersections are distinct and not concentrated on a deletion shape, many of those intersections survive. The list length will be logarithmic in q, so that the variance-sensitive tail can pay for a union bound over all lists.

Set

where the fixed constant A will be chosen below. Consider any ordered tuple of 2t distinct affine lines, separated into two lists of length t. Call the tuple admissible if its cross-list intersections form a set P_0 of t^2 distinct finite points, and

For this tuple, ignore deletions by every shape equal to a tuple line, and let Y_0 count the survivors in P_0 after the remaining deletions. We claim that, with probability tending to one,

To prove the claim, fix a tuple in advance. Omitting shapes is a deterministic operation on each trial, so the trials remain independent. Omission can only restore points, and hence \E Y_0\geq\delta t^2. By (36), each trial’s contribution to the deletion set within P_0 has size at most C_0=DH_0. The probability that this contribution is nonempty is at most Dt^2/q, by a union bound over P_0 and the per-point deletion hypothesis.

For completeness, the rarity of a nonempty contribution also controls the conditional variance of the exposure martingale. Fix the past, and let g_i(w) be the conditional expected final value of Y_0 when the current trial has outcome w. Let g_i(\varnothing) denote the hypothetical value obtained by making this trial delete nothing on P_0. Independence leaves the law of the future trials unchanged, so

with equality to zero whenever the trial’s contribution is empty. The current trial also retains its original law conditional on the past. Thus the martingale increment has absolute value at most 2C_0, and its conditional variance is at most

The sum of conditional variances is at most D^2C_0^2t^2, since there are at most Dq trials. Applying Lemma 3.1 at deviation \delta t^2/2 yields

In particular, c_0 is independent of A.

There are at most (q(q+1))^{2t} ordered tuples. The logarithm of the union bound in (38) is

Choose, for example, any fixed A>5/c_0. This proves (37) simultaneously for all admissible tuples.

Consequences of an alleged cover. The random part of the argument is complete. We now keep the deletion outcome fixed and show deterministically that the simultaneous events exclude any cover without an almost full pencil. Random sampling below is only a way to find a short witness inside a fixed cover.

Fix a realization satisfying both (34) and (37). Suppose that the second conclusion of the lemma fails. From an offending cover remove every line which actually occurred as a listed deletion shape. Such a line contains no point of X, so the remaining line set L still covers all but at most 2q points of X. Put m=|L|, and for any projective point p write n_p=|\{\ell\in L:p\in\ell\}|. Define

The count of covered survivors and (35) give

Since \delta_q\geq\delta and m\leq q, this implies

For the second estimate, subtract the number of covered survivors from \sum_{\ell\in L}|X\cap\ell| and use m\leq q. Finally, put

The failure of the pencil conclusion implies R\leq(1-\rho)q. We will find an admissible tuple of lines from L with fewer than \delta t^2/2 survivors in its cross-intersection set.

Low concurrency: R\leq q^{1/2+\kappa/4}. Let T=q^{1/2-\kappa/3}. The number of ordered pairs of distinct lines of L meeting at a point x\in X is \sum_{x\in X}n_x(n_x-1). Points with n_x<T contribute at most

The set P=\{x\in X:n_x\geq T\} has size

for sufficiently large q. Theorem 2.1, applied to P and L, therefore gives \sum_{x\in P}n_x\leq q^{3/2-\kappa}. The contribution of these points to the ordered-pair count is at most

Together, (40) and (41) show that the fraction of ordered distinct line pairs meeting in X is

Sample an ordered tuple of 2t distinct lines uniformly from L. The expected number of its cross pairs meeting in X is t^2 times the fraction in (42). Markov’s inequality shows that this number is less than \delta t^2/2 with probability tending to one.

We next check the two admissibility conditions. A given sampled pair is parallel with probability at most R/(m-1). Once two distinct lines have been sampled, at most R population lines pass through their projective intersection, so the probability of concurrency for any specified three sampled positions is at most R/(m-2). The probability of any parallel pair or concurrent triple in the tuple is consequently

If neither event occurs, every cross intersection is finite and the cross intersections are distinct: equality of two different cross intersections would make at least three of the tuple lines concurrent.

To verify (36), fix F\in\mathcal F. Consider the event that F is not a tuple line but contains more than H_0 distinct finite cross intersections. Each tuple line then contains at most D points of F. Greedily choose a cross intersection on F and its two representing positions, and discard all cross intersections on either of those lines. Each step discards at most 2D points. Since H_0=2Dh, this produces h cross pairs whose 2h positions are distinct.

Among the population L, there are at most mDR ordered distinct line pairs, neither line equal to F, whose intersection lies in F. Indeed, the first line meets F in at most D points, and at each such point there are at most R choices of the second line. There are at most t^{2h} ordered choices of the h cross pairs of positions. For each choice, the sampled lines at those 2h distinct positions are uniform among (m)_{2h} assignments, where (z)_a=z(z-1)\cdots(z-a+1). The probability of the event for this fixed shape is therefore at most

The numerator may count assignments with repeated population lines; this only enlarges the upper bound. Summing (44) over all shapes gives

because \kappa<1/10 and h=10(D+1) imply

Thus, with probability tending to one, the sampled tuple is admissible and has fewer than \delta t^2/2 cross pairs meeting in X.

High concurrency: R>q^{1/2+\kappa/4}. Choose a projective point p with n_p=R, and take all R lines of L through p as the pencil. Its complement has size

for sufficiently large q, by (39); no complement line passes through p. Sample the first list of t lines uniformly without replacement from the pencil, and independently sample the second list in the same way from the complement.

Any cross intersection lies off p. At a cross intersection x\in X, exactly one pencil line passes through x, and the number of cross pairs meeting there is the number of complement lines through x, namely n_x-1. Thus at most E_L of all RN population cross pairs meet in X. Their fraction is at most

As before, expectation and Markov’s inequality show that fewer than \delta t^2/2 sampled cross pairs meet in X, with probability tending to one.

For a fixed complement line, at most one pencil line meets it at infinity when p is finite. When p is at infinity, the pencil lines have direction p and every complement line has a different direction, so all cross intersections are finite. The probability of any infinite cross intersection is therefore at most t^2/R. Two equal cross intersections must use the same pencil line, since distinct pencil lines meet only at p, which lies on no complement line. Given two complement lines, their projective intersection determines at most one affine pencil line, namely its join with p. If this join is the line at infinity, there is no affine candidate. Conditioning on the second list and taking a union bound over its pairs shows that the probability of a collision is O(t^3/R). The total probability of a failure of finiteness or distinctness is therefore

Fix F\in\mathcal F, and consider the event that F is not a tuple line but contains more than H_0 distinct finite cross intersections. The same greedy argument gives h cross pairs with disjoint positions. There are at most DN population cross pairs, with neither line equal to F, whose intersection lies in F: a complement line distinct from F meets F in at most D points, all off p, and each such point determines at most one pencil line. The two lists are sampled independently, so the probability of this occupancy violation for a fixed shape is at most

After summing over \mathcal F, the bound becomes

since

The sampled tuple is consequently admissible and has fewer than \delta t^2/2 cross pairs meeting in X, with probability tending to one in this regime as well.

The contradiction and the order of choices. All sampling estimates above are uniform over line sets satisfying (39) and the appropriate bound on R. In either regime, for every sufficiently large q there is therefore an admissible tuple from the fixed line set L with

No line of L actually occurred as a listed deletion shape. Hence ignoring exact occurrences of its tuple lines changes none of the deletions in the fixed realization, and the tuple’s count Y_0 is exactly |X\cap P_0|. This contradicts (37).

In particular, the cover and the tuple are allowed to depend on the realized deletions: the event (37) was established simultaneously for every admissible tuple before fixing the realization. Sampling from L is used only to prove the existence of a tuple inside that fixed realization. No concentration estimate is conditioned on the choice of the cover. The contradiction proves the second conclusion, and finishes the proof.□

Proof. We grow a set of vertices with small size compared with the number of parts it reaches. Whenever it does not yet dominate those parts, we use an undominated vertex to reach another part. A minimality condition on the transversals prevents this growth from stopping without the required domination certificate.

Choose an inclusion-minimal nonempty subfamily of parts with no independent transversal, and distinguish one part A_* of this subfamily. Let \mathcal U be the family of independent transversals of all its other parts. Minimality makes \mathcal U nonempty. The deficient subfamily has at least two parts, since every part is nonempty.

Choose any x_1\in A_*. Among U\in\mathcal U, minimize |N(x_1)\cap U|, where N(x) denotes the neighborhood of x in G. Fix a minimizer and write Y_1=N(x_1)\cap U. This set is nonempty: otherwise adjoining x_1 would give an independent transversal of the deficient subfamily.

Inductively, suppose that vertices x_1,\ldots,x_j and sets Y_1,\ldots,Y_j have been fixed with the following properties:

1. 1.

   The sets Y_a are nonempty and pairwise disjoint, and some U\in\mathcal U jointly realizes all the equalities

   N(x_a)\cap U=Y_a\qquad(1\le a\le j).
2. 2.

   At stage a, the size |Y_a| was minimized over all U\in\mathcal U satisfying the already fixed equalities for indices smaller than a.

3. 3.

   Each x_a lies either in A_* or in a part represented by a vertex of some earlier Y_b, with b<a.

Let Y=\bigcup_{a=1}^jY_a, let I consist of the distinguished part and all parts represented in Y, and put

By joint realization, the vertices of Y occupy distinct parts, none of them A_*. Thus |I|=|Y|+1, while nonemptiness of the Y_a gives j\le |Y|. The third invariant shows that T lies in the union of the parts indexed by I, and

If T dominates this union, we have the required certificate.

Otherwise, choose a vertex x_{j+1} in that union, outside T, with no neighbor in T. Among the transversals realizing all the current equalities, choose U minimizing |N(x_{j+1})\cap U|, and set

This set avoids all the previous Y_a, because x_{j+1} has no neighbor in T. We claim it is nonempty.

If it were empty and x_{j+1}\in A_*, then U\cup\{x_{j+1}\} would be an independent transversal of the deficient subfamily. Otherwise, the part of x_{j+1} contains a unique vertex y of Y, say y\in Y_b. The transversal U uses y in that part, so x_{j+1}\notin U. Replace y by x_{j+1} to form

Since N(x_{j+1})\cap U=\varnothing, this is again an independent transversal of the nondistinguished parts. For every a<b, the vertex y does not belong to Y_a, and the new vertex is not adjacent to x_a. Consequently the exact earlier equalities are preserved:

For a=b, the replacement removes the neighbor y and adds no neighbor, so

This contradicts the minimum imposed at stage b. Notice that the contradiction uses only the equalities preceding stage b; preservation of later equalities is not required.

Thus Y_{j+1} is nonempty and all the induction invariants continue to hold. Each continuation adds vertices in previously unrepresented parts to Y, whereas all of Y lies in one transversal of the fixed nondistinguished subfamily. There can be only finitely many continuations. The process must therefore stop with a dominating set T, proving the lemma.□

Proof of Theorem 4.1. The case n=0 is immediate, so suppose n\ge1. Fix D and, for the moment, a constant integer K\ge6. We will choose K sufficiently large in terms of D at the end.

Form a graph whose vertices are the candidate positions (i,k), partitioned into the n pools. Put an edge between candidates in different pools precisely when their translates conflict. Candidate positions are distinct vertices even when their sampled shifts happen to coincide. An independent transversal in this graph is exactly a selection as in the theorem.

By Lemma 4.2, it suffices to show that, with probability tending to one, there are no nonempty index sets I, with |I|=m, and sets T of at most 2m candidate positions in those pools that dominate their union. We use the slightly weaker bound 2m to simplify the counting. Throughout the probability estimates, I and T are fixed sets of indices before any shifts are exposed.

The proof splits according to m, the number of pools in the certificate. When m is small, the forbidden lines associated with T occupy only a small part of each candidate’s possible shifts. When m is proportional to q, that direct bound is insufficient. Instead, we expose T in a bounded number of chunks and prove that a positive average proportion of shifts remains feasible. Crucially, this proportion will depend only on D, so we may subsequently choose K large enough that the unused candidates defeat all certificates.

Forbidden equations and counting possible certificates. For every direction d in use, fix a nonzero linear functional \pi_d:\F_q^2\to\F_q whose kernel is d. After exposing the shifts of the candidates e\in T, call a shift b\in\F_q^2 feasible for target i if, for every such e, with source-pool index j, it avoids every equation

We impose these prohibitions even when i=j. This only makes feasibility more restrictive. A feasible candidate outside T has no neighbor in T, so its existence prevents domination.

Set

For one target i and one exposed candidate e, there are at most C equations in (48). This remains true if the two lists D_i and D_j are counted separately, retaining duplicate directions. Each equation excludes one affine line, containing exactly q shifts.

The number of choices of I is at most

There is an absolute constant C_*>0 such that, for K\ge6, the number of candidate-index sets T in these pools with |T|\le2m is at most

For example, the usual bound \sum_{t=0}^{r}\binom Nt\le(eN/r)^r for 1\le r\le N/2 applies with N=Km and r=2m.

The range 1\le m\le c_1q. Condition on all the exposed shifts in T. A fresh uniform shift for any target i\in I is infeasible with probability at most

At least (K-2)m candidate positions in the target pools remain unexposed. Their shifts are conditionally independent and uniform. Thus the probability that T dominates, for this fixed I,T, is at most

Combining this with the counts of I and T, the probability of a dominating certificate of size parameter m is at most

Choose K large enough that

Then the bracket in (52) is at most 1/2 throughout this range, and tends to zero for every fixed positive m. Summing over m gives o(1): for a fixed cutoff, the finite initial sum tends to zero, while the remaining terms are bounded by a geometric tail.

A feasible-density estimate for m>c_1q. We prove that there is a constant \delta_1>0, depending only on D and not on K, such that for every fixed I,T in this range,

Here U_i^{\mathrm{fin}} is the set of shifts feasible for target i after all candidates in T have been exposed. The estimate is uniform in I,T and the configuration data. The lower cutoff on q may depend on the fixed value of K.

Expose the candidate positions of T in a fixed order, divided into consecutive chunks of size at most \lfloor\alpha q\rfloor, with all but the last having that size. For sufficiently large q, \lfloor\alpha q\rfloor\ge\alpha q/2. Since |T|\le2m\le2Dq, the number of chunks is at most

In particular, this bound does not involve K. If T is empty, the desired feasible-density estimate holds deterministically; otherwise there is at least one chunk.

At the start of a chunk, condition on all shifts previously exposed. Let U_i be the set of shifts still feasible for target i, and write

For the analysis of this chunk we keep all these sets frozen at their start values. They are now deterministic, while the shifts belonging to the new chunk are independent uniform vectors.

For an entry e of the chunk, with source-pool index j, define Z_e by summing, over all equations (48) associated with i\in I and e, the number of shifts b\in U_i satisfying that equation. Count the D_i and D_j lists separately, including duplicates. A shift deleted more than once is therefore counted more than once, which is harmless for an upper bound on loss. Each line contains at most q shifts, and each of its right-hand sides is uniform in \F_q. Consequently,

All expectations and variances in the following chunk calculation are conditional on the fixed past.

The terms whose directions belong to the target. The expectation bound alone does not control the loss in a chunk. We estimate its fluctuations by separating the two direction lists in each forbidden equation. Bounded reuse of target directions handles one list; the affine second moment will handle the source list. Write

where Z_e^{(1)} uses the list D_i in each target, and Z_e^{(2)} uses the list D_j of the source. Group the terms of Z_e^{(1)} by direction. The group for d is a function only of \pi_d(b_e). For distinct directions d,d', the functionals \pi_d,\pi_{d'} are linearly independent, so

is a bijection from \F_q^2 to itself. The two coordinates are therefore independent and uniform. The direction groups are pairwise independent, which suffices for adding their variances.

There are at most Dm such groups. Each direction belongs to at most D target direction sets; for each associated target-source pair there are at most D^2 choices of (u,v). Thus every group is bounded by D^3q, and

The terms whose directions belong to the source. For each target i and each direction d, define the variance of its parallel line slices by

where the sum is over the q affine lines of direction d. These variances obey the exact identity

where the sum runs over all q+1 directions. This is precisely the normalized affine second-moment identity in [27, Lemma A.1], applied to U_i\subseteq\F_q^2. That identity holds for every subset of every finite affine plane; it has no randomness, characteristic, or subfield hypothesis. Thus it applies after conditioning on any history of earlier chunks. This is the reason we can control all source directions even when the feasible sets U_i have complicated shapes.

Every individual summand of Z_e^{(2)} associated with i,d,u,v is a uniformly sampled line-slice count, with its slice index translated by a fixed offset. Its variance is therefore V_{i,d}. There are at most D^3m summands, and each pair (i,d) is repeated at most D^2 times. Cauchy–Schwarz applied to their centered sum, without any independence assumption, gives

Each source pool contributes at most K entries to the chunk, and each direction belongs to at most D source direction sets. Consequently, by (59),

Call an entry regular if A_e\le mq^{3/2}. There are at most KD\sqrt q irregular entries. For a regular entry, (57), (60), and \operatorname{Var}(X+Y)\le2\operatorname{Var}(X)+2\operatorname{Var}(Y) give

For a fixed constant \gamma>0, Chebyshev’s inequality and (56) therefore imply

where B_{D,\gamma} is independent of K. In the last step we used m>c_1q.

Conditional independence and loss over one chunk. The preceding variance bounds show that each regular entry has a small chance of removing far more than its expected share. We now use independence within the chunk to show that few entries do so, and convert that statement into a deterministic bound on the total remaining feasible set.

The regularity of an entry is determined by the frozen sets U_i and its fixed source-pool index. In particular, it does not depend on its fresh shift b_e. After conditioning on the past, the collection of regular entries is fixed, and their variables Z_e are independent functions of independent shifts. Their common threshold in (63) is also fixed under this conditioning.

A union bound over subsets of regular entries, using the chunk size bound and (63), shows that the probability of at least \gamma q threshold exceedances is at most

for all sufficiently large q, with c_{D,\gamma}>0 independent of K. If there are fewer than \lceil\gamma q\rceil regular entries, the event in question is empty and the bound remains valid.

For each fixed K, we may also take q sufficiently large that

Except on the event in (64), all but at most 2\gamma q entries are regular and below the threshold: the exceptions include all irregular entries. The actual loss of feasible shifts within the chunk is at most \sum_eZ_e, because these counts used the larger feasible sets at the start of the chunk. Bounding each exceptional entry by Cmq and all other entries by the threshold gives, for the end-of-chunk value M', the deterministic inequality

Choose \gamma>0, depending only on D, so small that

At the beginning, before exposing T, every shift is feasible, so M=mq^2. If all J\le J_0 chunks satisfy (66), iteration gives

The conditional probability bound (64) holds for every possible past. Averaging over the past and taking a union bound over the at most J_0 chunks proves (54). The constants J_0, \gamma, and \delta_1 depend only on D. The dependence on K in (65) affects only how large q must be, not these constants.

Unused candidates and the large-range union bound. We have established the required positive average feasible density with a failure probability of order \exp(-\Omega_D(q\log q)). There are only exponentially many candidate certificates, so this error can be summed over all of them. On the successful event, the unused candidates now supply the further exponential saving needed to rule out domination.

Condition now on all the shifts belonging to T, and suppose the feasible-density event in (54) succeeds. Let t_i be the number of exposed candidate positions from pool i. Every unused candidate from that pool remains independent and uniform, and is feasible with probability |U_i^{\mathrm{fin}}|/q^2. The probability that none of the unused candidates in the target pools is feasible is therefore at most

To obtain the last inequality, use

This argument also covers pools for which every candidate belongs to T; it does not assume K-t_i is positive in every target pool.

For m>c_1q, the number of pairs I,T is at most A_K^m, where

For each fixed pair, domination can occur only if the feasible-density estimate fails or all unused candidates are infeasible despite its success. The sum of the first failure probabilities over all m,I,T in the large range is bounded by

Here the number of choices is at most \sum_{m\le Dq}A_K^m=\exp(O_{D,K}(q)), with K fixed.

Finally choose K sufficiently large, still depending only on D, so that both (53) and

hold. Such a choice exists because \delta_1>0 does not depend on K, whereas A_K grows only quadratically in K. By (68), the sum of the remaining failure probabilities is then at most

Together with the small-range estimate, this excludes all dominating certificates with probability tending to one. Lemma 4.2 therefore supplies an independent transversal, proving the theorem.

The choices have been made in the order

In particular, K is fixed before taking q to infinity, and all sufficiently-large-q conditions may depend on that fixed K. Every estimate above is uniform over the configurations and direction sets subject to the bounds in the theorem.□

Proof. Let s tend to infinity through primes congruent to 2\pmod3. Since \gcd(3,s-1)=1, cubing permutes \F_s^* and fixes zero. Thus f is bijective. It maps horizontal lines to horizontal lines and vertical lines to vertical lines. We first prove the two survival properties simultaneously with high probability, then use them to classify mixed covers satisfying (71).

Survivors in the original coordinates. Choose the lines \ell_d, independently for the s-1 values of d, uniformly within their parallel classes. Fix a line \ell of finite nonzero slope d, and temporarily ignore the choice \ell_d. Each of the other s-2 choices deletes a uniformly distributed point of \ell. Let Z_\ell count the surviving points on \ell. Its expectation is

Changing one of these choices changes the survivor count by at most two. Apply the independent-trial jump bound and bounded-drift concentration estimate of [27, Lemmas A.2–A.3] to the exposure martingale, with T=s-2, L=2, and u=\mu/2. The martingale has zero drift, and hence

There are fewer than s^2 lines under consideration. A union bound, together with \mu/2\ge5 for sufficiently large s, shows that all these counts are at least five with probability tending to one. If \ell\ne\ell_d, reinstating the deletion by \ell_d changes no point on \ell, since the two lines are parallel. Thus every required line in the original coordinates has at least five points of Y.

Survivors and almost-pencil covers in the new coordinates. In the new coordinates, the possible deletion shapes are

There are s(s-1) such shapes, each of size s, and each of the s-1 independent trials chooses one of them. Every point is deleted by a specified trial with probability 1/s, so its overall survival probability is the uniform value

for all sufficiently large s.

Each shape meets every affine line in at most three points. For a vertical line this follows from bijectivity of cubing; for a horizontal line it follows from d\ne0. For a line of finite nonzero slope m, the intersection is determined by

a nonzero polynomial equation of degree three. In particular, no shape is itself a line when s>5. All the hypotheses of Lemma 3.2 hold with field size s, a fixed integer constant, for example D=3, survival lower bound \delta=1/4, and \rho_0=1/100. The exact-line occurrence probabilities are zero, and the subfield restriction is automatic for a prime field. With probability tending to one, every line consequently contains at least s/8 points of f(Y), and its almost-cover conclusion holds for f(Y) as well. We now combine that conclusion with the lower bound on every line to replace an almost pencil by a complete one.

From an almost pencil to a full parallel class. Assume these events hold, and consider a cover satisfying (71). Repeated resources can be removed; alternatively, one may keep their original counts, since removal only reduces the budget. The line portion has at most s distinct lines and leaves at most b\le2s points of f(Y) uncovered. Lemma 3.2 supplies at least (1-\rho_0)s distinct lines in this portion through a common projective point p. There are at most \rho_0s other lines, and

If an affine line through p were absent from the cover, all the chosen lines through p would cover at most one of its affine points. The other lines would cover at most \rho_0s further points, and the individual point resources at most 2\rho_0s. Thus at most 1+3\rho_0s points of this missing line would be covered. For sufficiently large s, this contradicts

Every affine line through p must therefore be present. A finite p requires s+1 lines, which is impossible. An infinite p requires all s lines in its parallel class, and then (71) forces a=s and b=0. This also rules out repetitions in a cover attaining the budget.

The events used in the two coordinate systems hold simultaneously with probability tending to one. Consequently every sufficiently large prime s\equiv2\pmod3 admits a successful configuration Y. A mixed cover of cost less than s would satisfy (71) but not its necessary equality conclusion. The two stated consequences follow.□

Proof. Undo the translation and apply M_i^{-1}. An ambient line in the given direction meeting P_{i,k} becomes a line through a point of \F_s^2 in a finite nonzero subfield direction. Its intersection with \F_s^2 is the corresponding subfield line. The s lines in that subfield parallel class extend to distinct parallel ambient lines. Exactly one is the omitted line in the definition of Y; the other s-1 each contain at least five points of Y, by Lemma 5.1. These are precisely the lines meeting the candidate’s retained configuration.□

Proof. We verify the hypotheses of Lemma 3.2 for the full pool, which gives the first two assertions. The third follows from a separate union bound over finite points and lines.

Treat each candidate shift as one independent deletion trial, listing the lines of \mathcal B_{i,k}. There are KN_q=O_{s,K}(q) trials, each listing m=(s-1)^2 lines. We may take the shape family to be all q(q+1) ambient affine lines. Each shape has size q, and two distinct line shapes intersect in at most one point. Thus the shape and trial bounds in Lemma 3.2 hold with a sufficiently large fixed integer D depending only on s,K.

A candidate’s deleting set is a uniform translate of a fixed union of m lines. Its deletion probability at a fixed point is independent of the point and is at most m/q. Independence of the shifts makes the overall survival probability \delta_q uniform on \F_q^2. For sufficiently large q, m/q\le1/2 and N_q\le2q/(s-1). Using \log(1-t)\ge-2t for 0\le t\le1/2, we obtain

Fix \delta=\exp(-4K(s-1)) and \rho=\delta/10.

For completeness, the exact-line hypothesis also has a uniform bound. A fixed line \ell of direction d can occur only in candidates of groups with d\in S_i, of which there are at most two. In each such candidate, there are s-1 translated lines in this direction. Each fixed line has probability 1/q of becoming \ell under the uniform shift. Therefore the sum, over all trials, of the probabilities of listing \ell is at most

Increasing the fixed D if necessary verifies every hypothesis of Lemma 3.2. Its conclusions give the first two properties.

To prove the third, fix p\notin\ell. For one candidate in group i, there are at most s-1 possible points y\in\ell whose join to p has a direction in S_i: each such direction contributes at most one intersection with \ell. A fixed point belongs to a uniform translate of W_i with probability s^2/q^2. The probability for this candidate is thus at most

If six distinct groups meet the condition, choose one witnessing candidate from each. There are at most (KN_q)^6=O_{s,K}(q^6) choices, and their shifts are independent. For the fixed pair (p,\ell), the probability of six such groups is therefore O_{s,K}(q^{-6}). There are at most q^2q(q+1)=O(q^4) pairs (p,\ell). The union bound gives a total failure probability O_{s,K}(q^{-2}), proving the claim.□

Proof. There are four types of pairs, according to whether their edges are ordinary or exceptional and, in the latter case, whether their group indices agree.

Two ordinary edges with distinct base points share the ordinary label of their join. Next, an exceptional base point y\in Y_i lies on a deletion line in every direction of the nonempty set S_i, so y\notin X. Its join with x\in X cannot have direction in S_i: otherwise that join would be a selected deletion line containing x. Its ordinary label therefore belongs to both the exceptional edge and e_x.

For exceptional edges from distinct groups i,j, the base points are distinct by (75). That same separation condition ensures that their join has direction outside both D_i and D_j, and hence outside S_i\cup S_j. The two edges share its ordinary label.

Finally, consider e_{i,w} and e_{i,w'} with w\ne w'. The transformed points f(w),f(w') are distinct. If their join has finite nonzero slope t, the exceptional edges share the special label of this subfield line in the part of direction M_i(t). If their join is horizontal or vertical, the relevant original coordinates are equal as well, because f preserves these two parallel classes bijectively. The original base points then share an ordinary axis-direction label, in a direction of A_i. This completes the intersection proof.

We also check that the parameters count distinct edges, as required when we count exceptional edges below. Two ordinary labels in nonparallel directions determine the ordinary base point, so ordinary edges are distinct. An exceptional edge has special labels and cannot equal an ordinary edge. Within one group, the special labels in any two distinct directions of S_i determine f(w), since the corresponding subfield lines are nonparallel. As |S_i|=s-1\ge2, equal exceptional edges within a group would imply w=w'. Finally, any special label tagged by group i is absent from every edge of a different group. Exceptional edges in distinct groups are therefore distinct too.□

Proof. The assertions for special vertices and altered ordinary directions follow directly from (78). For an axis direction, undoing b_i,M_i fixes one original coordinate, so applying f gives the corresponding horizontal or vertical line. A line in a direction outside S_i\cup A_i cannot contain two points of P_i, since the join directions of that embedded subplane are exactly S_i\cup A_i. It therefore covers at most one exceptional position. A singleton can be included in an arbitrary subfield line through it, and an empty set requires no covering resource.□

Completion of the proof of Theorem 1.1. We prove that H has no vertex cover of size at most q. Suppose to the contrary that C is such a cover. Its ordinary vertices, regarded as affine lines, must cover X: special vertices belong to no ordinary edge. These lines also cover X_{\rm pool}. Lemma 6.2 therefore gives a projective point p such that at least (1-\rho)q ordinary vertices of C are lines through p. The line-survival bound will force every undeleted member of this pencil into C. We then count the vertices left for exceptional edges, separating centers at infinity, centers inside one of the sets P_i, and finite centers outside them all.

Every undeleted line in this pencil is forced. We claim that

where incidence with an infinite p means that \ell has the corresponding direction. If o_\ell were missing, all other lines of C through p would cover at most one affine point of \ell. There are at most \rho q vertices outside the large pencil subcollection. Each of their ordinary lines covers at most one point of \ell, and their special vertices cover no ordinary edge. Consequently

This contradicts (77), since \delta q/2>1+\rho q for sufficiently large q and \rho=\delta/10. At infinity the pencil lines are parallel, so the possible contribution of one central point is absent; the same upper bound still applies.

Let F_p be the set of ordinary vertices forced by (79), and call the vertices of C\setminus F_p the additional vertices. The deleted pencil lines determine how many additional vertices the assumed budget |C|\le q permits.

An infinite center. Suppose p is the point at infinity in direction d. Put

Only these groups contribute deletion lines in direction d, and each contributes s-1, by Lemma 6.1. At most z(s-1) of the q lines in this parallel class belong to B. Thus

None of the forced vertices covers any exceptional edge of a group in I_d, because those groups use special vertices in direction d.

If z=1, all positions of this group’s f(Y) must therefore be covered by at most s-1 additional vertices. By Lemma 7.2, their effects can be included in at most s-1 subfield lines. This contradicts Lemma 5.1.

If z=2, the two groups are 1,*, by (72). An additional vertex can now meet both groups, so we use the weighted line-and-point budget instead of counting one line per vertex. For each of these groups let a_i count the additional vertices that cover at least one of its positions and are either special vertices of this group or ordinary vertices in its axis directions A_i. Let b_i' count the other additional vertices covering a position of the group. By Lemma 7.2, the latter vertices each cover only a singleton. The former supply subfield lines. The weighted conclusion of Lemma 5.1 gives

Each additional vertex contributes at most one to the sum of the two left sides. A special vertex is confined to its tagged group. An ordinary axis-direction vertex counted in a_i is a line meeting P_i with direction in A_i\subseteq D_i; by (75) it cannot meet the other group’s P_j. It therefore contributes nothing to that other group, even as a singleton. Any vertex of neither exclusive type contributes at most 1/2 to each group. This accounts for every type of additional vertex, including those covering neither group. Summing (80), we obtain

a contradiction.

A finite center inside an embedded configuration. Now let p be finite, and write

There are q+1 affine lines through p, so

The loss of one in the second inequality comes from the q+1 members of a finite pencil and the assumed cover size q. If h_p=0, the forced vertices already exceed the permitted size of C. We may therefore assume h_p\ge1 in both finite-center cases.

Suppose p\in P_i, for the necessarily unique such group. Every deletion line through p comes from this group: a line from another group would contradict (75), since its direction belongs to that other group’s conflict set. There is at most one such line in each direction of S_i, and hence

Let w_p=M_i^{-1}(p-b_i)\in\F_s^2, whether or not w_p\in Y. We account for the exceptional positions of this group covered by F_p: they will all lie on two nonparallel lines in the new coordinates. For a position with base point y\ne p, its join with p has a direction in S_i\cup A_i. A direction in S_i cannot cover this edge by an ordinary vertex. Any actual forced coverage must therefore lie along one of the two axis-direction lines through p. A position based at p itself, if present, lies on both these axes as well.

Since f preserves the two coordinate parallel classes, all these covered positions are contained, in the new coordinates, in the horizontal and vertical lines through f(w_p). The remaining positions are covered by the additional vertices; each can be included in one subfield line by Lemma 7.2. Equations (81) and (82) would thus give a cover of f(Y) by at most

lines containing the two nonparallel coordinate lines. These are legitimate covering resources whether or not their ordinary labels belong to F_p: their union contains every position covered by F_p. Removing any duplicate replacement lines preserves these two distinct lines and can only decrease the count. This contradicts Lemma 5.1.

A finite center outside all embedded configurations. It remains to consider p\notin\bigcup_{i\in\mathcal I}P_i. Here we use the five points on each deletion line, rather than the small-plane cover obstruction. We will find 5h_p exceptional edges missed by F_p, while each additional vertex covers at most five of them.

Each group contributes at most one deletion line through p. Indeed, two distinct such lines cannot be parallel. After undoing b_i,M_i, their subfield affine equations have distinct subfield directions. Solving these two equations uses a nonsingular linear system over \F_s, so their intersection lies in \F_s^2. This would place p in P_i, a contradiction. Also, deletion lines from different groups cannot coincide, by (75).

The h_p deletion lines through p therefore come from h_p distinct groups. From each such group i, choose five distinct points of Y_i on its contributing line, possible by Lemma 6.1. These give 5h_p distinct exceptional edges, by Proposition 7.1. None is covered by a forced ordinary vertex: its unique join line to p is precisely its contributing deletion line, whose direction is altered for that group.

Any one additional vertex covers at most five of these selected edges. For a special vertex this follows because it belongs to only one group. An ordinary line through p covers none, by the same unique-join and altered-direction argument. Finally, let an ordinary vertex o_\ell, with \ell not through p, cover some selected edges. The line \ell meets each contributing line in at most one point, so o_\ell covers at most one selected edge from each contributing group. Every such group has a selected point y\in Y_i\cap\ell whose join to p has direction in S_i. The third part of Lemma 6.2, which applies to all candidates and hence to the selection, bounds the number of these groups by five. This proves the asserted bound for every additional vertex.

By (81), at most h_p-1 additional vertices are available. They can cover at most 5(h_p-1) of the 5h_p selected edges, a final contradiction.

We have ruled out every possible projective center p, and hence every vertex cover of size at most q. Therefore \tau(H)\ge q+1. Conversely, any edge of the nonempty intersecting hypergraph H is itself a vertex cover and has size q+1. It follows that

The parameter choices in Section 6 give this hypergraph for every sufficiently large odd integer n, with q=s^n, after fixing any sufficiently large prime s\equiv2\pmod3 and a successful Y. Choose one such Y for each eligible s, and let n_0(s)\ge3 exceed all the resulting degree thresholds. This proves Theorem 1.1. Since there are arbitrarily large odd integers, it also gives infinitely many ranks r=q+1.□