Compatible translates from independent pools
ProvedOAI.RyserCoveringCounterexample.Selection.compatible_selection_uniform_oddExtFor every positive integer there is an integer such that for every there is a threshold with the following property. Let be a finite field with and let . For let and let be a set of directions with , and assume each direction belongs to for at most indices . For distinct , translates and conflict if there are , and with
Draw independent uniform shifts for each , independently for all indices. Then with probability at least there is a choice of indices for which the translates have no conflicts.
This is Theorem 4.1 of the paper, proved through an independent-transversal argument in the tradition of Haxell. It separates the independent random choices needed by the deletion estimates from the geometric compatibility needed for exceptional edges to intersect.
import Mathlib import Definitions.Def_RyserOddSupport namespace OAI universe u namespace RyserCoveringCounterexample.Selection
theorem compatible_selection_uniform_oddExt (D : ℕ) (hD : 1 ≤ D) :
∃ K : ℕ, 6 ≤ K ∧
∀ ε : ℝ, 0 < ε → ∃ Q : ℕ,
∀ (F : Type u) [Field F] [Fintype F] [DecidableEq F]
(n : ℕ) (data : Data F n),
Bounded D data → Q ≤ Fintype.card F →
1 - ε ≤ (poolLaw F n K).prob
(fun pool => HasCompatibleChoice data pool) := by
sorry
end RyserCoveringCounterexample.Selection
end OAI