Theorem 37 — clique number
ProvedBuchiRabinIndex.LowerBound.theorem_37automata-theoryfinite-combinatoricsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1rabin-index
The coexistence graph has clique number
Moreover, for every and ,
The final clause retains the domain of from Definition 34. Exponents are integers under the indicated parity conditions. This supplies the explicit values appearing again in the goal.
Differences from the source:
- encoding: nodes are finite words of positive integers → List Nat with positivity in node and tree predicates; reason: children retain the source’s indices starting at 1
- encoding: the unique n-full ordered tree of Definition 12 → the explicitly enumerated positive words of weight at most n−1; reason: this is the same finite tree; no size is fixed
Preamble
import Definitions.Def_BuchiRabinIndex_LowerBound_Nodes set_option autoImplicit false
Formal statement
namespace BuchiRabinIndex.LowerBound
/-- STOC 2027 submission #1731, theorem 37; statement only. -/
theorem theorem_37 :
omega 1 = 1 ∧
(∀ n, 2 ≤ n →
(Even n → omega n = 2 ^ (n / 2)) ∧
(Odd n → omega n = 3 * 2 ^ ((n - 3) / 2))) ∧
(∀ n c, 1 ≤ n → n / 2 < c → c ≤ n - 1 → g n c = omega n) := by sorry
end BuchiRabinIndex.LowerBound
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), Theorem 37, p. 27; https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1731.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.