==== TABLE OF CONTENTS ====
Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//candidates.tex
Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//construction.tex
Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//deletion.tex
Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//elementary.tex
Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//local.tex
Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//merge-split.tex
Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//paper.tex
Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//selection.tex
Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//references.bib
===========================
==== BEGIN Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//candidates.tex ====
\section{Random merged pairs and their candidate graph}\label{sec:candidates}
The construction in Section~\ref{sec:deterministic-construction} calls for
two compatible split lines in every direction. We begin by supplying many
valid choices for each of these lines. We also record which choices
conflict: besides having large sets of candidates, we need their conflict
graph to have controlled degrees and, apart from a small specified set,
controlled codegrees.
Throughout this section, $M_g^0$ and $M_g^1$ are sampled independently and
uniformly from $\mathcal L_g$, independently for different directions
$g$. This sampling law allows the two constituents in a direction to
coincide. In that case they create no adjacency between distinct points
on a target line. With this convention the tuple validity tests of
Section~\ref{sec:deterministic-construction} apply throughout the sampling
space and agree with the original tests whenever every constituent pair
is distinct. We impose distinctness only after obtaining the estimates
below.
A \emph{successful tuple} in direction $g$ is a choice of four distinct
generators $d_0,d_1,d_2,d_3\ne g$ and bits
$\sigma_0,\ldots,\sigma_3$ such that
\[
u_i=M_{d_i}^{\sigma_i}\cap M_{d_{i+1}}^{1-\sigma_{i+1}},
\qquad i\in\mathbb Z/4\mathbb Z,
\]
are four distinct points on one $g$-line. Thus success concerns only
alignment and distinctness. A valid tuple must also pass the additional
tests in Section~\ref{sec:deterministic-construction}: its target line is
not a constituent, neither opposite pair is adjacent, and no external
point on the target line is adjacent to two designated positions.
For each line supporting valid tuples, retain one of them by a fixed
deterministic rule. Let $Q_g$ be the resulting set of tuples in direction
$g$. In particular, distinct members of $Q_g$ have distinct target lines.
Each of the two slots $(g,1),(g,2)$ carries a copy of $Q_g$. These copies
form the vertices of a graph: two vertices in different slots are joined
exactly when their tuples fail a compatibility condition from
Section~\ref{sec:deterministic-construction}; vertices in the same slot
are not joined. Choosing one vertex from each slot with no edges among
the chosen vertices is therefore precisely a compatible choice of the
required tuples. For a vertex $v$, write $L_v$ for its line, $F_v$ for its
four designated points, $\Gamma_v$ for its generator set, and $N(v)$ for
its graph neighborhood.
\begin{proposition}\label{prop:candidate-graph}
There are constants $c_*>0$ and $C_*<\infty$ such that, with probability
$1-o(1)$, the following assertions hold simultaneously, with
$\beta=1/8$ and $c_0=1/5$:
\begin{enumerate}[label=\textup{(\roman*)}]
\item $c_*q\le |Q_g|\le q$ for every direction $g$.
\item Every vertex has degree at most $C_*q$, and has at most $q^\beta$
neighbors in each slot.
\item For every $v$ there is a set $J(v)$ of at most $q^\beta$ vertices
such that $|N(v)\cap N(w)|\le q^\beta$ for $w\notin J(v)$.
Every member of $J(v)$ is adjacent to $v$ or is in its slot.
\item At most $\lceil\log q\rceil$ constituents pass through any affine
point, counting multiplicity. Every line other than one of the $M_g^1$
has at least $c_0q$ points outside $\bigcup_gM_g^1$.
\end{enumerate}
Consequently the event that these assertions hold and that
$M_g^0\ne M_g^1$ for every $g$ has probability $e^{-1}+o(1)$.
\end{proposition}
The proof has two counting stages. First we count successful tuples and
show that, after the validity tests, they occupy linearly many distinct
lines. We then bound incidences among tuples, their designated points,
and test lines; these estimates will give the graph bounds. A moment
argument supplies the uniform tail estimates at both stages. All counts
refer to the independent sampling law above, without conditioning on a
later selection of compatible split lines.
\subsection{A moment argument for small patterns}
When discussing exposure of the random choices, we call a direction a
\emph{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.
\begin{lemma}\label{lem:pattern-moments}
Let $Z=\sum_a I_a$ count labelled patterns in independent colour variables,
where $I_a$ is the indicator of pattern $a$. For each label $a$, let $C_a$
be its deterministic set of tested colours, of uniformly bounded size,
so that $I_a$ is measurable in those variables. A bounded set $K_0$ of
colours may already have fixed values; all overlap tests below concern
the supports $C_a\setminus K_0$.
\begin{enumerate}[label=\textup{(\roman*)}]
\item If, after fixing any further bounded set of colours, the conditional
expected total is $O(1)$ uniformly, then $\E Z^s=O_s(1)$ for every fixed
positive integer $s$.
\item Suppose instead that the conditional expected total is $O(q)$,
and the conditional expected count of patterns using any of the further
exposed colours is $O(1)$. Overlap here excludes the initially fixed
colours. Then
\[
\E|Z-\E Z|^{2s}=O_s(q^s).
\]
All expectations are conditional on the initially fixed colours, if any.
\end{enumerate}
\end{lemma}
\begin{proof}
For (i), expand $Z^s$ as a sum over ordered sequences of $s$ patterns.
After exposing all colours used by a prefix, the conditional expected
number of choices for the next pattern is $O_s(1)$, uniformly in the
values already seen. Summing one entry at a time proves the bound.
For (ii), work in the initially conditioned law and put $p_a=\E I_a$.
Expand the $2s$th centered moment as products of $I_a-p_a$. In each
sequence, form the graph whose entries are adjacent when their supports
outside $K_0$ share a colour. A term with an isolated entry vanishes,
because its centered factor is independent of all the other factors.
Every remaining sequence can be reordered so that each connected
component grows from its first entry, with every later entry sharing a
colour with an earlier one. Each component has at least two entries, so
at most $s$ entries start components.
To sum these terms in absolute value, bound each factor by $I_a+p_a$.
Given a prefix and its exposed values, an unrestricted next entry costs
$O_s(q)$, whereas an entry required to share a colour with the prefix
costs $O_s(1)$. The sums of $p_a$ obey the same bounds: for each fixed
set of earlier colour labels, average the uniform conditional bounds
over its possible values. Induction over the remaining entries therefore
gives $O_s(q^s)$ for each permitted ordering and component pattern.
There are only a bounded number of these, depending on $s$.
\end{proof}
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$.
\subsection{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
\[
\E H_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~\ref{lem:pattern-moments}(ii), for both $H_g$ and $Y_g$;
in particular, $\E Y_g=O(q)$. Its tail estimate and a union bound give,
with probability $1-o(1)$ simultaneously for every $g$,
\begin{equation}\label{eq:tuple-counts}
H_g\ge8q,\qquad Y_g\le C_1q
\end{equation}
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~\ref{lem:pattern-moments}(i)
then supplies the required tail bound.
\paragraph{A constituent target line.}
First fix the two offsets of $g$. The target must be one of the two
specified constituent lines, and the prescribed-line estimate gives
conditional total $O(1)$.
\paragraph{An opposite adjacency.}
A witness consists of an extra colour and an orientation pairing two
opposite positions. This colour is neither the target nor a generator:
a generator pairs consecutive positions. If the witness colour is fresh,
first expose a successful tuple, at expected cost $O(q)$. The choices
for the witness then cost $O(q)q^{-2}=O(q^{-1})$, giving total $O(1)$.
If the witness colour is already exposed, distinguish whether a tuple
generator also overlaps the exposure. With such an overlap the basic
tuple count is $O(1)$. With all tuple generators fresh, enumerate the
target line instead. The exposed witness forces two exact positions on
that line, and the other two positions must lie on it. For fixed labels
and line this costs at most $q^{-6}$, against $O(q^5)$ choices of line
and tuple labels. This case also has conditional total $O(1)$.
\paragraph{An external point adjacent to two positions.}
Here the witness consists of two distinct extra colours, their
orientations, and their common external point $w$ on the target line.
Tuple generators cannot witness this condition. If both witness colours
are fresh, expose a successful tuple first. There are then $O(q^2)$
colour choices and $q$ choices for $w$, each with probability at most
$q^{-4}$. Their total cost is $O(q^{-1})$, against the $O(q)$ cost
of the tuple.
If a witness colour is exposed, first specify that colour and its
orientation. For a tuple overlapping the exposure, the tuple costs
$O(1)$, and $w$ is forced after the tuple's offsets are exposed. The
other witness costs $O(1)$ if it is exposed and $O(q^{-1})$ if it is
fresh. If instead all tuple generators are fresh, enumerate the target
line: the exposed witness prescribes $w$ and one exact tuple position.
For fixed labels and line the tuple costs at most $q^{-5}$, against
$O(q^5)$ choices. The remaining witness still costs at most $O(1)$.
These witnesses exhaust the extra validity failures. Subtracting their
counts from $H_g$ in~\eqref{eq:tuple-counts} leaves linearly many valid
tuples. Cauchy--Schwarz, together with $Y_g\le C_1q$, shows that these
tuples occupy at least $c_*q$ distinct lines. Retaining one tuple on
each such line gives $|Q_g|\ge c_*q$; the upper bound $|Q_g|\le q$
follows from the number of lines in a parallel class. This proves
Proposition~\ref{prop:candidate-graph}(i).
\subsection{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)$:
\begin{enumerate}[label=\textup{(\alph*)}]
\item For a fixed target $g$ and any line $\ell$, at most $q^\theta$
successful tuples designate a point on $\ell$.
\item For any nonconstituent line $\ell$, at most $C_2q$ successful
tuples, over all targets, designate a point on $\ell$.
\item For any two distinct specified generators, at most $q^\theta$
successful tuples, over all targets, use both.
\item 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.
\end{enumerate}
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~\ref{lem:pattern-moments}(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~\ref{lem:pattern-moments}(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~\ref{lem:pattern-moments}(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.
\subsection{Degrees, codegrees, and initial occupancy}
We now translate the incidence estimates into the graph assertions of
Proposition~\ref{prop:candidate-graph}. 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
\[
\E U_\ell=q(1-1/q)^q.
\]
Changing one hit changes $U_\ell$ by at most one. Apply
Lemma~\ref{lem:independent-trial-jumps} to these $q$ independent trials
with $L=1$, and then Lemma~\ref{lem:bounded-drift-concentration} to
their exposure martingale. Since $(1-1/q)^q\to e^{-1}>1/5$, there is
a fixed $\delta>0$ such that $\E U_\ell-q/5\ge\delta q$ for all
sufficiently large $q$. Taking deviation $u=\delta q$, a fixed positive
multiple of $q$, gives probability $\exp(-\Omega(q))$ that
$U_\ell2(1+B),
\label{eq:det-size-condition}
\end{equation}
then there is an intersecting $(q+1)$-partite $(q+1)$-uniform hypergraph
with exactly $q+1$ nonisolated vertices in each part and cover number
$q+1$. Its edges are in bijection with the set $X$ in
\eqref{eq:det-core}.
\end{proposition}
\subsection{Partitions and intersecting edges}
We prove Proposition~\ref{prop:deterministic-reduction} 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:
\begin{itemize}
\item $\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;
\item $(M_g^0\cup M_g^1)\cap X$;
\item $\{u_0,u_2\}$ and $\{u_1,u_3\}$ for each of its two split lines,
using that line's tuple ordering.
\end{itemize}
Distinct lines of $\mathcal L_g$ are disjoint and partition $A$, so
\eqref{eq:det-split-intersection} 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 \eqref{eq:det-split-intersection}. 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 $B1+\rho q/4\geq1+t.
\]
The strict inequality follows from \eqref{eq:det-size-condition}.
The only remaining nonsplit case is $\ell=p+g=M_g^1$. Suppose its
merged block is omitted. A selected regular block represented through
$p$ meets $\ell$ only possibly at $p$. A selected merged block represented
through $p$ consists of a constituent $M_d^0$ through $p$ and its partner
$M_d^1$. The former meets $\ell$ at $p$, and the latter contributes at
most one additional point. None of these lines equals $\ell$, because
its own merged block was omitted. There are at most $B$ such partners,
by the constituent multiplicity bound at $p$. Hence all selected blocks
represented through $p$ cover at most $1+B$ points on $\ell$. Every
other selected block covers at most two points on $\ell$: regular lines
meet it in at most one, merged pairs in at most two, and split blocks
have size two. Occupancy on $R$ now gives the contradiction
\[
\rho q\leq|\ell\cap R|
\leq1+B+2t
\leq1+B+\rho q/2
<\rho q.
\]
This proves the claimed necessity of the block in every nonsplit
direction.
Put $b=b(p)$. The split lines through $p$ have distinct directions,
because distinct parallel lines do not meet. The claim therefore
requires $q+1-b$ distinct labels, leaving room for at most $b-1$ more.
It remains to check the designated points on those split lines.
\subsection{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
\begin{equation}
|Z(p)|\leq b.
\label{eq:det-partner-count}
\end{equation}
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~\ref{prop:deterministic-reduction}.
\begin{remark}
For the multiplicity bound $B=\lceil\log q\rceil$ used in the
probabilistic construction, it is enough to require explicitly
$q\geq4$ and $\rho q>2(1+\lceil\log q\rceil)$. Every fixed
$\rho>0$ satisfies this inequality for all sufficiently large $q$.
Primality is not used in the deterministic reduction; any restriction
to prime orders must come from establishing the finite configuration
properties.
\end{remark}
==== END Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//construction.tex ====
==== BEGIN Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//deletion.tex ====
\section{Deletion lines and concentration of core covers}
\label{sec:deletion}
The deterministic construction asks for rigidity of line covers of the
core $R_0$. We establish that rigidity in two steps. First, after a fixed
number of lines in each direction are deleted, with probability tending
to one every cover of the surviving set by at most $q$ other lines also
covers almost all of the plane. Second, over a prime field, the Sz\H{o}nyi--Weiner stability
theorem puts almost all lines of such an almost-cover in one pencil.
The deletion law matters. Our eventual split lines come from a constrained
selection, so their law is not uniform. We prove the first step for any
law whose probability at each deletion set is at most $\exp(Kq)$ times
its uniform probability, with $K$ fixed. A qualitative estimate for
uniform deletion would not suffice under this change of measure.
Throughout this section, $q$ tends to infinity through prime powers and
$A=\mathbb F_q^2$. Let $\mathcal L$ be its $q(q+1)$ affine lines. Primality
will be required only for the final application of projective stability.
Fix an integer $k\ge1$. For $q\ge k$, let $\mathsf U_{q,k}$ be the uniform
law on sets $D\subseteq\mathcal L$ containing exactly $k$ lines in each
direction. Define
\[
R_D=A\setminus\bigcup_{\ell\in D}\ell,
\qquad i_D(x)=|\{\ell\in D:x\in\ell\}|.
\]
For probability measures on a countable set, total variation distance is
one half of the sum of the absolute coordinate differences.
\begin{theorem}[Robust deletion estimates]\label{thm:deletion}
Fix $k\ge1$ and $K\ge0$. For each $q$, let $\mathsf Q_q$ be a probability
law on the same sets as $\mathsf U_{q,k}$ such that
\[
\mathsf Q_q(D)\le e^{Kq}\mathsf U_{q,k}(D)
\quad\text{for every }D.
\]
Then the following assertions hold as $q\to\infty$.
\begin{enumerate}[label=\textup{(\roman*)}]
\item The empirical probability measure
$q^{-2}\sum_{x\in A}\delta_{i_D(x)}$ converges in probability, in total
variation, to the Poisson distribution with mean $k$.
\item Write $\mu=e^{-k}$. For every fixed $\lambda,\eta>0$, the probability
that at least $\eta q$ lines $\ell\in\mathcal L\setminus D$ satisfy
\[
\left|\frac{|\ell\cap R_D|}{q}-\mu\right|\ge\lambda
\]
tends to zero.
\item For every fixed $\delta>0$, the probability that there is a set
$C\subseteq\mathcal L\setminus D$ with $|C|\le q$ which covers $R_D$ and
leaves at least $\delta q^2$ points of $A$ uncovered tends to zero.
\end{enumerate}
\end{theorem}
Part~\textup{(iii)} is the cover statement needed for the construction.
The first two parts provide its input: the surviving density and the
occupancy of all but a sublinear number of lines. We prove them in that
order using one counting principle.
For a proposed witness $C$ of size $m$, expose the lines of $D$ and $C$
in a carefully chosen random order. For a positive proportion of orders,
their point-multiplicity profiles will force more than $m$ exposures at
which the next line has atypical occupancy. In the counting experiment,
where $D$ and $C$ are themselves sampled, each such step has conditional
probability $O(q^{-1})$.
The first $m$ savings pay for the at most $q^m\exp(O(q))$ witnesses;
the remaining positive proportion of steps pays for $e^{Kq}$.
Erd\H{o}s and Lov\'asz~\cite[Section~4]{ErdosLovasz1975} count small
covers by their collinear subsets in a random-line construction;
Kahn~\cite{Kahn1992} subsequently strengthened the random-line result.
The profile count below provides the uniform change-of-measure control
used here.
\subsection{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
\begin{equation}\label{eq:profile-limits}
\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.
\end{equation}
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
\begin{equation}\label{eq:profile-incidences}
\int x_{ij}\,d\nu_D(x)=iP_{ij},\qquad
\int x_{ij}\,d\nu_C(x)=jP_{ij}.
\end{equation}
Summing these identities by Tonelli's theorem yields
\begin{equation}\label{eq:profile-means}
\sum_{i,j}iP_{ij}=k,\qquad \sum_{i,j}jP_{ij}=c.
\end{equation}
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$
\emph{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.
\begin{lemma}[Counting by profile detection]\label{lem:profile-counting}
For each $q$, let $\mathscr A_q$ be a deterministic class of pairs $(D,C)$
as above. Assume there is $a>0$ such that every pair in every class has
either $m=0$ or $m\ge aq$. Suppose every subsequential limit
\eqref{eq:profile-limits}, along objects in the classes with $q\to\infty$,
satisfies
\begin{equation}\label{eq:visible-excess}
\nu_D(\text{$D$-visible profiles})+
\nu_C(\text{$C$-visible profiles})>c.
\end{equation}
There is $b>0$ such that, for all sufficiently large $q$,
\[
\mathsf U_{q,k}\{D:\text{some }C\text{ has }(D,C)\in\mathscr A_q\}
\le \exp(-bq\log q).
\]
The constants may depend on $k,a$ and the sequence of classes.
\end{lemma}
\begin{proof}
We first keep $(D,C)$ fixed and show that a positive proportion of
its exposure orders produce more than $m$ marked steps. We then
sample $D$ and $C$ independently and show that so many marks are
rare. Comparing the two experiments will pay for all possible
witness sets $C$.
\paragraph{Exposure of a fixed pair.}
First fix one deterministic object $(D,C)$ and randomize only its
exposure order. Order $D$ and $C$ independently and uniformly, and set
$n_D=k(q+1)$ and $\gamma=\sqrt2$. With equal exposure rates, limiting
point-survival probabilities would depend only on $i+j$.
The irrational exponent makes
$i+\gamma j$ distinct for distinct pairs $(i,j)$, allowing the exposure
test to distinguish both coordinates. Assign the successive $D$-steps the
parameters $d/n_D$ for $d=n_D,n_D-1,\ldots,1$, and the successive
$C$-steps the parameters $(a'/m)^{1/\gamma}$ for
$a'=m,m-1,\ldots,1$. Omit the second list if $m=0$. Interleave the lists
in decreasing parameter order, breaking ties deterministically. At a
step with parameter $z$, the fractions of lines of the two types still
unexposed, including the current line of its type, differ from $z$ and
$z^\gamma$ by at most $O(1/n_D)$ and $O(1/m)$, respectively.
Let $U$ be the points on none of the previously exposed lines. For
fixed thresholds $\eta_0,\epsilon>0$, mark a step if $z>\eta_0$ and its
line $\ell$ satisfies
\begin{equation}\label{eq:mark}
\left|\frac{|\ell\cap U|}{q}-\frac{|U|}{q^2}\right|>\epsilon.
\end{equation}
Write $N$ for the number of marks. We relate its expectation to the
profiles and then count marked exposure sequences.
\paragraph{Detecting the visible profiles.}
For a limit \eqref{eq:profile-limits}, put
\[
u(z)=\sum_{i,j}P_{ij}z^{i+\gamma j},\qquad
f_D(x,z)=\sum_{i\ge1,j\ge0}x_{ij}z^{i-1+\gamma j},\qquad
f_C(x,z)=\sum_{i\ge0,j\ge1}x_{ij}z^{i+\gamma(j-1)}.
\]
These functions are continuous jointly in the displayed variables for
$0\eta_0$ and for all target lines of
type $T$. To verify this, at a $D$-step with $d$ remaining $D$-lines and
$a'$ remaining $C$-lines, a point on $\ell$ of multiplicities $i,j$ is
uncovered with probability
\[
\frac{(d-1)_{i-1}}{(n_D-1)_{i-1}}
\frac{(a')_j}{(m)_j}.
\]
Here $(t)_r=t(t-1)\cdots(t-r+1)$, and the second factor is one if $j=0$;
when $m=0$ only $j=0$ occurs. Off $\ell$, the first factor is
$(d-1)_i/(n_D-1)_i$. The analogous formulas at $C$-steps shift $j$
instead. For bounded $i+j$ these expressions have the claimed uniform
power approximations. The uniform profile mean bound controls the
remaining tails, and the target line itself occupies only $1/q$ of the
plane. We may retain only a subsequence with $m=0$, or one with $m\ge aq$,
so every denominator in the relevant bounded-multiplicity approximation
tends to infinity.
Both normalized uncovered counts have conditional variance $O(1/q)$.
Indeed the previously exposed lines form uniform subsets of specified
sizes with the target excluded. Exchanging a selected and an unselected
line changes either normalized count by at most $2/q$: on the target
each other line meets at most one point, and in the plane each line has
$q$ points. The transposition coupling for sampling without replacement
gives Doob martingale increments at most $2/q$ in $O(q)$ exposures, proving
the variance estimate. This establishes concentration conditional on
each target, uniformly in the target and its step.
For a visible profile $x$ of type $T$, the functions $f_T(x,z)$ and $u(z)$
agree only on a set of Lebesgue measure zero in $(0,1)$. For proof, put
$z=e^{-s}$. Their difference is an analytic generalized Dirichlet series
on $\operatorname{Re}s>0$, with absolutely summable coefficients and
exponents $i+\gamma j$. These exponents are distinct and locally finite.
If the difference vanishes identically and some coefficient is nonzero,
choose its least exponent, divide by the corresponding exponential, and
let $s\to+\infty$. Dominated convergence gives a nonzero limit, a
contradiction. Thus identity of the functions is exactly invisibility.
The zero set of a nonzero analytic function on the real interval is
discrete there and hence null.
At a fixed step the target is uniform among lines of its type. The
uniform parameter grids converge to the probability densities $1$ for
$D$ and $\gamma z^{\gamma-1}$ for $C$. Weak convergence of the products
of these grids and the empirical profile measures, followed by the
open-set lower bound and the conditional concentration just proved,
gives
\begin{align}
\liminf\frac{\mathbb E N}{q}\ \ge\ &
\iint\mathbf1_{\{\eta_03\epsilon\}}
\,d\nu_D(x)\,dz \notag\\
&+\iint\mathbf1_{\{\eta_03\epsilon\}}
\,d\nu_C(x)\,\gamma z^{\gamma-1}\,dz.
\label{eq:marks-limit}
\end{align}
The right side increases to the visible mass sum when the thresholds
decrease to zero.
The limiting test now has a uniform consequence. The strict excess in
\eqref{eq:visible-excess} need not have been quantified in the lemma's
hypothesis; compactness supplies the margin needed for counting.
There are fixed $\eta_0,\epsilon,\xi>0$ such that every sufficiently large
object in the classes satisfies
\begin{equation}\label{eq:marks-margin}
\mathbb E N\ge m+\xi q.
\end{equation}
Otherwise take both thresholds and the proposed margin equal to $1/t$,
choose violating objects with $q_t\to\infty$, and pass to a subsequential
profile limit. For any fixed positive thresholds, their mark count is
eventually no larger than the count at thresholds $1/t$. Its limiting
upper expectation divided by $q_t$ is therefore at most $c$. Equation
\eqref{eq:marks-limit}, followed by decreasing the fixed thresholds to
zero, contradicts \eqref{eq:visible-excess}. This proves the uniform
margin without assuming a quantitative excess in advance. Since
$N\le n_D+m$, \eqref{eq:marks-margin} implies
\begin{equation}\label{eq:marks-positive-probability}
\mathbb P\{N\ge m+\xi q/2\}\ge\frac{\xi q}{2n_D}.
\end{equation}
The probability in this display is only over orderings of the fixed
object, and its lower bound is a positive constant for large $q$.
\paragraph{Counting the marked exposures.}
We have proved that every fixed forbidden pair has a positive probability
of producing more than $m$ marks. We now use a different experiment to
count how often any pair can produce that many marks. Sample $D$ from
$\mathsf U_{q,k}$, sample $C$ independently as a uniform $m$-subset of
$\mathcal L$, and use the same random orderings. This experiment is
\emph{not} conditioned on $D\cap C=\varnothing$. Disjointness will enter
only when we apply \eqref{eq:marks-positive-probability} to an object in
$\mathscr A_q$.
At a $D$-step with $z>\eta_0$, conditional on all past exposures, the
probability of any particular next line is $O(q^{-2})$. To see this,
sample a uniform ordering of direction tokens, with $k$ copies of each
direction, and choose its offsets uniformly without replacement when a
token recurs. A direction has conditional probability at most
$k/(\eta_0n_D)$, and any line in that direction then has probability at
most $1/(q-k)$ for large $q$. Past $C$-exposures do not change this law.
At a $C$-step the same bound follows from uniform sampling without
replacement from $q(q+1)$ lines.
At this point $U$ is fixed by the exposed history.
Lemma~\ref{lem:affine-second-moment} gives, for this arbitrary set,
\begin{equation}\label{eq:affine-variance}
\sum_{\ell\in\mathcal L}
\left(|\ell\cap U|-\frac{|U|}{q}\right)^2
=q|U|-\frac{|U|^2}{q}\le\frac{q^3}{4}.
\end{equation}
It follows that at most $q/(4\epsilon^2)$ lines can cause a mark. Thus every step has
conditional mark probability at most $B/q$, for a fixed $B$; steps below
the parameter threshold have mark probability zero. Multiplying these
conditional bounds over any specified collection of steps and taking a
subset union bound over $O(q)$ steps gives
\begin{equation}\label{eq:many-marks-upper}
\mathbb P\{N\ge m+\xi q/2\}
\le \exp(O(q))q^{-m-\xi q/2}.
\end{equation}
This uses no independence between marks.
\paragraph{Paying for all witnesses.}
By \eqref{eq:marks-positive-probability}, the probability that the sampled
pair belongs to $\mathscr A_q$ is at most a constant times the right side
of \eqref{eq:many-marks-upper}. Passing from a random $C$ to the existence
of a witness $C$ costs at most
\[
\binom{q(q+1)}m\le q^m\exp(O(q)),\qquad 0\le m\le q.
\]
For $m>0$, this follows from $\binom nm\le(en/m)^m$ and
$m\log(q/m)=O(q)$; $m=0$ is immediate. The $q^m$ factors cancel.
Summing over the at most $q+1$ possible values of $m$ leaves
$\exp(-\xi q\log q/2+O(q))$, which proves the lemma.
\end{proof}
\subsection{The three deletion estimates}
\begin{proof}[Proof of Theorem~\ref{thm:deletion}]
Multiplication of the bound in Lemma~\ref{lem:profile-counting} by $e^{Kq}$
still gives a probability tending to zero. We will use this observation
for three classes of witnesses.
\paragraph{The multiplicity law.}
For part~\textup{(i)}, fix a positive total variation tolerance and take
$m=0$ and the class where the $D$-multiplicity profile violates that
tolerance from Poisson$(k)$. In a subsequential limit $j=0$ throughout.
If all $D$-mass is invisible, \eqref{eq:profile-incidences} gives
\[
iP_{i0}=kP_{i-1,0}\quad(i\ge1).
\]
Normalization then forces $P_{i0}=e^{-k}k^i/i!$, contrary to the fixed
tolerance, which persists by total variation convergence. Thus some
positive $D$-mass is visible, and the counting lemma applies with $c=0$.
This proves part~\textup{(i)}.
Fix now the particular sequence of dominated laws in the theorem. By
part~\textup{(i)}, we may choose a deterministic sequence $\epsilon_q$
decreasing to zero sufficiently slowly that, with probability tending
to one, the empirical $D$-multiplicity law lies within $\epsilon_q$ of
Poisson$(k)$. Such a sequence follows by choosing successive thresholds
$1/t$ after their failure probabilities have become small. These
restrictions define deterministic classes of outcomes; they do not
condition the independent counting experiment in the lemma.
\paragraph{Line occupancy.}
For part~\textup{(ii)}, it suffices to take $0<\eta<1$. If at least
$\eta q$ non-$D$ lines have the stated deviation, at least
$m=\lfloor\eta q/2\rfloor$ have deviations of one common sign. Treat
the two signs separately, and let $C$ be any such $m$-set. Include the
Poisson-closeness restriction just chosen in the class of pairs.
In every subsequential limit, the $i$-marginal of $P$ is Poisson$(k)$, so
\[
\sum_jP_{0j}=\mu.
\]
Every limiting $C$-profile has $\sum_jx_{0j}\ge\mu+\lambda$, or every
one has $\sum_jx_{0j}\le\mu-\lambda$, according to the sign. These are
closed conditions on the compact profile space. Consequently all
$C$-mass is visible: an invisible $C$-profile has this row sum equal to
$\sum_jP_{0j}=\mu$.
If all $D$-mass were invisible, the incidence identities would give
\begin{equation}\label{eq:poisson-factorization}
P_{ij}=\frac{k^i}{i!}P_{0j}.
\end{equation}
By Tonelli's theorem and \eqref{eq:profile-means}, this would imply
\[
\int\sum_jx_{0j}\,d\nu_C(x)
=\sum_jjP_{0j}
=e^{-k}\sum_{i,j}jP_{ij}=\mu c.
\]
But the common sign deviation bounds this integral above by
$(\mu-\lambda)c$ or below by $(\mu+\lambda)c$, and
$c=\eta/2>0$. This is a contradiction. There is therefore also positive
visible $D$-mass, giving the strict excess required by the counting
lemma. Its bound, the domination factor, and the vanishing failure
probability of the Poisson restriction prove part~\textup{(ii)}.
\paragraph{A core cover almost covers the plane.}
We have obtained the density and line occupancy needed to analyze a
cover. The occupancy estimates and the budget of $q$ lines force the
$i=0$ row of its limiting profile to be supported on $j=1$. If the cover
still misses a positive proportion of the plane, additional deletion
profiles must then be visible.
A second diagonal choice, using parts~\textup{(i)} and \textup{(ii)},
provides deterministic thresholds tending to zero such that, with
probability tending to one, the Poisson restriction holds and all but
$o(q)$ non-$D$ lines have $|\ell\cap R_D|/q=\mu+o(1)$, with the errors
uniform among the nonexceptional lines. More explicitly, one may choose
$t=t(q)\to\infty$ slowly so that the number of lines with deviation at
least $1/t$ is smaller than $q/t$, except with probability tending to zero.
Fix $\delta>0$ and consider witnesses for failure of part~\textup{(iii)}
subject to these deterministic restrictions. Covering $R_D$ by $m$ lines
implies
\[
\frac mq\ge\frac{|R_D|}{q^2}=\mu+o(1),
\]
so the lower bound on positive $m/q$ required by the counting lemma holds.
In a limit, almost every $C$-profile satisfies
$\sum_jx_{0j}=\mu$, because at most $o(q)$ members of $C$ can be among the
exceptional lines. Covering gives $P_{00}=0$, and $c\le1$. Hence
\[
c\mu
=\int\sum_jx_{0j}\,d\nu_C
=\sum_jjP_{0j}
\ge\sum_jP_{0j}=\mu.
\]
It follows that $c=1$, $P_{01}=\mu$, and $P_{0j}=0$ for $j\ne1$.
Moreover \eqref{eq:profile-incidences} gives
$\int x_{01}\,d\nu_C=P_{01}=\mu$. Since $x_{01}\le\sum_jx_{0j}=\mu$
almost everywhere and $\nu_C$ has mass one, $x_{01}=\mu$ almost everywhere.
Every such profile is visible, because an invisible $C$-profile would
have $x_{01}=P_{00}=0$.
All $D$-mass cannot be invisible either. Otherwise
\eqref{eq:poisson-factorization} and the preceding description of the
$i=0$ row would force $P$ to be supported on $j=1$. This contradicts
$\sum_iP_{i0}\ge\delta$, the limiting fraction of points uncovered by
$C$. Thus the visible mass is strictly greater than $c$ again. The
counting lemma applies, and adding back the vanishing probabilities of
the deterministic restrictions proves part~\textup{(iii)}.
\end{proof}
\subsection{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\H{o}s and
Lov\'asz~\cite[Section~4, proof of Theorem~10, part~II]{ErdosLovasz1975}
forces almost all of a set of $q$ projective points onto one line when
it has sufficiently few disjoint lines. Over prime fields, Sz\H{o}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\H{o}nyi and
Weiner~\cite[Theorem~4]{SzonyiWeiner2012}, also reproduced by H\'eger and
Nagy~\cite[Result~3.6]{HegerNagy2017}. 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.
\begin{lemma}[Prime-plane stability for affine line covers]
\label{lem:prime-stability}
Let $\zeta>0$ and put $\delta_\zeta=\min\{\zeta/4,1/100\}$.
If $q$ is prime and $q\ge\max\{100,4/\zeta\}$, then any set of at most
$q$ distinct affine lines missing fewer than $\delta_\zeta q^2$ affine
points has at least $(1-\zeta)q$ members through a common projective
point. A point at infinity means that these members are parallel.
\end{lemma}
\begin{proof}
We must account for the points at infinity before applying the
projective statement. Let $h<\delta_\zeta q^2$ be the number of missed
affine points and $d$ the
number of represented directions. Extending the lines projectively
leaves exactly $q+1-d$ uncovered points at infinity. Under projective
duality the line set becomes a point set $B$ of size at most $q$, with
\[
\Delta=h+q+1-d\le h+q+1
\]
skew projective lines. Set $\beta=\lfloor q/3\rfloor$. Then
$|B|\le q\le3(q+1)/2-\beta$, and
\[
\Delta\le h+q+1<\delta_\zeta q^2+q+1
\le0.0201q^2<\frac{2q^2}{81}
<\frac29(\beta+1)^2.
\]
Thus the stability theorem applies. Dualizing its conclusion gives at
least
\[
q-\frac{2\Delta}{q+1}
\ge q-\frac{2h}{q+1}-2
>q-2\delta_\zeta q-2
\ge(1-\zeta)q
\]
concurrent lines. The last inequality uses
$2\delta_\zeta\le\zeta/2$ and $2\le\zeta q/2$.
\end{proof}
\begin{corollary}[Concentration of core covers]\label{cor:core-pencil}
Assume the laws of Theorem~\ref{thm:deletion}, and let $q$ tend to infinity
through primes. For each fixed $\zeta>0$, with probability tending to one,
every set $C\subseteq\mathcal L\setminus D$ of at most $q$ lines covering
$R_D$ has at least $(1-\zeta)q$ members through a common projective point.
\end{corollary}
\begin{proof}
Apply Theorem~\ref{thm:deletion}\textup{(iii)} with
$\delta=\delta_\zeta$, followed by Lemma~\ref{lem:prime-stability}.
\end{proof}
==== END Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//deletion.tex ====
==== BEGIN Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//elementary.tex ====
\section{Elementary incidence and concentration estimates}
\label{sec:elementary}
The statements in this appendix do not depend on the construction.
The incidence identity holds over every finite field and for every set
of points, including a set obtained from earlier random choices. The two
probability estimates apply to a specified filtration or to independent
trials; their applications must still supply the relevant stopping rules
and union bounds.
\begin{lemma}[Affine second moment]\label{lem:affine-second-moment}
Let $q$ be a prime power, let $U\subseteq\F_q^2$, and let $\mathcal L$
be the set of all affine lines. Then
\begin{align*}
\sum_{\ell\in\mathcal L}|U\cap\ell|&=(q+1)|U|,\\
\sum_{\ell\in\mathcal L}|U\cap\ell|^2&=|U|^2+q|U|,\\
\sum_{\ell\in\mathcal L}\left(|U\cap\ell|-\frac{|U|}{q}\right)^2
&=q|U|-\frac{|U|^2}{q}\le\frac{q^3}{4}.
\end{align*}
For each direction $d$, define
\[
V_d=\frac1q\sum_{\ell\parallel d}
\left(|U\cap\ell|-\frac{|U|}{q}\right)^2.
\]
Then $\sum_d V_d=|U|-|U|^2/q^2\le |U|\le q^2$.
\end{lemma}
\begin{proof}
Every point lies on $q+1$ affine lines, proving the first identity.
Every ordered pair of distinct points lies on exactly one line; the
$|U|$ equal pairs each lie on $q+1$ lines. Thus the second sum is
$|U|(|U|-1)+(q+1)|U|$. Expanding the square and using
$|\mathcal L|=q(q+1)$ gives the third identity. Its upper bound follows
by maximizing $qx-x^2/q$ for $0\le x\le q^2$, whose maximum is
$q^3/4$ at $x=q^2/2$. Finally, the parallel classes partition
$\mathcal L$, so division by $q$ gives the directional identity.
\end{proof}
The next estimate is the bounded-increment exponential-moment argument
of Azuma~\cite{Azuma1967}, stated for a process with a predictable drift.
We retain a constant that accommodates centering each increment.
\begin{lemma}[Bounded-drift concentration]
\label{lem:bounded-drift-concentration}
Let $(X_t)_{t=0}^T$ be a real process adapted to a filtration
$(\mathcal F_t)_{t=0}^T$, where $T\ge1$ is an integer. Suppose $L>0$
and $|X_{t+1}-X_t|\le L$ almost surely for $0\le t0$ and each
fixed integer $0\le t\le T$,
\[
\Prb\left(\left|X_t-X_0-\sum_{j0$, Markov's inequality bounds the upper tail at $u$ by
$\exp(-\theta u+2TL^2\theta^2)$. Choosing
$\theta=u/(4TL^2)$ gives $\exp(-u^2/(8TL^2))$.
Apply the same argument to $-Z_j$ and add the two tails. This proves a
bound at each fixed time; no maximum over times is being taken.
\end{proof}
\begin{lemma}[Independent-trial jumps]
\label{lem:independent-trial-jumps}
Let $Y$ be an integrable real function of independent trials
$\xi_1,\ldots,\xi_T$. Suppose changing only trial $i$ changes $Y$
by at most $c_i$, where $c_i\ge0$. The Doob martingale obtained by
revealing these trials in order has its $i$th increment bounded in
absolute value by $c_i$, and its conditional variance bounded by $c_i^2$.
In particular, if $T\ge1$ and $c_i\le L$ for a constant $L>0$, then
for every $u>0$,
\[
\Prb(|Y-\E Y|\ge u)\le
2\exp\left(-\frac{u^2}{8TL^2}\right).
\]
\end{lemma}
\begin{proof}
Fix the values of the first $i-1$ trials. For a possible value $z$ of
trial $i$, average $Y$ over the independent future trials to obtain
$f_i(z)$. Coupling the same future trials for two values $z,z'$ gives
$|f_i(z)-f_i(z')|\le c_i$. Independence ensures that this is the
conditional future law for both values. Thus the range of $f_i$ has
length at most $c_i$. Its deviation from its mean over trial $i$ is
bounded in absolute value by $c_i$; this deviation is exactly the
$i$th Doob increment. Its conditional second moment, and hence its
conditional variance, is at most $c_i^2$. The martingale starts at
$\E Y$, ends at $Y$, and has zero conditional drift. Apply
Lemma~\ref{lem:bounded-drift-concentration} at time $T$.
\end{proof}
==== END Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//elementary.tex ====
==== BEGIN Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//local.tex ====
\section{Excluding small covers at affine pencils}\label{sec:pencils}
The deterministic reduction leaves a specific obstruction at an affine
point $p$. If $b$ selected split lines pass through $p$, a hypothetical
cover has already spent $q+1-b$ of its labels on the other directions.
Only $b-1$ labels remain to cover the $4b$ designated points, beyond those
covered by partner lines of constituents through $p$. For $b\ge3$, the
local condition in Section~\ref{sec:deterministic-construction} excludes
precisely this possibility. We prove that the selection procedure returns
a collection violating this condition with probability $o(1)$.
The input from selection is an upper bound for prescribed choices,
conditional on fixed offsets. We first apply that bound and then average
geometric events under the original independent offset law. In
particular, successful return remains part of the event being estimated;
we do not condition the offset law on successful return.
Throughout this section the offsets $M_d^0,M_d^1$ have the independent,
with-replacement law used in the construction. Let $\mathcal A$ be the
event that the selection procedure returns a compatible collection. The
conditional estimate \eqref{sel:conditional-offset-cylinder}, obtained
from Proposition~\ref{sel:selection}, says that for any fixed offset
configuration $M$ and any $s$ prescribed tuple choices in distinct slots,
\begin{equation}\label{eq:pencil-cylinder}
\mathbb P(\mathcal A\text{ and these choices}\mid M)
\le (K/q)^s,
\end{equation}
where $K$ is the fixed constant in that estimate. The prescriptions may
depend on $M$, provided they are fixed once $M$ is fixed. An unavailable
tuple has probability zero, so they may range over all generator and bit
labels. On $\mathcal A$, $M_d^0\ne M_d^1$ for every direction $d$, no selected
split line is a constituent, and constituent multiplicity at every point
is at most $B=\lceil\log q\rceil$.
\begin{proposition}\label{prop:pencil-local}
In the independent offset experiment with the selection procedure above,
\[
\mathbb P\bigl(\mathcal A\text{ and the local condition fails at some }
p\in A\bigr)=o(1).
\]
Here the local condition, required whenever $b(p)\ge3$, is the prohibition
on covers of $F(p)$ by $Z(p)$ and at most $b(p)-1$ additional sets stated in
Section~\ref{sec:deterministic-construction}.
\end{proposition}
The estimate at a fixed point must save three powers of $q$, since we
will sum over $q^2$ affine points. We obtain those savings from two
sources: repeated generator directions and additional incidences forced
by a cover. Three generator reuses already cost $O(q^{-3})$. With zero,
one, or two reuses, we will extract respectively three, two, or one
further incidence costs. The resulting bound at a fixed point is
$O(B^3/q^3)$, apart from the separately controlled event of a large pencil.
\subsection{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.
\begin{lemma}\label{lem:pencil-reuse}
For a fixed affine point $p$, with $\kappa$ the reuse count of the
selected tuples through $p$,
\[
\mathbb P(\mathcal A,\ b(p)\ge2,\ \kappa\ge3)=O(q^{-3}).
\]
\end{lemma}
\begin{proof}
We extract a bounded collection of tuples witnessing three reuses, then
sum its selection and offset probabilities. Form a graph whose vertices
are the tuples and join two vertices when their tuples share a generator.
If the number of vertices minus the number of connected components is at
least three, this graph
contains connected pieces with a total of three noninitial vertices and
at most six vertices altogether. To see this, allocate three units among
the quantities $|C|-1$ for its components, and in each used component grow
a connected set with one more vertex than its allocation. Order each
piece from a root so that every subsequent vertex has a generator already
used in the piece.
If the number of vertices minus the number of components is at most two,
then $\kappa\ge3$ can occur only in a component of three vertices, with a
different generator on each of the three pairwise overlaps. Two components
of size two contribute at most two reuses. In a component of size three,
one generator common to all three contributes exactly two reuses and
precludes any additional overlap. Otherwise three reuses require the
three distinct pairwise overlaps. In an ordering of this triangle, the
second tuple has one old generator and the third has two.
In either case the witness has bounded size. To bound the probability
that one is selected, we bound the expected number of selected witnesses.
A prescription specifies its slots (and hence its target directions),
its generator directions, and its bits.
For a length-$l$ prescription $\pi$, let $T_\pi$ be the offset event that
its tuple lines pass through $p$ and that its positions are distinct and
external to $p$. By conditioning on $M$ first, its contribution is at most
\begin{equation}\label{eq:pencil-weight}
(K/q)^l\mathbb P_M(T_\pi).
\end{equation}
Here $\mathbb P_M$ is the unconditioned independent offset law. Only
after obtaining this bound do we relax restrictions such as distinctness
of slots in the sum of its right side.
We now estimate the sum of \eqref{eq:pencil-weight} by processing the
witness in the order just chosen. Expose all offsets of a tuple's
generators when that tuple is processed. Call a generator old if its
direction has already been exposed. There are a bounded number of
exposed directions in a witness. If the next tuple has $j$ old generators,
there are $O(q^{4-j})$ choices for its
generator and bit labels. A position with two old adjacent generators
is fixed; all other positions are independent and uniform either in the
plane or on an exposed constituent. Their coordinates identifying a
line of the target direction are independent uniform elements of
$\mathbb F_q$. The maximum number $f$ of fixed positions for
$j=0,1,2,3,4$ is respectively $0,0,1,2,4$.
If no position is fixed, there are $O(q)$ target directions and the
alignment probability with the prescribed line $p+g$ is $q^{-4}$.
If a position is fixed, it must be external to $p$ and therefore determines
$g$; the other $4-f$ positions cost $q^{-(4-f)}$. Including the two slot
choices and one factor $K/q$ from \eqref{eq:pencil-weight}, the conditional
extension bounds are
\begin{equation}\label{eq:pencil-extension}
\begin{array}{c|ccccc}
j&0&1&2&3&4\\ \hline
\text{extension bound}&O(1)&O(q^{-1})&O(q^{-2})&O(q^{-2})&O(q^{-1}).
\end{array}
\end{equation}
For $j=2$ both possibilities $f=0$ and $f=1$ give $O(q^{-2})$.
The estimates are uniform in previously exposed offsets. An impossible
fixed-position configuration contributes zero.
Each of the three noninitial steps in the first type of witness saves at
least $q^{-1}$. The triangle saves $q^{-1}$ and $q^{-2}$ at its second
and third steps. Summing the finitely many witness-order types and
iterating \eqref{eq:pencil-extension} proves the lemma. No bound on $b$
was needed.
\end{proof}
\subsection{The aligned law for at most two reuses}
Lemma~\ref{lem:pencil-reuse} 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
\begin{equation}\label{eq:pencil-directions}
(q+1)^{5b-\kappa}
\end{equation}
assignments of target and generator directions: there are $b$ target
entries and $4b-\kappa$ generator classes. Call an assignment
\emph{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 \emph{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,
\begin{equation}\label{eq:pencil-alignment}
\mathbb P_M(\text{alignment})=q^{-4b}.
\end{equation}
Conditional only on alignment, the offsets and positions can be generated
as follows; we refer to this distribution as the \emph{aligned law}.
\begin{enumerate}[label=(\roman*)]
\item At a root, choose four independent uniform points of $L_i$ and set
the generator offsets to the prescribed lines through their endpoints.
\item 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.
\item All offsets in directions outside $\Gamma$ retain their original
independent law.
\end{enumerate}
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
\eqref{eq:pencil-alignment} 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 \emph{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
\eqref{eq:det-partner-set}, with $F$ in place of $F(p)$; throughout
these counts $Z(p)$ refers to this prescribed list.
A \emph{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 \emph{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.
\subsection{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.
\begin{lemma}\label{lem:pencil-small-reuse}
Fix $p\in A$, $3\le b\le B$, an equality pattern with $\kappa=0$ or $1$,
an eligible direction assignment, and the bits. Under the aligned law,
the probability of an admissible bad cover is at most
\[
b^{O(1)}(2B/q)^{3-\kappa}.
\]
The polynomial exponent and implicit constant are absolute.
\end{lemma}
\begin{proof}
When $\kappa=0$, all $4b$ positions are independent uniform points of
their target lines. When $\kappa=1$, two positions of the child are
projections of two parent positions along the shared generator direction.
Call these two child indices dependent. All nondependent positions are
independent uniform points of their target lines, and each has at most
one dependent image. We fix the offsets in unused directions, restricting
to configurations whose unused constituent multiplicity is at most $B$
everywhere. These offsets are independent of the point variables under
the aligned law. Configurations violating this multiplicity bound
contribute no admissible occurrence.
We first turn a cover into incidence conditions. Given an admissible
bad cover, assign each of the $4b$ positions to precoverage or to one of
at most $b-1$ additional covering sets. Mark certain assigned indices as
\emph{surplus}, according to the following rule:
\begin{itemize}
\item Mark every position assigned to precoverage.
\item For an ordinary line or an unused merged pair with at least three
assigned positions, retain two assigned indices as anchors and mark all
others. A set of size at most two needs no marks.
\item For a used merged pair of direction $d$ with $n'$ assigned
positions, mark $\max\{0,n'-2t_d\}$ nonpurposeful indices. There are
enough such indices because there are only $2t_d$ purposeful endpoints.
\end{itemize}
Every additional set retains at most two unmarked indices, except that a
used merged pair may retain an additional $2(t_d-1)$. Each used pair is
allowed at most once. Thus the number of surplus indices is at least
\[
4b-2(b-1)-2\sum_{d\in\Gamma}(t_d-1)
=2b+2-2\kappa.
\]
Discard any dependent indices from the surplus and denote the remainder
by $I$. Then
\begin{equation}\label{eq:pencil-surplus}
|I|\ge 2b+2\quad(\kappa=0),\qquad
|I|\ge 2b-2\quad(\kappa=1).
\end{equation}
For each $v\in I$, its covering assignment gives an incidence condition
on its independent point variable $x_v$, using at most two anchor
variables:
\begin{enumerate}[label=(\alph*)]
\item In precoverage, $x_v$ lies on a partner of an unused constituent
through $p$.
\item On an ordinary line, $x_v$ lies on the line through its two stored
anchors, which are distinct points.
\item On an unused merged pair, choose one stored anchor whose underlying
variable is not $x_v$. Then $x_v$ lies on either constituent of some
unused merged pair containing that anchor.
\item On a used merged pair, $x_v$ lies on the line of that generator
direction through one of its purposeful endpoints. Choose an endpoint
on the constituent actually covering $x_v$.
\end{enumerate}
In every case the candidate line containing $x_v$ differs from its own
target line. Replace a dependent anchor by its underlying parent
variable when recording these dependencies.
No condition needs its own variable as an anchor. Only the case
$\kappa=1$ requires explanation. For an ordinary line, $x_v$ and its
dependent image lie on a shared-generator constituent, which is forbidden
as an ordinary covering line. For an unused pair, the two stored anchors
are different from the surplus index, and at most one can be its
dependent image; choose the other. For a used pair, the surplus index is
nonpurposeful for that generator. If its chosen endpoint were its
dependent image, the line joining the two distinct points would have the
shared generator direction. The surplus index would then itself be
purposeful for that direction, a contradiction.
The surplus count alone does not allow us to multiply incidence
probabilities: one condition may depend on another condition's variable.
We therefore extract a collection with acyclic dependencies. Draw a
directed edge from $v\in I$ to each underlying anchor variable that also
belongs to $I$. This directed graph has no loops and outdegree
at most two. It has an acyclic induced set of size at least
$\lceil |I|/3\rceil$: process the vertices in any order, assigning each
one of three colours not used by its already processed outneighbors. A
monochromatic directed cycle is impossible, since its last processed
vertex has an earlier outneighbor on the cycle. Each colour class is
therefore acyclic. By \eqref{eq:pencil-surplus} and $b\ge3$, we can retain
exactly $3-\kappa$ incidence conditions inducing an acyclic graph.
Only the retained conditions now need to be counted. There are
$b^{O(1)}$ possible specifications of their indices, condition types,
anchor indices, and, when needed, used-generator direction, because at
most three conditions remain. In case (c) the unused direction is left
unspecified. Thus we take a union over these specifications without
enumerating the full cover. By the extraction, it suffices to include
specifications with no self-dependency and with an acyclic dependency
graph.
Fix such a specification and all independent variables outside its
retained indices. The acyclic graph gives an integration order: integrate
the remaining independent uniform variables by
successively removing a vertex of indegree zero. No other remaining
condition depends on the variable removed. With the other variables
fixed, its condition is either impossible or asks for membership in at
most $2B$ lines different from its target line. In case (a) there are at
most $B$ relevant constituents through $p$; in case (c) the fixed anchor
belongs to at most $B$ unused constituents, giving at most $2B$ candidate
constituents of the corresponding pairs. Cases (b) and (d) give one
line. Each candidate line meets the target line in at most one point.
The conditional probability is therefore at most $2B/q$ at every removal.
For this integration we retain only the indicated incidence conditions,
their line exclusions, and the distinctness of any two ordinary-line
anchors needed to define their line. We discard other cover, distinctness, and
admissibility conditions. Their role was to extract a specification with
no self-dependency; retaining them as conditioning would change the law
of the variables being integrated.
The specified event costs at most $(2B/q)^{3-\kappa}$. Sum over the
polynomially many specifications and average over the fixed unused offsets.
\end{proof}
\subsection{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.
\begin{lemma}\label{lem:pencil-two-reuses}
Fix $p\in A$, $3\le b\le B$, an equality pattern with $\kappa=2$, and
the bits. Summed over eligible direction assignments, the probabilities
of alignment and an admissible bad cover are at most
\[
(q+1)^{5b-2}q^{-4b}\,O(b^3/q),\qquad 3\le b\le B.
\]
\end{lemma}
\begin{proof}
For the direction count, regard each target and each generator equality
class as one \emph{token}; there are $5b-2$ tokens. We first estimate the
mean probability of bad geometry over assignments in which all tokens
receive distinct directions. Equivalently, assign them by a uniform
injection into $\mathcal G$. At the end we bound the remaining eligible
assignments, in which a target direction equals a generator direction of
another tuple. Under the aligned law an admissible bad cover requires at
least one of the following four events:
\begin{enumerate}[label=(\roman*)]
\item An unused direction has one constituent through $p$ and the other
through a designated point.
\item A used merged pair meets a point of a tuple not using that generator.
\item Three designated points lie on a line different from every target
line and from every constituent of a used direction.
\item Three noncollinear designated points lie in one unused merged pair.
\end{enumerate}
Indeed, if (i) fails there is no precoverage. If (ii) fails, a used pair
covers only its $2t_d$ purposeful endpoints. Ordinary allowed lines cover
at most two points when (iii) fails. If an unused pair covers three points,
they either witness (iv) or are collinear. In the latter case two lie on
one constituent, so their common line is that unused constituent. By
admissibility it is not a target line, and it cannot be a constituent of
a used direction; thus it witnesses (iii). Without these events the
additional $b-1$ sets cover at most
\[
2(b-1)+2\kappa=2b+2<4b
\]
points, a contradiction.
Conditionally on directions and designated points, unused offsets are
independent. Event (i) has probability $O(b/q)$: for a specified point,
direction, and orientation, the two offsets have prescribed values and
cost $q^{-2}$, and there are $O(bq)$ choices. Event (iv) costs
$O(b^3/q^2)$: choose the three noncollinear points and two that lie on one
constituent. Their joining line determines the direction and one offset;
the parallel line through the third point determines the other offset.
If that direction is unused this costs $q^{-2}$, with two possible offset
orientations.
The remaining events (ii) and (iii) involve used constituents and may
involve projected positions. Their estimates use the randomness of the
direction assignment. To keep the relevant conditional laws explicit,
use the following sequential version of the injection average. Process
roots and children in the order already chosen. First
reveal a tuple's target token, then generate its fresh positions and any
prescribed projections, and finally reveal its new generator tokens and
set their offsets. This has the aligned law: positions use the present
target and any previously fixed shared constituents, but not the values
of the new generator directions. In particular, a projected position
need not be an independent uniform point. When the tested line is fixed
before that position's tuple is processed, its incidence is tested at the
reveal of the tuple's target token; the opposite timing is handled below
by revealing the later generator token. The alignment factor $q^{-4b}$
is the same for every injection. At every stage
unrevealed tokens are uniformly
assigned without replacement among unused directions. In particular a
specific required value determined before a token is revealed costs at
most
\begin{equation}\label{eq:pencil-token}
(q+1-5b)^{-1}=O(q^{-1}).
\end{equation}
Consider (ii) for a specified used constituent and a specified point of
a tuple not using that generator. If the constituent was fixed before
that tuple is processed, a fresh position hits it with probability $1/q$.
A dependent position is the projection of an already fixed shared
constituent onto the new target line. To hit the tested constituent,
the target line must pass through the intersection of the two fixed
constituents. An intersection at $p$ cannot produce an admissible external
point. Any other intersection prescribes a target direction and costs
$O(q^{-1})$ by \eqref{eq:pencil-token}.
In the opposite timing, the tested point is known before the first tuple
using the tested direction is processed. The purposeful endpoint defining
the tested constituent is generated before that new generator token is
revealed. Admissibility makes the endpoint different from the earlier
point. Their joining direction is therefore prescribed at the reveal of
the generator token, again costing $O(q^{-1})$. Summing over $O(b^2)$
choices bounds (ii), jointly with the indicated admissibility conditions,
by $O(b^2/q)$.
For (iii), the three distinct points come from three distinct tuples:
two on one target line would force the triple line to be that target.
The points in the first two processed tuples determine a line $h$.
At the last tuple, a fresh position hits $h$ with probability at most
$1/q$, keeping the necessary exclusion $h\ne L_i$. If the last position
is a projection along a shared constituent $h_s$, the event requires
$h\ne h_s$. Parallel lines give no incidence. Otherwise their
intersection must differ from $p$ and prescribes the new target direction,
giving $O(q^{-1})$ by \eqref{eq:pencil-token}. Summing over triples gives
$O(b^3/q)$. Every constraint in this argument is determined before the
random value used to enforce it is revealed. Other conditions are
discarded in taking these upper bounds.
Combining the four events, the mean bad-geometry probability over
injective token assignments is $O(b^3/q)$. Multiplying by the common
alignment probability $q^{-4b}$ and by the number of injections gives
the required contribution from these assignments. The only eligible
noninjective assignments have an equality between a target token and a
generator token. There are at most
\[
b(4b-2)(q+1)^{5b-3}
\]
such assignments, by selecting one cross-equality and ignoring remaining
restrictions. For each eligible assignment the alignment probability is
still exactly $q^{-4b}$; use the trivial upper bound one for subsequent
bad geometry. Their total is absorbed by the claimed bound.
\end{proof}
\subsection{Summing over all selected pencils}
We now combine the selection estimate with the geometric estimates to
prove Proposition~\ref{prop:pencil-local}. 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 \eqref{eq:pencil-cylinder}. 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
\begin{equation}\label{eq:pencil-common-factor}
\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}.
\end{equation}
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~\ref{lem:pencil-small-reuse}. For $\kappa=2$,
Lemma~\ref{lem:pencil-two-reuses} 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~\ref{lem:pencil-reuse} 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~\ref{prop:pencil-local}: a violation of the local
condition occurs with probability $o(1)$, jointly with successful return
of the selection procedure.
==== END Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//local.tex ====
==== BEGIN Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//merge-split.tex ====
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[font=\small]
\node[anchor=east] at (-.2,1.1) {original class:};
\node[draw,rounded corners,minimum width=2.2cm] (ordinary) at (1.3,1.1)
{$q-4$ other lines};
\node[draw,rounded corners,minimum width=2.2cm] (merged) at (4.1,1.1)
{$M_g^0,\ M_g^1$};
\node[draw,rounded corners,minimum width=2.2cm] (split) at (6.9,1.1)
{$S_g^1,\ S_g^2$};
\node[anchor=east] at (-.2,0) {new blocks:};
\node[draw,rounded corners,minimum width=2.2cm] (ordinary2) at (1.3,0)
{$q-4$ blocks};
\node[draw,rounded corners,minimum width=2.2cm] (merged2) at (4.1,0)
{$1$ merged block};
\node[draw,rounded corners,minimum width=2.2cm] (split2) at (6.9,0)
{$4$ pair blocks};
\draw[-{Stealth}] (ordinary)--(ordinary2);
\draw[-{Stealth}] (merged)--(merged2);
\draw[-{Stealth}] (split)--(split2);
\end{tikzpicture}
\medskip
\begin{tikzpicture}[scale=.95,font=\small]
\draw[gray] (-.6,0)--(6.6,0) node[right] {$S$};
\foreach \i/\x in {0/0,1/2,2/4,3/6}{
\coordinate (u\i) at (\x,0);
\node[below=5pt] at (u\i) {$u_\i$};}
\draw (u0) to[bend right=45] node[below] {$d_1$} (u1);
\draw (u1) to[bend right=45] node[below] {$d_2$} (u2);
\draw (u2) to[bend right=45] node[below] {$d_3$} (u3);
\draw (u3) to[bend right=35] node[above] {$d_0$} (u0);
\foreach \i in {0,2}{\fill[blue!70!black] (u\i) circle (2.5pt);}
\foreach \i in {1,3}{\draw[red!75!black,thick,fill=white] (u\i) circle (2.5pt);}
\end{tikzpicture}
\caption{The merge and split operation gives $q+1$ blocks per direction.
Below, the four points on one split line form two opposite-pair blocks,
shown by filled and open points. An arc labelled $d_i$ means that its
endpoints lie on different constituents of the merged pair in direction
$d_i$, and hence share its block label. The arcs record this relation;
they are not affine lines. The diagram is schematic.}
\label{fig:cycle}
\end{figure}
==== END Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//merge-split.tex ====
==== BEGIN Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//paper.tex ====
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\input{glyphtounicode}
\input{glyphtounicode-cmex}
\pdfgentounicode=1
\pdftrailerid{}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools,mathrsfs}
\usepackage{microtype,enumitem,booktabs,array,longtable,needspace}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning}
\usepackage{xcolor}
\usepackage{xurl}
\usepackage{hyperref}
\hypersetup{colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,
urlcolor=blue!45!black,pdftitle={Balanced counterexamples to Ryser's conjecture at prime orders},pdfauthor={OpenAI}}
\urlstyle{same}
\setlength{\emergencystretch}{2em}
\setlist{itemsep=3pt,topsep=5pt}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\F}{\mathbb F}
\newcommand{\E}{\mathbb E}
\newcommand{\Prb}{\mathbb P}
\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\Cov}{Cov}
\title{Balanced counterexamples to Ryser's conjecture at prime orders}
\author{OpenAI}
\date{September 27, 2026}
\begin{document}
\maketitle
\begin{abstract}
For every sufficiently large prime $q$, we construct a finite intersecting
$(q+1)$-partite $(q+1)$-uniform hypergraph with covering number $q+1$
and exactly $q+1$ nonisolated vertices in each part. This disproves
Ryser's covering conjecture, even for intersecting hypergraphs with
equally sized parts.
\end{abstract}
\section{Introduction}
A vertex cover of a finite hypergraph $H$ is a set of vertices meeting
every edge. Its minimum possible size is the \emph{covering number}
$\tau(H)$. The \emph{matching number} $\nu(H)$ is the maximum number of
pairwise disjoint edges. For an integer $r\ge2$, an $r$-partite
$r$-uniform hypergraph has disjoint vertex parts $V_1,\ldots,V_r$, and
each edge contains exactly one vertex from each part. Here \emph{balance}
refers to equal sizes of the vertex parts. Ryser's covering conjecture
proposes that every such hypergraph satisfies
\begin{equation}\label{eq:ryser}
\tau(H)\le (r-1)\nu(H).
\end{equation}
A hypergraph with at least one edge is \emph{intersecting} if every two
distinct edges meet. In this case $\nu(H)=1$, and the proposed bound is $r-1$.
A cover may use vertices from any of the parts, so making each individual
part large does not by itself obstruct a small cover.
For $r=2$, inequality~\eqref{eq:ryser} is K\H{o}nig's matching theorem
for bipartite graphs. Henderson's 1971 thesis contains an equivalent
formulation of the general conjecture~\cite{Henderson1971}; Best and
Wanless~\cite{BestWanless2018} discuss its attribution to Ryser and
separate it from his Latin-square transversal conjecture.
Aharoni proved the full tripartite case~\cite{Aharoni2001}.
In the intersecting case, Gy\'arf\'as proved the conjecture through rank
four and Tuza proved rank five; see
Kir\'aly and T\'othm\'er\'esz~\cite{KiralyTothmeresz2017} for the
historical account. For \emph{linear} intersecting hypergraphs, in which
every two distinct edges meet in exactly one vertex, Franceti\'c, Herke,
McKay, and Wanless established the conjecture through rank
nine~\cite{FranceticHerkeMcKayWanless2017}.
For each of $r=4,5$, Haxell and Scott proved a bound
$\tau(H)\le(r-\varepsilon_r)\nu(H)$ with a positive constant
$\varepsilon_r$~\cite{HaxellScott2012}. More recently, White proved
$\tau(H)\le6$ for four-partite four-uniform hypergraphs with
$\nu(H)=2$~\cite{White2026}.
These results concern the covering inequality itself. Lov\'asz proposed
the stronger assertion that, in every $r$-partite $r$-uniform hypergraph
with at least one edge, deleting $r-1$ vertices can reduce the matching number.
Clow, Haxell, and Mohar disproved that assertion at
$r=3$~\cite{ClowHaxellMohar2025}; Abiad, Garbe, Povill, and Spiegel
subsequently gave an infinite family at $r=3$ and examples at
$r=4$~\cite{AbiadGarbePovillSpiegel2025}. Those examples do not
contradict~\eqref{eq:ryser}.
Finite planes explain why the bound $r-1$ is natural. In the affine plane
$\F_q^2$, make one part for each of the $q+1$ directions, with one vertex
for each line of that direction. An affine point determines an edge
consisting of the labels of the lines through it. Two such edges meet at
the label of their joining line. Each parallel class is a cover of size
$q$, and fewer than $q$ lines cannot cover $q^2$ points. Thus this
hypergraph is intersecting and has covering number $q$. It is the usual
truncated-projective-plane example, expressed through affine duality.
Abu-Khazneh, Bar\'at, Pokrovskiy, and Szab\'o exploit the rigidity of
minimum covers in a truncated plane and add a new part and exceptional
edges. For every prime power $q\ge3$, their construction yields an
intersecting $(q+2)$-partite $(q+2)$-uniform hypergraph with covering
number $q+1$~\cite[Theorem~1.2, Lemma~1.3, Corollary~1.4]{AbuKhaznehBaratPokrovskiySzabo2019}.
Haxell and Scott use affine planes to construct intersecting $r$-partite
$r$-uniform hypergraphs with covering number at least $r-4$ for every
sufficiently large $r$, and at least $r-3$ when $r$ is
even~\cite[Theorem~6]{HaxellScott2017}.
Equal part sizes alone do not force a large covering number:
Franceti\'c, Herke, McKay, and Wanless constructed a linear intersecting
13-partite hypergraph with 13 nonisolated vertices in each part, and
reported that its covering number is nine by
computation~\cite[Section~3.1]{FranceticHerkeMcKayWanless2017}.
Here we modify the affine-plane example while keeping $q+1$ parts, one
for each direction. The modification raises both the covering number and
each part size to $q+1$.
\begin{theorem}\label{thm:main}
There exists $q_0$ such that, for every prime $q\ge q_0$, there is a
finite intersecting $(q+1)$-partite $(q+1)$-uniform hypergraph $H$ with
\[
|V_1|=\cdots=|V_{q+1}|=q+1,
\qquad \tau(H)=q+1.
\]
Every vertex belongs to an edge.
\end{theorem}
Since $\nu(H)=1$, this gives counterexamples to~\eqref{eq:ryser}.
The value $\tau(H)=r$, where $r=q+1$, is the largest possible for an
intersecting $r$-uniform hypergraph, since any edge is a cover. The
nonisolated vertices in each part also form a cover, so a hypergraph with
$\tau(H)=r$ must have at least $r$ such vertices in every part. Our
construction attains this minimum simultaneously in all parts.
The argument produces an example for each prime beyond one fixed
threshold; that threshold is not numerical.
The companion article~\cite[Theorem~1.1]{OpenAIExtension2026} treats a different
range of field orders: for every sufficiently large prime $s\equiv2
\pmod3$, it gives counterexamples of order $q=s^n$ for every sufficiently
large odd $n$, with the threshold for $n$ depending on $s$. Its theorem
does not assert balance. The proof here is independent of that
construction.
\subsection{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\'arf\'as's tree-cover conjecture asks for at most $r-1$ such trees
in every $r$-edge-colored complete graph
\cite[Conjecture~1]{Milicevic2017}. Erd\H{o}s, Gy\'arf\'as, and Pyber
record the equivalence of this covering formulation with the
intersecting case of Ryser's conjecture
\cite[Section~3, after Theorem~2]{ErdosGyarfasPyber1991}. The standard
transfer gives the following consequence of Theorem~\ref{thm:main}.
\begin{corollary}\label{cor:tree-cover}
For every sufficiently large prime $q$, there is a finite complete
graph with a $(q+1)$-edge-coloring whose vertices require exactly
$q+1$ monochromatic trees to cover. The same minimum holds for
connected monochromatic subgraphs.
\end{corollary}
\begin{proof}
Put $r=q+1$ and take the hypergraph $H$ from Theorem~\ref{thm:main}.
Use its edges as the vertices of a complete graph. Color a pair
$ef$ by any index $i$ for which $e$ and $f$ have the same vertex in
part $V_i$; intersection guarantees such an index. Along a path of
color $i$, this vertex of $V_i$ is constant. Thus each connected
monochromatic subgraph corresponds to a hypergraph vertex lying in all
the hyperedges represented by its vertices; for a singleton choose any
vertex of the corresponding hyperedge.
A cover by $t$ such subgraphs would give a vertex cover of $H$ of
size at most $t$, so $t\ge\tau(H)=r$. Conversely, the $r$
monochromatic stars centered at any fixed graph vertex cover the
complete graph, allowing singleton stars for unused colors.
\end{proof}
\subsection{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~\ref{fig:cycle} shows the rule;
Section~\ref{sec:deterministic-construction} 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 \emph{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 \emph{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~\ref{sec:deterministic-construction} makes these requirements
explicit before we construct data satisfying them.
\subsection{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 \emph{independent transversal} of this graph.
Section~\ref{sec:candidates} bounds the sizes and degrees of this graph,
including the exceptional pairs that can have large common neighborhoods.
Section~\ref{sec:selection} 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~\cite[Section~4]{LohSudakov2007}.
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~\ref{sec:deletion} 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\H{o}s and Lov\'asz~\cite[Section~4]{ErdosLovasz1975};
Kahn subsequently developed the random-line approach
further~\cite{Kahn1992}. 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\H{o}nyi and
Weiner~\cite{SzonyiWeiner2012}, also stated by H\'eger and
Nagy~\cite{HegerNagy2017}, to turn an almost-cover into a large pencil.
This is the step that requires $q$ to be prime.
Finally, Section~\ref{sec:pencils} 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~\ref{sec:assembly} intersects the resulting
successful events and applies the deterministic construction.
Appendix~\ref{sec:elementary} supplies three elementary estimates in a
form independent of the construction; these are also the precise inputs
used by the companion article.
\paragraph{Conventions.}
All logarithms are natural. An event holds with high probability if its
probability tends to one along the orders under discussion. Constants
in $O(\cdot)$ may depend on parameters fixed before $q$ varies. Every
auxiliary constant is fixed independently of $q$; the final threshold
may depend on those constants.
\input{construction}
\input{deletion}
\input{candidates}
\input{selection}
\input{local}
\section{Completion of the construction}\label{sec:assembly}
We now put the three probability estimates on the same experiment. The
candidate graph and selection procedure give compatible tuples and line
occupancy; deletion domination gives the core-cover condition; the local
incidence estimate gives the last condition of
Proposition~\ref{prop:deterministic-reduction}.
\begin{proof}[Proof of Theorem~\ref{thm:main}]
Fix the candidate constants $c_*,C_*$ from
Proposition~\ref{prop:candidate-graph}, set $c_0=1/5$, and fix all the
selection constants in the order given in
\eqref{sel:constants-one}--\eqref{sel:constants-three}. In particular,
$K_*$ and $\rho>0$ do not depend on $q$.
Choose independent constituent offsets as in
Section~\ref{sec:candidates}. By Proposition~\ref{prop:candidate-graph},
the event that all its bounds hold and every constituent pair is distinct
has probability $e^{-1}+o(1)$. Return failure outside that event.
For an outcome in it, apply Proposition~\ref{sel:selection} to the two
slots for each direction. All its graph hypotheses hold with the fixed
constants $c_*,C_*,c_0=1/5$. Its independent transversal is exactly a
compatible collection of valid tuples. The probability of returning
such a collection, denoted by $\mathcal A$, is bounded below by a
positive constant, uniformly for all sufficiently large $q$.
Section~\ref{sec:selection-application} verifies that
\eqref{sel:occupancy-conclusion} supplies the $R_0$ and $R$ line-occupancy
bounds in Proposition~\ref{prop:deterministic-reduction}. Thus those
bounds fail jointly with $\mathcal A$ with probability $o(1)$. The
constituent multiplicity bound is already included in the initial event.
By Corollary~\ref{sel:deletion-domination}, the law of the three deletion
lines per direction, conditional on $\mathcal A$, is bounded pointwise
by $\exp(K_0q)$ times the uniform law for a fixed constant $K_0$.
Apply Corollary~\ref{cor:core-pencil} with $k=3$ and
$\zeta=\rho/4$. For prime $q$, concentration of all possible core
covers therefore fails with conditional probability $o(1)$, and hence
also with joint probability $o(1)$.
Finally, the uniform conditional cylinder bound for selection is
\eqref{sel:conditional-offset-cylinder}. It applies even to prescriptions
that are not available in a given candidate graph, whose probability is
zero. Together with compatibility and the constituent multiplicity cap,
it supplies all hypotheses of Proposition~\ref{prop:pencil-local}.
The local condition thus fails jointly with $\mathcal A$ with probability
$o(1)$.
Subtracting these three failure probabilities from $\Prb(\mathcal A)$
leaves positive probability for all sufficiently large primes.
The constants do not depend on the prime. Increase the threshold so that
$q\ge4$ and $\rho q>2(1+\lceil\log q\rceil)$.
The resulting finite configuration satisfies every hypothesis of
Proposition~\ref{prop:deterministic-reduction}, with
$B=\lceil\log q\rceil$. That proposition gives the asserted hypergraph,
including exactly $q+1$ nonisolated vertices in each part and
$\tau(H)=q+1$.
\end{proof}
\appendix
\input{elementary}
\bibliographystyle{plain}
\bibliography{references}
\end{document}
==== END Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//paper.tex ====
==== BEGIN Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//selection.tex ====
\section{Selecting split lines}\label{sec:selection}
The candidate graph supplies many choices in each slot; we must now
choose one vertex from every slot without creating a conflict. We need
two further properties of this choice. First, an event prescribing the
chosen vertices in several slots must have small probability. Such an
event is called a \emph{cylinder}, and its bound will allow us to count
exceptional pencil configurations. Second, the chosen split lines must
leave a positive proportion of the initially available points on every
affine line.
We prove these properties together in a graph statement whose bounds are
uniform over all inputs satisfying the hypotheses. The cylinder bound
includes the event that the procedure succeeds; we do not condition the
individual choices on eventual success.
\begin{proposition}[Selection with bounded cylinder probabilities]
\label{sel:selection}
Fix constants $c_*,C_*>0$ and $00$, depending only on $c_*,C_*,c_0$,
and a random procedure which either fails or returns an independent
transversal $(V_i)_{i\in I_0}$, where $I_0$ is the set of slots and
$V_i\in Q_i$. If $\mathcal A$ denotes its event of returning a
transversal, then
\begin{equation}\label{sel:success}
\Prb(\mathcal A)=1-o(1).
\end{equation}
For any $s$ distinct slots $i_1,\ldots,i_s$ and any prescribed vertices
$v_j\in Q_{i_j}$,
\begin{equation}\label{sel:cylinder}
\Prb\bigl(\mathcal A, V_{i_j}=v_j\ (1\le j\le s)\bigr)
\le (K_*/q)^s.
\end{equation}
Suppose also that the slots are indexed by $(g,k)$, with two slots for
each direction $g$ of an affine plane of order $q$. Associate to each
vertex in slot $(g,k)$ a line of direction $g$, injectively within
that slot. For every affine line $\ell$, let $T_\ell\subseteq\ell$
be a fixed set of at least $c_0q$ points. From $T_\ell$ remove every
point on a selected line different from $\ell$, and call the remaining
set $T_\ell^{\rm fin}$. Then the same procedure satisfies
\begin{equation}\label{sel:occupancy-conclusion}
\Prb\bigl(\mathcal A, \min_\ell |T_\ell^{\rm fin}|<\rho q\bigr)
=o(1).
\end{equation}
The errors in \eqref{sel:success} and
\eqref{sel:occupancy-conclusion} are uniform in all the stated input
data. By the injectivity within a slot, \eqref{sel:cylinder} also
holds for prescribed candidate lines.
\end{proposition}
The selection has two stages. In the main stage we repeatedly choose a
slot and a vertex, delete conflicts, and thin the remaining choices so
that every vertex has the same survival probability. Domain sizes then
decrease at a common rate. Remaining degrees decrease faster, because
the chosen slot also disappears. We show that this difference leaves a
sparse enough graph to complete the last slots by the local lemma.
Partial random selection followed by local-lemma completion also appears
in Loh and Sudakov~\cite[Section~4]{LohSudakov2007}. Here we additionally
track occupancy on each affine line and prove a cylinder bound for the
complete returned transversal.
The main technical issue is concentration of the remaining degrees.
A choice in $J(v)$ can delete many neighbors of $v$, but it also kills
$v$ or removes its slot. We will use this implication to stop tracking
$v$ after such a choice, without losing any degree estimate needed for
a subsequent step.
\subsection{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_*),\label{sel:constants-one}\\
B_*&=2/(s_{\min}c_*),&
\rho&=c_0\exp(-6B_*)/4,\label{sel:constants-two}\\
0\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
\begin{equation}\label{sel:thinning-rate}
\lambda_u=\frac{\alpha-r_u(t)}{1-r_u(t)}.
\end{equation}
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:
\begin{equation}\label{sel:equal-survival}
(1-r_u(t))(1-\lambda_u)=1-\alpha.
\end{equation}
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$,
\begin{equation}\label{sel:bernoulli-tail}
\Prb(Z\ge k)\le \E\binom Zk\le\mu_*^k/k!
\le(e\mu_*/k)^k.
\end{equation}
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)$.
\subsection{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~\ref{lem:bounded-drift-concentration},
the appendix form of the Azuma--Hoeffding estimate~\cite{Azuma1967}.
For an adapted process $X_t$ with $|X_{t+1}-X_t|\le L$ for
$0\le t0$ such that
\begin{equation}\label{sel:unconditional-success}
\Prb(\mathcal A)\ge a_0
\end{equation}
for all sufficiently large $q$. For every fixed offset outcome $M$,
\begin{equation}\label{sel:conditional-offset-cylinder}
\Prb(\mathcal A,\hbox{ prescribed choices in }s\hbox{ slots}\mid M)
\le(K_*/q)^s.
\end{equation}
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.
\begin{corollary}[Domination of the deletion-line law]
\label{sel:deletion-domination}
Let $D$ consist of the selected split lines and the lines $M_g^1$
in the preceding experiment. Conditional on $\mathcal A$, the law
of $D$ is dominated pointwise by $\exp(O(q))$ times the uniform
law on sets containing three distinct lines in each direction.
\end{corollary}
\begin{proof}
Fix such an unordered deletion set $D_0$. For each direction there
are six assignments of its three lines to $M_g^1$, split slot 1,
and split slot 2. For a fixed assignment in all directions, the
initial probability of the prescribed $M_g^1$ values is
$q^{-(q+1)}$. Conditional on the full offset data, the probability
of all prescribed split lines jointly with $\mathcal A$ is at most
$(K_*/q)^{2(q+1)}$, by
\eqref{sel:conditional-offset-cylinder}. Averaging over the
unconstrained offsets $M_g^0$ and summing over all role assignments
gives
\[
\Prb(\mathcal A,D=D_0)
\le\left(\frac{6K_*^2}{q^3}\right)^{q+1}.
\]
The uniform law $U$ assigns $D_0$ probability
$\binom q3^{-(q+1)}$. Dividing also by
\eqref{sel:unconditional-success}, we obtain
\begin{equation}\label{sel:deletion-ratio}
\frac{\Prb(D=D_0\mid\mathcal A)}{U(D_0)}
\le a_0^{-1}\left[K_*^2(1-1/q)(1-2/q)\right]^{q+1}
\le a_0^{-1}K_*^{2(q+1)}=\exp(O(q)).
\end{equation}
All probabilities before this final conditioning use the original
independent offset law; the event $\mathcal A$ enforces the candidate
graph conditions and constituent distinctness.
\end{proof}
==== END Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//selection.tex ====
==== BEGIN Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//references.bib ====
@phdthesis{Henderson1971,
author = {Henderson, John Robert},
title = {Permutation Decompositions of $(0,1)$-Matrices and Decomposition Transversals},
school = {California Institute of Technology},
year = {1971},
doi = {10.7907/J1Z1-SK19},
url = {https://thesis.caltech.edu/5726/}
}
@article{Aharoni2001,
author = {Aharoni, Ron},
title = {{Ryser}'s Conjecture for Tripartite 3-Graphs},
journal = {Combinatorica},
volume = {21},
number = {1},
pages = {1--4},
year = {2001},
doi = {10.1007/s004930170001}
}
@article{Tuza1983,
author = {Tuza, Zsolt},
title = {{Ryser}'s conjecture on transversals of $r$-partite hypergraphs},
journal = {Ars Combinatoria},
volume = {16-B},
pages = {201--209},
year = {1983},
url = {https://combinatorialpress.com/ars/vol16b/}
}
@article{FranceticHerkeMcKayWanless2017,
author = {Franceti{\'c}, Nevena and Herke, Sarada and McKay, Brendan D. and Wanless, Ian M.},
title = {On {Ryser}'s conjecture for linear intersecting multipartite hypergraphs},
journal = {European Journal of Combinatorics},
volume = {61},
pages = {91--105},
year = {2017},
doi = {10.1016/j.ejc.2016.10.004},
eprint = {1508.00951},
archivePrefix = {arXiv},
primaryClass = {math.CO}
}
@article{SzonyiWeiner2012,
author = {Sz{\H o}nyi, Tam{\'a}s and Weiner, Zsuzsa},
title = {A stability theorem for lines in {Galois} planes of prime order},
journal = {Designs, Codes and Cryptography},
volume = {62},
number = {1},
pages = {103--108},
year = {2012},
doi = {10.1007/s10623-011-9495-z}
}
@article{HegerNagy2017,
author = {H{\'e}ger, Tam{\'a}s and Nagy, Zolt{\'a}n L{\'o}r{\'a}nt},
title = {Dominating sets in projective planes},
journal = {Journal of Combinatorial Designs},
volume = {25},
number = {7},
pages = {293--309},
year = {2017},
doi = {10.1002/jcd.21527},
eprint = {1603.02933},
archivePrefix = {arXiv},
primaryClass = {math.CO}
}
@article{Azuma1967,
author = {Azuma, Kazuoki},
title = {Weighted sums of certain dependent random variables},
journal = {T\^ohoku Mathematical Journal, Second Series},
volume = {19},
number = {3},
pages = {357--367},
year = {1967},
doi = {10.2748/tmj/1178243286}
}
@incollection{ErdosLovasz1975,
author = {Erd{\H o}s, Paul and Lov{\'a}sz, L{\'a}szl{\'o}},
title = {Problems and results on 3-chromatic hypergraphs and some related questions},
booktitle = {Infinite and Finite Sets},
editor = {Hajnal, Andr{\'a}s and Rado, Richard and S{\'o}s, Vera T.},
series = {Colloquia Mathematica Societatis J{\'a}nos Bolyai},
volume = {10},
pages = {609--627},
publisher = {North-Holland},
address = {Amsterdam},
year = {1975},
url = {https://www.renyi.hu/~p_erdos/1975-34.pdf}
}
@article{LohSudakov2007,
author = {Loh, Po-Shen and Sudakov, Benny},
title = {Independent transversals in locally sparse graphs},
journal = {Journal of Combinatorial Theory, Series B},
volume = {97},
number = {6},
pages = {904--918},
year = {2007},
doi = {10.1016/j.jctb.2007.02.003},
eprint = {0706.2124},
archivePrefix = {arXiv},
primaryClass = {math.CO}
}
@article{ClowHaxellMohar2025,
author = {Clow, Alexander and Haxell, Penny and Mohar, Bojan},
title = {A Counterexample to a Conjecture of {Lov{\'a}sz}},
journal = {Combinatorica},
volume = {46},
pages = {26},
year = {2026},
doi = {10.1007/s00493-026-00220-3},
note = {Article 26},
eprint = {2505.05339},
archivePrefix = {arXiv},
primaryClass = {math.CO},
url = {https://link.springer.com/article/10.1007/s00493-026-00220-3}
}
@misc{AbiadGarbePovillSpiegel2025,
author = {Abiad, Aida and Garbe, Frederik and Povill, Xavier and Spiegel, Christoph},
title = {Infinitely many counterexamples to a conjecture of {Lov{\'a}sz}},
year = {2025},
eprint = {2506.21286},
archivePrefix = {arXiv},
primaryClass = {math.CO},
note = {Version 2, 14 July 2025},
howpublished = {\href{https://arxiv.org/abs/2506.21286v2}{arXiv:2506.21286v2}},
url = {https://arxiv.org/abs/2506.21286v2}
}
@misc{BestWanless2018,
howpublished = {\href{https://arxiv.org/abs/1801.02893}{arXiv:1801.02893}},
author = {Best, Darcy and Wanless, Ian M.},
title = {What did {Ryser} Conjecture?},
year = {2018},
eprint = {1801.02893},
archivePrefix = {arXiv},
primaryClass = {math.CO},
url = {https://arxiv.org/abs/1801.02893}
}
@article{KiralyTothmeresz2017,
author = {Kir{\'a}ly, Zolt{\'a}n and T{\'o}thm{\'e}r{\'e}sz, Lilla},
title = {On {Ryser}'s Conjecture for $t$-Intersecting and Degree-Bounded Hypergraphs},
journal = {The Electronic Journal of Combinatorics},
volume = {24},
number = {4},
pages = {P4.40},
year = {2017},
doi = {10.37236/6448},
eprint = {1705.10024},
archivePrefix = {arXiv},
primaryClass = {math.CO}
}
@article{AbuKhaznehBaratPokrovskiySzabo2019,
author = {Abu-Khazneh, Ahmad and Bar{\'a}t, J{\'a}nos and Pokrovskiy, Alexey and Szab{\'o}, Tibor},
title = {A family of extremal hypergraphs for {Ryser}'s conjecture},
journal = {Journal of Combinatorial Theory, Series A},
volume = {161},
pages = {164--177},
year = {2019},
doi = {10.1016/j.jcta.2018.07.011},
eprint = {1605.06361},
archivePrefix = {arXiv},
primaryClass = {math.CO}
}
@article{Kahn1992,
author = {Kahn, Jeff},
title = {On a problem of {Erd{\H o}s} and {Lov{\'a}sz}: Random lines in a projective plane},
journal = {Combinatorica},
volume = {12},
number = {4},
pages = {417--423},
year = {1992},
doi = {10.1007/BF01305234}
}
@misc{OpenAIExtension2026,
author = {{OpenAI}},
title = {{A counterexample to Ryser's covering conjecture}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/A-Counterexample-to-Rysers-Covering-Conjecture-September-23-2026/paper.pdf}{OAI:A-Counterexample-to-Rysers-Covering-Conjecture-September-23-2026}},
year = {2026}
}
@misc{White2026,
author = {White, Patrick},
title = {{Tuza}'s {Ryser}-conjecture claim for four-partite hypergraphs with matching number two},
year = {2026},
eprint = {2609.14281},
archivePrefix = {arXiv},
primaryClass = {math.CO},
note = {Version 1, 13 September 2026},
howpublished = {\href{https://arxiv.org/abs/2609.14281v1}{arXiv:2609.14281v1}},
url = {https://arxiv.org/abs/2609.14281v1}
}
@article{HaxellScott2012,
author = {Haxell, P. E. and Scott, A. D.},
title = {On {Ryser}'s conjecture},
journal = {The Electronic Journal of Combinatorics},
volume = {19},
number = {1},
pages = {P23},
year = {2012},
doi = {10.37236/1175},
note = {\href{https://doi.org/10.37236/1175}{doi:10.37236/1175}}
}
@article{ErdosGyarfasPyber1991,
author = {Erd{\H o}s, Paul and Gy{\'a}rf{\'a}s, Andr{\'a}s and Pyber, L{\'a}szl{\'o}},
title = {Vertex coverings by monochromatic cycles and trees},
journal = {Journal of Combinatorial Theory, Series B},
volume = {51},
number = {1},
pages = {90--95},
year = {1991},
doi = {10.1016/0095-8956(91)90007-7}
}
@article{HaxellScott2017,
author = {Haxell, P. E. and Scott, A. D.},
title = {A note on intersecting hypergraphs with large cover number},
journal = {The Electronic Journal of Combinatorics},
volume = {24},
number = {3},
pages = {P3.26},
year = {2017},
doi = {10.37236/6460},
eprint = {1609.05458},
archivePrefix = {arXiv},
primaryClass = {math.CO}
}
@misc{Milicevic2017,
author = {Mili{\'c}evi{\'c}, Luka},
title = {Covering complete graphs by monochromatically bounded sets},
year = {2017},
eprint = {1705.09370},
archivePrefix = {arXiv},
primaryClass = {math.CO},
note = {Version 1, 25 May 2017},
howpublished = {Preprint, \href{https://arxiv.org/abs/1705.09370v1}{arXiv:1705.09370v1}},
url = {https://arxiv.org/abs/1705.09370v1}
}
==== END Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders//references.bib ====