has_three_by_three_grid
For a hypergraph with edge set H : Set (Finset V) of finite subsets of V, H contains a 3x3 grid if there exist families R, C : Fin 3 → Finset V of edges in H such that R is pairwise disjoint, C is pairwise disjoint, and ¬ Disjoint (R i) (C j) for all i, j : Fin 3.
Statement
def has_three_by_three_grid {V : Type*} (H : Set (Finset V)) : Prop
- Defined in
- arXiv:2611.05261 Section 1 and Section 3
- Verified
- 05 Nov 2026
- Axioms
- none listed
Read back from the Lean
Given a type V and a family of finite subsets H : Set (Finset V), has_three_by_three_grid H asserts that there exist two sequences of three finite subsets of V, R : Fin 3 → Finset V (the rows) and C : Fin 3 → Finset V (the columns), such that:
1. For every i : Fin 3, R i ∈ H;
2. For every j : Fin 3, C j ∈ H;
3. For all i, i' : Fin 3, if i ≠ i', then R i and R i' are disjoint;
4. For all j, j' : Fin 3, if j ≠ j', then C j and C j' are disjoint;
5. For all i, j : Fin 3, R i and C j are not disjoint (i.e., they have non-empty intersection).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Predicate that a hypergraph of finite edges contains a 3x3 grid of edges. -/ def has_three_by_three_grid {V : Type*} (H : Set (Finset V)) : Prop := ∃ (R C : Fin 3 → Finset V), (∀ i, R i ∈ H) ∧ (∀ j, C j ∈ H) ∧ (∀ i i', i ≠ i' → Disjoint (R i) (R i')) ∧ (∀ j j', j ≠ j' → Disjoint (C j) (C j')) ∧ (∀ i j, ¬ Disjoint (R i) (C j))