Written on the Wall IICombinatorics
Written on the Wall II - Conjecture 100
WOWII Conjecture 100 (status O):
Mathematical statement
WOWII Conjecture 100 (status O):
For a simple connected graph G,
α(G) ≤ ⌈(max_v l(v) + 0.5 · diam(Gᶜ)) / 2⌉
where α(G) = G.indepNum is the independence number,
max_v l(v) is the maximum over all vertices of the independence number of
the neighbourhood (in G), and diam(Gᶜ) is the diameter of the
complement Gᶜ.
Note:* length(Ḡ) in DeLaVina's original is interpreted here as the
diameter of the complement. The hypothesis hGc : Gᶜ.Connected is added so
that diam(Gᶜ) is finite (otherwise Gᶜ.ediam = ⊤ and
Gᶜ.ediam.toNat collapses silently to 0); see the module
docstring above.
Statement source: Written on the Wall II statement material
Statement terms: Source-specific
Source-specific terms. Therefore does not assert reuse rights beyond attributed display.
Statement artifacts, not proofs
These records expose exact Lean propositions and statement-only wrappers. Defining a proposition does not supply a proof of it. A placeholder-bearing target also contains no proof. Elaboration checks syntax and types; it does not certify that a formalization perfectly captures every nuance of the informal problem.
Pinned Lean formulation 1
conjecture100
theorem conjecture100 (G : SimpleGraph α) [DecidableRel G.Adj] (h : G.Connected) (hGc : Gᶜ.Connected) : let maxL := (Finset.univ.image (indepNeighborsCard G)).max' (by simp) (G.indepNum : ℝ) ≤ ⌈((maxL : ℝ) + (1 / 2) * (degreeL2Norm Gᶜ : ℝ)) / 2⌉ := by sorry- Statement source
- Formal Conjectures
- Lean version
- v4.27.0
- Placeholder
- Present; no proof artifact
- Source evidence
- Pinned source index
- Fidelity review
- Community formulation
References