AFTD Auto-Formalizing Theoretical Domains

spectral_extremal_clique_num_le_chromatic_number

theoremverifiedformalization

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.

  1. 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.

    line 4

      unfold spectral_extremal_clique_num spectral_extremal_chromatic_number
  2. The 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.

    line 5

    uses iSup_mono, SimpleGraph.cliqueNum_le_chromaticNumber

      exact 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

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

/-- 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
See it in the graphDiscuss this resultChallenge it