Lemma 5.4 — Fixing every other group, more than 2∆ light vertices in one configuration forces a bad pair in another configuration of that group.
OpenGreedyColoringLCA969.LowerBound.Supplement.lemma_5_4graph-theorylocal-computationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Fix integers , , , a deterministic standard-oracle algorithm with fixed tape, a group , and all the other groups' configurations in the hard construction of §5.1. Let and . If some configuration of group has strictly more than light vertices, then some configuration of that group has a bad pair:
Every other group's ordered adjacency lists remain fixed. Lightness and return labels come from the actual executions; queries into other groups are allowed. The conclusion provides the obstruction used in the MIS lower bound, including the zero-query lightness regime.
Differences from the source:
- encoding: vertices 1 through n and L-valued answers in the standard adjacency-list model → Fin n identifiers and injective positive-integer return codes, with success and cost derived from the immutable shared-tape execution; reason: shifting identifiers and coding labels preserves every graph, list order, question and graph-query count
- encoding: independently configurable groups and a pair in one biclique → HardInput is a subtype of represented graphs; SameOutside fixes all other lists, and adjacency/equal neighbor sets recognize opposite/same sides; reason: decomposition witnesses are not sampled or stored; for Delta>=3 this recognition is exactly biclique membership
- generalization: LCAs return Boolean labels → arbitrary positive return codes and possible nontermination; invalid codes and nontermination fail global MIS success; reason: the published machine includes all source LCAs; for Theorem 5.6 and Lemma 5.7 invalid codes can be normalized to a Boolean label without graph queries or reducing success, while the rewiring proof of Lemma 5.4 uses only equality of returned codes; infinite executions are never light
Preamble
import Definitions.Def_GreedyColoringLCA969_LowerBound_Supplement_HardInputs open scoped ENNReal BigOperators open MeasureTheory Classical set_option autoImplicit false
Formal statement
namespace GreedyColoringLCA969.LowerBound.Supplement
theorem lemma_5_4 (Δ lam τ : ℕ) (hΔ : 3 ≤ Δ) (hlam : 2 ≤ lam) (hτ : 1 ≤ τ)
(B : DeterministicLCA .standard) (i : Fin τ) (R : HardInput Δ lam τ)
(hmany : 2 * Δ < groupLightCount B R.val Δ lam i.val) :
∃ S : HardInput Δ lam τ, SameOutside R.val S.val Δ lam i.val ∧
∃ v w : Fin (hardSize Δ lam τ), v.val / groupSize Δ lam = i.val ∧
w.val / groupSize Δ lam = i.val ∧ BadPair B S.val Δ v w := by sorry
end GreedyColoringLCA969.LowerBound.Supplement
Source
Zi Song Yeoh, Krzysztof Onak, Dragos-Florian Ristache, STOC 2027 submission #969 (October 2026), p. 28 (PDF 29), Lemma 5.4