Lemma 14 — Coexistence is exactly the chain-union bound
ProvedBuchiRabinIndex.LowerBound.Supplement.lemma_14automata-theorygraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let be distinct names in . Then
This characterizes the conflict relation used in the minimum-flag problem. Both directions and all positive sizes are retained.
Differences from the source:
- encoding: positive integer node words, finite chains and the n-full tree → published List Nat names with positivity, Finset chains and explicit fullTree n; reason: the existing published representation preserves each source name, chain and coexistence edge
Preamble
import Definitions.Def_BuchiRabinIndex_LowerBound_Supplement_Flags set_option autoImplicit false
Formal statement
namespace BuchiRabinIndex.LowerBound.Supplement
/-- STOC 2027 submission #1731, lemma 14. Statement only. -/
theorem lemma_14 (n : ℕ) (hn : 1 ≤ n) (x y : Node)
(hx : x ∈ fullTree n) (hy : y ∈ fullTree n) (hne : x ≠ y) :
(∃ T : Finset Node, Ordered T ∧ T.card ≤ n ∧ x ∈ T ∧ y ∈ T) ↔
(chain x ∪ chain y).card ≤ n := by sorry
end BuchiRabinIndex.LowerBound.Supplement
Source
Cong Tian, Runzhe Ma, Wensheng Wang, Zhenhua Duan, Büchi Determinization with Optimal States and Square Root Index Improvement, STOC 2027 submission #1731 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1731.pdf, Lemma 14, p. 11