bipartite_subset_graph
For integers k ≥ 2 and r ≥ 0, G(k,r) is the bipartite graph on two disjoint copies of the family of k-element subsets of {1, ..., 2k-1}, where two vertices a_S and b_T are adjacent if and only if |S ∩ T| ≤ r.
Statement
def bipartite_subset_graph (k r : ℕ) :
SimpleGraph ({S : Finset (Fin (2 * k - 1)) // S.card = k} ⊕ {T : Finset (Fin (2 * k - 1)) // T.card = k})- Defined in
- arXiv:2610.42094, Definition 1.2
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Used by 6
- bipartite_subset_colorable_iff_below_thresholdFor positive k, the standard lists are colorable at threshold r exactly when r is less than the least uncolorable threshold.
- bipartite_subset_colorable_at_oneFor every k at least two, the bipartite subset graph with intersection threshold one is colorable from its standard lists.
- bipartite_subset_uncolorable_of_geFor integers k ≥ 1 and r with k ≤ r, the bipartite subset graph bipartite_subset_graph k r has no proper coloring from its standard lists,…
- bipartite_subset_colorable_succFor every positive k and threshold r, colorability of the standard-list subset graph at k implies colorability at k+1 and the same…
- bipartite_subset_standard_list_colorableFor integers k and r, bipartite_subset_standard_list_colorable k r asserts that the bipartite subset graph bipartite_subset_graph k r…
- bipartite_subset_colorable_five_at_twoThe standard lists color the bipartite subset graph at k = 5 and intersection threshold 2.
Read back from the Lean
bipartite_subset_graph k r is the simple graph whose vertices are the disjoint union of two copies of {S : Finset (Fin (2 * k - 1)) // S.card = k} (the $k$-element subsets of Fin (2 * k - 1)). An edge exists between a vertex Sum.inl S in the first copy and a vertex Sum.inr T in the second copy if and only if the cardinality of their intersection is at most r ((S.1 ∩ T.1).card ≤ r). There are no edges between two vertices belonging to the same copy.
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
/-- The bipartite subset graph G(k,r) whose two vertex classes are copies of the k-subsets of 2k-1, adjacent when their intersection has size at most r. -/ def bipartite_subset_graph (k r : ℕ) : SimpleGraph ({S : Finset (Fin (2 * k - 1)) // S.card = k} ⊕ {T : Finset (Fin (2 * k - 1)) // T.card = k}) := { Adj := fun | Sum.inl S, Sum.inr T => (S.1 ∩ T.1).card ≤ r | Sum.inr T, Sum.inl S => (S.1 ∩ T.1).card ≤ r | _, _ => False symm := ⟨by intro u v h cases u <;> cases v <;> simp at h ⊢ <;> exact h⟩ loopless := ⟨by intro u cases u <;> simp⟩ }