spectral_extremal_clique_num_le_chromatic_number
For every natural number k and real number r, the extremal distance-k clique number spectral_extremal_clique_num k r is less than or equal to the extremal distance-k chromatic number spectral_extremal_chromatic_number k r.
Statement
theorem spectral_extremal_clique_num_le_chromatic_number (k : ℕ) (r : ℝ) :
spectral_extremal_clique_num k r ≤ spectral_extremal_chromatic_number k r- Formalizes
- arXiv:2610.13852 Sec. 6, Eq. (6.1)
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- spectral_extremal_clique_numFor an integer k ≥ 1 and real number r, the extremal distance-k clique number under spectral radius constraint r, denoted ω_λ(k, r), is…
- spectral_extremal_chromatic_numberFor an integer k ≥ 1 and real number r, the extremal distance-k chromatic number under spectral radius constraint r, denoted χ_λ(k, r), is…
- simple_graph_powerThe d-th power G^d of a graph G: same vertices, two distinct vertices adjacent iff they are joined by a path (equivalently a walk) of…
- adjacency_spectral_radiusThe adjacency spectral radius of a simple graph G on a finite vertex set is the spectral radius of its real adjacency matrix.
Read back from the Lean
For every natural number $k$ and every real number $r$, the spectral extremal clique number spectral_extremal_clique_num k r is less than or equal to the spectral extremal chromatic number spectral_extremal_chromatic_number k r (in the extended natural numbers $\mathbb{N}_\infty$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Both the extremal distance-k clique number and chromatic number are defined as the supremum of the clique number and chromatic number, respectively, of the graph power G^k taken over all finite graphs G whose adjacency spectral radius is bounded by r. Because the clique number of any graph is at most its chromatic number, the inequality holds point-wise for each graph G^k. The result follows by the monotonicity of the supremum.
The inequality is expressed as comparing nested suprema over all vertex counts n, graphs G on n vertices, and proofs that the adjacency spectral radius of G is at most r.
We unfold the definitions of spectral_extremal_clique_num and spectral_extremal_chromatic_number, exposing their definitions as suprema over n : ℕ, graphs G on Fin n, and the condition that the spectral radius of G does not exceed r.
unfold spectral_extremal_clique_num spectral_extremal_chromatic_numberThe extremal distance-k clique number is at most the extremal distance-k chromatic number.
Applying the monotonicity of the supremum (iSup_mono) across the three nested binders—n, G, and the spectral radius hypothesis—reduces the claim to showing that for any graph power G^k, its clique number is at most its chromatic number. This holds directly by SimpleGraph.cliqueNum_le_chromaticNumber.
uses
iSup_mono,SimpleGraph.cliqueNum_le_chromaticNumberexact iSup_mono fun n => iSup_mono fun G => iSup_mono fun _ => SimpleGraph.cliqueNum_le_chromaticNumber
iSup_mono- if f(i) ≤ g(i) for all indices i, then ⨆ i, f i ≤ ⨆ i, g i
SimpleGraph.cliqueNum_le_chromaticNumber- for any simple graph, its clique number is at most its chromatic number
- The clique number and chromatic number are evaluated in the extended natural numbers (ℕ∞) so that suprema are always well-defined.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- For every natural number k and real number r, the extremal distance-k clique number is at most the extremal distance-k chromatic number. -/theorem spectral_extremal_clique_num_le_chromatic_number (k : ℕ) (r : ℝ) : spectral_extremal_clique_num k r ≤ spectral_extremal_chromatic_number k r := by unfold spectral_extremal_clique_num spectral_extremal_chromatic_number exact iSup_mono fun n => iSup_mono fun G => iSup_mono fun _ => SimpleGraph.cliqueNum_le_chromaticNumber