AFTD Auto-Formalizing Theoretical Domains

petersen_hard_core_var_per_vertex_eq_poly

theoremverifiedformalization

For every real activity x, the per-vertex hard-core variance of the Petersen graph hardCoreVarSize petersen_graph (fun _ => x) / 10 equals petersen_poly_variance_per_vertex x.

Statement

theorem petersen_hard_core_var_per_vertex_eq_poly (x : ℝ) :
    letI : DecidableRel petersen_graph.Adj := fun s t => inferInstanceAs (Decidable (Disjoint s.1 t.1))
    hardCoreVarSize petersen_graph (fun _ => x) / 10 = petersen_poly_variance_per_vertex x
Formalizes
arXiv:1806.02146, folklore
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • petersen_graphThe Petersen graph P10, as the Kneser graph K(5,2): a SimpleGraph on the vertex type {s : Finset (Fin 5) // s.card = 2} of 2-element…
  • hardCoreVarSizeGiven a finite graph G on a type V with decidable equality and vertex fugacities lam, the variance of the independent set size…
  • petersen_poly_variance_per_vertexFor an activity x, the per-vertex hard-core variance of the Petersen graph computed from its independence polynomial 1 + 10*x + 30*x^2 +…
  • weightThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…

Read back from the Lean

For every real number $x$, the variance of the independent set size under the hard-core model on the Petersen graph with constant activity $x$, divided by 10, equals petersen_poly_variance_per_vertex x.

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

The proof establishes that the per-vertex hard-core variance of the Petersen graph at activity x equals the explicit rational function `petersen_poly_variance_per_vertex x` by computing its independence polynomial. Exhaustive finite checking via `decide` determines that the Petersen graph has exactly 1, 10, 30, 30, 5, and 0 independent sets of sizes 0, 1, 2, 3, 4, and 5 respectively, with no independent sets of size 5 or greater. A general fiberwise sum decomposition partitions sums over all independent sets by their cardinality, yielding the partition function Z(x), the first moment A₁(x), and the second moment A₂(x) as explicit polynomials in x. Finally, substituting these polynomial expressions into the definition of hard-core variance (A₂/Z - (A₁/Z)²) / 10 matches the target rational expression.

  1. A finite set of vertices is an independent set in the Petersen graph if and only if no two distinct vertices in it are adjacent.

    Unfolds the definition of graph independence via `SimpleGraph.isIndepSet_iff`, which expresses independence as pairwise non-adjacency, and simplifies set membership coercions from `Finset` to `Set`.

    lines 18–19

    uses SimpleGraph.isIndepSet_iff, Set.Pairwise, petersen_hard_core_var_per_vertex_eq_poly_indep, Finset.mem_coe

      simp only [SimpleGraph.isIndepSet_iff, Set.Pairwise, petersen_hard_core_var_per_vertex_eq_poly_indep,
        Finset.mem_coe]
  2. For every natural number k, the independent sets of size k in the Petersen graph are exactly the independent sets among all k-element subsets of vertices.

    Unfolds `petersen_hard_core_var_per_vertex_eq_poly_indepSets` and writes the k-element powerset as a filter on `Finset.univ`. After merging the filters with `Finset.filter_filter`, it applies `Finset.filter_congr` using the equivalence between graph independence and finset independence.

    lines 33–37

    uses Finset.filter_filter, Finset.powersetCard_eq_filter, Finset.powerset_univ, Finset.filter_congr, petersen_hard_core_var_per_vertex_eq_poly_isIndepSet_iff

      rw [petersen_hard_core_var_per_vertex_eq_poly_indepSets, Finset.filter_filter,
        Finset.powersetCard_eq_filter, Finset.powerset_univ, Finset.filter_filter]
      exact Finset.filter_congr (fun I _ => by
        rw [petersen_hard_core_var_per_vertex_eq_poly_isIndepSet_iff]
        tauto)
  3. The Petersen graph has exactly 1 independent set of size 0, 10 of size 1, 30 of size 2, 30 of size 3, 5 of size 4, and 0 of size 5. automation

    Because the Petersen graph has only 10 vertices, the cardinality of the independent sets of each fixed size from 0 through 5 is verified by exhaustive computation on finite sets using `decide`.

    lines 44–79

      decide
    
    /-- There are exactly ten independent sets of size `1` in the Petersen graph. -/
    lemma petersen_hard_core_var_per_vertex_eq_poly_count_1 :
        (Finset.filter petersen_hard_core_var_per_vertex_eq_poly_indep
          (Finset.powersetCard 1
            (Finset.univ : Finset petersen_hard_core_var_per_vertex_eq_poly_V))).card = 10 := by
      decide
    
    /-- There are exactly thirty independent sets of size `2` in the Petersen graph. -/
    lemma petersen_hard_core_var_per_vertex_eq_poly_count_2 :
        (Finset.filter petersen_hard_core_var_per_vertex_eq_poly_indep
          (Finset.powersetCard 2
            (Finset.univ : Finset petersen_hard_core_var_per_vertex_eq_poly_V))).card = 30 := by
      decide
    
    /-- There are exactly thirty independent sets of size `3` in the Petersen graph. -/
    lemma petersen_hard_core_var_per_vertex_eq_poly_count_3 :
        (Finset.filter petersen_hard_core_var_per_vertex_eq_poly_indep
          (Finset.powersetCard 3
            (Finset.univ : Finset petersen_hard_core_var_per_vertex_eq_poly_V))).card = 30 := by
      decide
    
    /-- There are exactly five independent sets of size `4` in the Petersen graph. -/
    lemma petersen_hard_core_var_per_vertex_eq_poly_count_4 :
        (Finset.filter petersen_hard_core_var_per_vertex_eq_poly_indep
          (Finset.powersetCard 4
            (Finset.univ : Finset petersen_hard_core_var_per_vertex_eq_poly_V))).card = 5 := by
      decide
    
    /-- The Petersen graph has no independent set of size `5`. -/
    lemma petersen_hard_core_var_per_vertex_eq_poly_count_5 :
        (Finset.filter petersen_hard_core_var_per_vertex_eq_poly_indep
          (Finset.powersetCard 5
            (Finset.univ : Finset petersen_hard_core_var_per_vertex_eq_poly_V))).card = 0 := by
      decide
  4. The filtered collection of independent sets of size k has cardinality 1 for k=0, 10 for k=1, 30 for k=2, 30 for k=3, and 5 for k=4.

    For each size k ∈ {0, 1, 2, 3, 4}, rewrites the filtered subset of `indepSets` into the filtered powerset using `petersen_hard_core_var_per_vertex_eq_poly_filter_card_eq` and substitutes the precomputed count for that size.

    lines 84–109

    uses petersen_hard_core_var_per_vertex_eq_poly_filter_card_eq, petersen_hard_core_var_per_vertex_eq_poly_count_0, petersen_hard_core_var_per_vertex_eq_poly_count_1, petersen_hard_core_var_per_vertex_eq_poly_count_2, petersen_hard_core_var_per_vertex_eq_poly_count_3, petersen_hard_core_var_per_vertex_eq_poly_count_4

      rw [petersen_hard_core_var_per_vertex_eq_poly_filter_card_eq,
        petersen_hard_core_var_per_vertex_eq_poly_count_0]
    
    /-- The number of independent sets of size `1`. -/
    lemma petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_1 :
        (petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter (fun I => I.card = 1)).card = 10 := by
      rw [petersen_hard_core_var_per_vertex_eq_poly_filter_card_eq,
        petersen_hard_core_var_per_vertex_eq_poly_count_1]
    
    /-- The number of independent sets of size `2`. -/
    lemma petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_2 :
        (petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter (fun I => I.card = 2)).card = 30 := by
      rw [petersen_hard_core_var_per_vertex_eq_poly_filter_card_eq,
        petersen_hard_core_var_per_vertex_eq_poly_count_2]
    
    /-- The number of independent sets of size `3`. -/
    lemma petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_3 :
        (petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter (fun I => I.card = 3)).card = 30 := by
      rw [petersen_hard_core_var_per_vertex_eq_poly_filter_card_eq,
        petersen_hard_core_var_per_vertex_eq_poly_count_3]
    
    /-- The number of independent sets of size `4`. -/
    lemma petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_4 :
        (petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter (fun I => I.card = 4)).card = 5 := by
      rw [petersen_hard_core_var_per_vertex_eq_poly_filter_card_eq,
        petersen_hard_core_var_per_vertex_eq_poly_count_4]
  5. Every independent set of vertices in the Petersen graph has cardinality at most 4.

    By contradiction: if an independent set I had cardinality strictly greater than 4, it would contain a subset J of cardinality 5 by `Finset.exists_subset_card_eq`. By monotonicity (`petersen_hard_core_var_per_vertex_eq_poly_indep_mono`), J would be an independent 5-subset, implying that the collection of independent 5-subsets is non-empty. But that collection was proven to have cardinality 0 by `petersen_hard_core_var_per_vertex_eq_poly_count_5`, a contradiction.

    lines 122–132

    uses Nat.not_le, Finset.exists_subset_card_eq, Finset.mem_filter, Finset.mem_powersetCard, Finset.subset_univ, petersen_hard_core_var_per_vertex_eq_poly_indep_mono, Finset.card_ne_zero_of_mem, petersen_hard_core_var_per_vertex_eq_poly_count_5

      by_contra hc
      rw [Nat.not_le] at hc
      obtain ⟨J, hJ, hJc⟩ := Finset.exists_subset_card_eq (s := I) (n := 5) hc
      have hJmem : J ∈ Finset.filter petersen_hard_core_var_per_vertex_eq_poly_indep
          (Finset.powersetCard 5
            (Finset.univ : Finset petersen_hard_core_var_per_vertex_eq_poly_V)) := by
        rw [Finset.mem_filter, Finset.mem_powersetCard]
        exact ⟨⟨Finset.subset_univ J, hJc⟩, petersen_hard_core_var_per_vertex_eq_poly_indep_mono h hJ⟩
      have hne := Finset.card_ne_zero_of_mem hJmem
      rw [petersen_hard_core_var_per_vertex_eq_poly_count_5] at hne
      exact hne rfl
  6. Every element of `indepSets` has cardinality at most 4.

    Unpacks membership in `indepSets` via `Finset.mem_filter`, converts graph-level independence to finset independence using `petersen_hard_core_var_per_vertex_eq_poly_isIndepSet_iff`, and applies `petersen_hard_core_var_per_vertex_eq_poly_card_le_four`.

    lines 138–140

    uses Finset.mem_filter, petersen_hard_core_var_per_vertex_eq_poly_card_le_four, petersen_hard_core_var_per_vertex_eq_poly_isIndepSet_iff

      rw [petersen_hard_core_var_per_vertex_eq_poly_indepSets, Finset.mem_filter] at hI
      exact petersen_hard_core_var_per_vertex_eq_poly_card_le_four
        ((petersen_hard_core_var_per_vertex_eq_poly_isIndepSet_iff I).mp hI.2)
  7. For any j, the sum of x^|I| · g(|I|) over all independent sets of size j equals the number of such sets times x^j · g(j).

    On the fiber of independent sets I with |I| = j, the summand x^|I| · g(|I|) takes the constant value x^j · g(j). Summing this constant over the fiber gives the cardinality of the fiber times the constant by `Finset.sum_const`.

    lines 148–161

    uses Finset.sum_const, nsmul_eq_mul, Finset.sum_congr, Finset.mem_filter

      have hstep : ∀ j : ℕ,
          (∑ I ∈ petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter (fun I => I.card = j),
              x ^ I.card * g I.card) =
            ((petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter
              (fun I => I.card = j)).card : ℝ) * (x ^ j * g j) := by
        intro j
        rw [show ((petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter
              (fun I => I.card = j)).card : ℝ) * (x ^ j * g j) =
            ∑ _I ∈ petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter
              (fun I => I.card = j), (x ^ j * g j) by
          rw [Finset.sum_const, nsmul_eq_mul]]
        exact Finset.sum_congr rfl (fun I hI => by
          simp only [Finset.mem_filter] at hI
          rw [hI.2])
  8. The cardinality of every independent set in `indepSets` lies in `Finset.range 5`. automation

    Because every independent set has cardinality at most 4, its cardinality is strictly less than 5, which means it belongs to `Finset.range 5` by `Finset.mem_range` (closed by linear integer arithmetic via `omega`).

    lines 162–167

    uses Finset.mem_range, petersen_hard_core_var_per_vertex_eq_poly_indepSets_card_le_four

      have hmem : ∀ I ∈ petersen_hard_core_var_per_vertex_eq_poly_indepSets,
          I.card ∈ Finset.range 5 := by
        intro I hI
        rw [Finset.mem_range]
        have h := petersen_hard_core_var_per_vertex_eq_poly_indepSets_card_le_four hI
        omega
  9. The weighted sum over all independent sets expands as 1 · (x⁰ g(0)) + 10 · (x¹ g(1)) + 30 · (x² g(2)) + 30 · (x³ g(3)) + 5 · (x⁴ g(4)).

    Groups the sum fiberwise by cardinality over `Finset.range 5` using `Finset.sum_fiberwise_of_maps_to`. It expands the finite sum over {0, 1, 2, 3, 4}, substitutes the fiber sums `hstep` and the known counts for each size from 0 to 4, and simplifies the resulting real polynomial with `push_cast` and `ring`.

    lines 168–180

    uses Finset.sum_fiberwise_of_maps_to, Finset.sum_range_succ, Finset.sum_range_zero, petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_0, petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_1, petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_2, petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_3, petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_4

      have hfib := Finset.sum_fiberwise_of_maps_to
        (s := petersen_hard_core_var_per_vertex_eq_poly_indepSets)
        (t := Finset.range 5) (g := fun I => I.card) hmem
        (f := fun I => x ^ I.card * g I.card)
      rw [← hfib]
      simp only [Finset.sum_range_succ, Finset.sum_range_zero, hstep,
        petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_0,
        petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_1,
        petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_2,
        petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_3,
        petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_4]
      push_cast
      ring
  10. The hard-core partition function Z(x) equals 1 + 10x + 30x² + 30x³ + 5x⁴.

    Specializes the general sum formula `petersen_hard_core_var_per_vertex_eq_poly_sum_eq` with the constant function g ≡ 1, simplifies multiplications by 1 with `mul_one`, and simplifies the polynomial using `ring`.

    lines 186–189

    uses petersen_hard_core_var_per_vertex_eq_poly_sum_eq, mul_one

      have h := petersen_hard_core_var_per_vertex_eq_poly_sum_eq (fun _ => (1 : ℝ)) x
      simp only [mul_one] at h
      rw [h]
      ring
  11. The first-moment sum A₁(x) = ∑ x^|I| · |I| equals 10x + 60x² + 90x³ + 20x⁴.

    Specializes `petersen_hard_core_var_per_vertex_eq_poly_sum_eq` with g(k) = k, casts integers to reals with `push_cast`, and simplifies the polynomial coefficients using `ring`.

    lines 195–198

    uses petersen_hard_core_var_per_vertex_eq_poly_sum_eq

      have h := petersen_hard_core_var_per_vertex_eq_poly_sum_eq (fun k : ℕ => (k : ℝ)) x
      rw [h]
      push_cast
      ring
  12. The second-moment sum A₂(x) = ∑ x^|I| · |I|² equals 10x + 120x² + 270x³ + 80x⁴.

    Specializes `petersen_hard_core_var_per_vertex_eq_poly_sum_eq` with g(k) = k², casts integers to reals with `push_cast`, and simplifies the polynomial coefficients using `ring`.

    lines 205–208

    uses petersen_hard_core_var_per_vertex_eq_poly_sum_eq

      have h := petersen_hard_core_var_per_vertex_eq_poly_sum_eq (fun k : ℕ => (k : ℝ) ^ 2) x
      rw [h]
      push_cast
      ring
  13. The per-vertex hard-core variance of the Petersen graph equals `petersen_poly_variance_per_vertex x`.

    Unfolds the definitions of `hardCoreVarSize` and `petersen_poly_variance_per_vertex`, simplifies the uniform vertex activity product to x^|I| via `Finset.prod_const`, and substitutes the explicit polynomial evaluations for Z(x), A₁(x), and A₂(x).

    lines 214–217

    uses Finset.prod_const, petersen_hard_core_var_per_vertex_eq_poly_sum_Z, petersen_hard_core_var_per_vertex_eq_poly_sum_A1, petersen_hard_core_var_per_vertex_eq_poly_sum_A2

      simp only [hardCoreVarSize, petersen_poly_variance_per_vertex, Finset.prod_const]
      rw [petersen_hard_core_var_per_vertex_eq_poly_sum_Z,
        petersen_hard_core_var_per_vertex_eq_poly_sum_A1,
        petersen_hard_core_var_per_vertex_eq_poly_sum_A2]
  14. The main theorem holds: for any real activity x, the per-vertex hard-core variance of the Petersen graph is given by `petersen_poly_variance_per_vertex x`.

    Concludes the theorem directly from `petersen_hard_core_var_per_vertex_eq_poly_main x`.

    line 223

    uses petersen_hard_core_var_per_vertex_eq_poly_main

      exact petersen_hard_core_var_per_vertex_eq_poly_main x
Finset.mem_coe
An element belongs to the set coercion of a finite set if and only if it belongs to the finite set.
SimpleGraph.isIndepSet_iff
A set of vertices in a simple graph is an independent set if and only if every pair of distinct vertices in it is non-adjacent.
Set.Pairwise
The proposition that a binary relation holds for every pair of distinct elements in a given set.
petersen_hard_core_var_per_vertex_eq_poly_indep
The property that no two distinct vertices in a finite set of vertices of the Petersen graph are adjacent.
Finset.filter_filter
Filtering a finite set successively by two predicates is equivalent to filtering by their conjunction.
Finset.powersetCard_eq_filter
The collection of subsets of size n from a finite set s equals the filter of its powerset by cardinality n.
Finset.powerset_univ
The powerset of the universal finite set of a finite type is the universal finite set of finite sets.
Finset.filter_congr
Two predicates that are equivalent on all elements of a finite set produce the same filtered sub-finset.
petersen_hard_core_var_per_vertex_eq_poly_isIndepSet_iff
A finite set of vertices is an independent set of the Petersen graph if and only if it satisfies finset-level independence.
petersen_hard_core_var_per_vertex_eq_poly_filter_card_eq
The independent sets of size k in the Petersen graph are exactly the independent sets among all k-element subsets of vertices.
petersen_hard_core_var_per_vertex_eq_poly_count_0
There is exactly 1 independent set of size 0 in the Petersen graph.
petersen_hard_core_var_per_vertex_eq_poly_count_1
There are exactly 10 independent sets of size 1 in the Petersen graph.
petersen_hard_core_var_per_vertex_eq_poly_count_2
There are exactly 30 independent sets of size 2 in the Petersen graph.
petersen_hard_core_var_per_vertex_eq_poly_count_3
There are exactly 30 independent sets of size 3 in the Petersen graph.
petersen_hard_core_var_per_vertex_eq_poly_count_4
There are exactly 5 independent sets of size 4 in the Petersen graph.
petersen_hard_core_var_per_vertex_eq_poly_count_5
There are no independent sets of size 5 in the Petersen graph.
Nat.not_le
For natural numbers, not being at most b is equivalent to being strictly greater than b.
Finset.exists_subset_card_eq
A finite set of cardinality at least n contains a subset of cardinality exactly n.
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the set and satisfies the predicate.
Finset.mem_powersetCard
A finite set belongs to the n-element powerset of t if and only if it is a subset of t of cardinality n.
Finset.subset_univ
Every finite set of elements from a finite type is a subset of the universal finite set.
petersen_hard_core_var_per_vertex_eq_poly_indep_mono
Any subset of an independent finset of vertices is an independent finset.
Finset.card_ne_zero_of_mem
A finite set that contains an element has non-zero cardinality.
petersen_hard_core_var_per_vertex_eq_poly_card_le_four
Every independent finset of vertices in the Petersen graph has cardinality at most 4.
Finset.sum_const
Summing a constant value over a finite set equals the cardinality of the set scalar-multiplied by that value.
nsmul_eq_mul
Natural number scalar multiplication in a semiring equals multiplication by the natural number cast to the ring.
Finset.sum_congr
Sums of pointwise equal functions over identical finite sets are equal.
Finset.mem_range
A natural number m belongs to `Finset.range n` if and only if m < n.
petersen_hard_core_var_per_vertex_eq_poly_indepSets_card_le_four
Every independent set in `indepSets` has cardinality at most 4.
Finset.sum_fiberwise_of_maps_to
A sum over a finite set can be partitioned fiberwise by grouping elements according to the values of a function whose image lies in the target set.
Finset.sum_range_succ
A sum over the range 0 to n+1 equals the sum over 0 to n plus the term at n.
Finset.sum_range_zero
A sum over the empty range `Finset.range 0` is 0.
petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_0
The number of independent sets of size 0 in the Petersen graph is 1.
petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_1
The number of independent sets of size 1 in the Petersen graph is 10.
petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_2
The number of independent sets of size 2 in the Petersen graph is 30.
petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_3
The number of independent sets of size 3 in the Petersen graph is 30.
petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_4
The number of independent sets of size 4 in the Petersen graph is 5.
petersen_hard_core_var_per_vertex_eq_poly_sum_eq
The sum of x^|I| · g(|I|) over all independent sets I expands as a linear combination weighted by the independent set counts for sizes 0 through 4.
mul_one
Multiplying an element by 1 on the right leaves it unchanged.
Finset.prod_const
The product of a constant element over a finite set equals that element raised to the cardinality of the set.
petersen_hard_core_var_per_vertex_eq_poly_sum_Z
The hard-core partition function of the Petersen graph at activity x equals 1 + 10x + 30x² + 30x³ + 5x⁴.
petersen_hard_core_var_per_vertex_eq_poly_sum_A1
The first-moment sum ∑ x^|I| · |I| of the Petersen graph at activity x equals 10x + 60x² + 90x³ + 20x⁴.
petersen_hard_core_var_per_vertex_eq_poly_sum_A2
The second-moment sum ∑ x^|I| · |I|² of the Petersen graph at activity x equals 10x + 120x² + 270x³ + 80x⁴.
petersen_hard_core_var_per_vertex_eq_poly_main
The per-vertex hard-core variance of the Petersen graph equals `petersen_poly_variance_per_vertex x`.

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

/-- The vertex type of the Petersen graph: two-element subsets of `Fin 5`. -/abbrev petersen_hard_core_var_per_vertex_eq_poly_V : Type := {s : Finset (Fin 5) // s.card = 2}/-- Decidable adjacency for the Petersen graph (the Kneser graph `K(5,2)`). -/instance petersen_hard_core_var_per_vertex_eq_poly_decRel : DecidableRel petersen_graph.Adj :=  fun s t => inferInstanceAs (Decidable (Disjoint s.1 t.1))/-- A `Finset`-level form of independence: no two distinct members are adjacent. -/abbrev petersen_hard_core_var_per_vertex_eq_poly_indep    (I : Finset petersen_hard_core_var_per_vertex_eq_poly_V) : Prop :=  ∀ a ∈ I, ∀ b ∈ I, a ≠ b → ¬ petersen_graph.Adj a b/-- Independence of a finset is the same as being an independent set of the graph. -/lemma petersen_hard_core_var_per_vertex_eq_poly_isIndepSet_iff    (I : Finset petersen_hard_core_var_per_vertex_eq_poly_V) :    petersen_graph.IsIndepSet (I : Set petersen_hard_core_var_per_vertex_eq_poly_V) ↔      petersen_hard_core_var_per_vertex_eq_poly_indep I := by  simp only [SimpleGraph.isIndepSet_iff, Set.Pairwise, petersen_hard_core_var_per_vertex_eq_poly_indep,    Finset.mem_coe]/-- The independent sets of the Petersen graph, as a finset of finsets of vertices. -/abbrev petersen_hard_core_var_per_vertex_eq_poly_indepSets :    Finset (Finset petersen_hard_core_var_per_vertex_eq_poly_V) :=  Finset.univ.filter (fun I =>    petersen_graph.IsIndepSet (I : Set petersen_hard_core_var_per_vertex_eq_poly_V))/-- Independent sets of size `k` are exactly the independent `k`-subsets of all vertices. -/lemma petersen_hard_core_var_per_vertex_eq_poly_filter_card_eq (k : ℕ) :    petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter (fun I => I.card = k) =      Finset.filter petersen_hard_core_var_per_vertex_eq_poly_indep        (Finset.powersetCard k          (Finset.univ : Finset petersen_hard_core_var_per_vertex_eq_poly_V)) := by  rw [petersen_hard_core_var_per_vertex_eq_poly_indepSets, Finset.filter_filter,    Finset.powersetCard_eq_filter, Finset.powerset_univ, Finset.filter_filter]  exact Finset.filter_congr (fun I _ => by    rw [petersen_hard_core_var_per_vertex_eq_poly_isIndepSet_iff]    tauto)/-- There is exactly one independent set of size `0` in the Petersen graph. -/lemma petersen_hard_core_var_per_vertex_eq_poly_count_0 :    (Finset.filter petersen_hard_core_var_per_vertex_eq_poly_indep      (Finset.powersetCard 0        (Finset.univ : Finset petersen_hard_core_var_per_vertex_eq_poly_V))).card = 1 := by  decide/-- There are exactly ten independent sets of size `1` in the Petersen graph. -/lemma petersen_hard_core_var_per_vertex_eq_poly_count_1 :    (Finset.filter petersen_hard_core_var_per_vertex_eq_poly_indep      (Finset.powersetCard 1        (Finset.univ : Finset petersen_hard_core_var_per_vertex_eq_poly_V))).card = 10 := by  decide/-- There are exactly thirty independent sets of size `2` in the Petersen graph. -/lemma petersen_hard_core_var_per_vertex_eq_poly_count_2 :    (Finset.filter petersen_hard_core_var_per_vertex_eq_poly_indep      (Finset.powersetCard 2        (Finset.univ : Finset petersen_hard_core_var_per_vertex_eq_poly_V))).card = 30 := by  decide/-- There are exactly thirty independent sets of size `3` in the Petersen graph. -/lemma petersen_hard_core_var_per_vertex_eq_poly_count_3 :    (Finset.filter petersen_hard_core_var_per_vertex_eq_poly_indep      (Finset.powersetCard 3        (Finset.univ : Finset petersen_hard_core_var_per_vertex_eq_poly_V))).card = 30 := by  decide/-- There are exactly five independent sets of size `4` in the Petersen graph. -/lemma petersen_hard_core_var_per_vertex_eq_poly_count_4 :    (Finset.filter petersen_hard_core_var_per_vertex_eq_poly_indep      (Finset.powersetCard 4        (Finset.univ : Finset petersen_hard_core_var_per_vertex_eq_poly_V))).card = 5 := by  decide/-- The Petersen graph has no independent set of size `5`. -/lemma petersen_hard_core_var_per_vertex_eq_poly_count_5 :    (Finset.filter petersen_hard_core_var_per_vertex_eq_poly_indep      (Finset.powersetCard 5        (Finset.univ : Finset petersen_hard_core_var_per_vertex_eq_poly_V))).card = 0 := by  decide/-- The number of independent sets of size `0`. -/lemma petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_0 :    (petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter (fun I => I.card = 0)).card = 1 := by  rw [petersen_hard_core_var_per_vertex_eq_poly_filter_card_eq,    petersen_hard_core_var_per_vertex_eq_poly_count_0]/-- The number of independent sets of size `1`. -/lemma petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_1 :    (petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter (fun I => I.card = 1)).card = 10 := by  rw [petersen_hard_core_var_per_vertex_eq_poly_filter_card_eq,    petersen_hard_core_var_per_vertex_eq_poly_count_1]/-- The number of independent sets of size `2`. -/lemma petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_2 :    (petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter (fun I => I.card = 2)).card = 30 := by  rw [petersen_hard_core_var_per_vertex_eq_poly_filter_card_eq,    petersen_hard_core_var_per_vertex_eq_poly_count_2]/-- The number of independent sets of size `3`. -/lemma petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_3 :    (petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter (fun I => I.card = 3)).card = 30 := by  rw [petersen_hard_core_var_per_vertex_eq_poly_filter_card_eq,    petersen_hard_core_var_per_vertex_eq_poly_count_3]/-- The number of independent sets of size `4`. -/lemma petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_4 :    (petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter (fun I => I.card = 4)).card = 5 := by  rw [petersen_hard_core_var_per_vertex_eq_poly_filter_card_eq,    petersen_hard_core_var_per_vertex_eq_poly_count_4]/-- A subset of an independent finset is independent. -/lemma petersen_hard_core_var_per_vertex_eq_poly_indep_mono    {I J : Finset petersen_hard_core_var_per_vertex_eq_poly_V}    (h : petersen_hard_core_var_per_vertex_eq_poly_indep I) (hJI : J ⊆ I) :    petersen_hard_core_var_per_vertex_eq_poly_indep J :=  fun a ha b hb hab => h a (hJI ha) b (hJI hb) hab/-- Every independent finset of the Petersen graph has at most four vertices. -/lemma petersen_hard_core_var_per_vertex_eq_poly_card_le_four    {I : Finset petersen_hard_core_var_per_vertex_eq_poly_V}    (h : petersen_hard_core_var_per_vertex_eq_poly_indep I) : I.card ≤ 4 := by  by_contra hc  rw [Nat.not_le] at hc  obtain ⟨J, hJ, hJc⟩ := Finset.exists_subset_card_eq (s := I) (n := 5) hc  have hJmem : J ∈ Finset.filter petersen_hard_core_var_per_vertex_eq_poly_indep      (Finset.powersetCard 5        (Finset.univ : Finset petersen_hard_core_var_per_vertex_eq_poly_V)) := by    rw [Finset.mem_filter, Finset.mem_powersetCard]    exact ⟨⟨Finset.subset_univ J, hJc⟩, petersen_hard_core_var_per_vertex_eq_poly_indep_mono h hJ⟩  have hne := Finset.card_ne_zero_of_mem hJmem  rw [petersen_hard_core_var_per_vertex_eq_poly_count_5] at hne  exact hne rfl/-- Every independent set of the Petersen graph has at most four vertices. -/lemma petersen_hard_core_var_per_vertex_eq_poly_indepSets_card_le_four    {I : Finset petersen_hard_core_var_per_vertex_eq_poly_V}    (hI : I ∈ petersen_hard_core_var_per_vertex_eq_poly_indepSets) : I.card ≤ 4 := by  rw [petersen_hard_core_var_per_vertex_eq_poly_indepSets, Finset.mem_filter] at hI  exact petersen_hard_core_var_per_vertex_eq_poly_card_le_four    ((petersen_hard_core_var_per_vertex_eq_poly_isIndepSet_iff I).mp hI.2)/-- Independent-set counts of the Petersen graph with the weight `x ^ |I| · g |I|`,grouped by the size `|I|` of the independent set. -/lemma petersen_hard_core_var_per_vertex_eq_poly_sum_eq (g : ℕ → ℝ) (x : ℝ) :    (∑ I ∈ petersen_hard_core_var_per_vertex_eq_poly_indepSets, x ^ I.card * g I.card) =      1 * (x ^ 0 * g 0) + 10 * (x ^ 1 * g 1) + 30 * (x ^ 2 * g 2) + 30 * (x ^ 3 * g 3) +        5 * (x ^ 4 * g 4) := by  have hstep : ∀ j : ℕ,      (∑ I ∈ petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter (fun I => I.card = j),          x ^ I.card * g I.card) =        ((petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter          (fun I => I.card = j)).card : ℝ) * (x ^ j * g j) := by    intro j    rw [show ((petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter          (fun I => I.card = j)).card : ℝ) * (x ^ j * g j) =        ∑ _I ∈ petersen_hard_core_var_per_vertex_eq_poly_indepSets.filter          (fun I => I.card = j), (x ^ j * g j) by      rw [Finset.sum_const, nsmul_eq_mul]]    exact Finset.sum_congr rfl (fun I hI => by      simp only [Finset.mem_filter] at hI      rw [hI.2])  have hmem : ∀ I ∈ petersen_hard_core_var_per_vertex_eq_poly_indepSets,      I.card ∈ Finset.range 5 := by    intro I hI    rw [Finset.mem_range]    have h := petersen_hard_core_var_per_vertex_eq_poly_indepSets_card_le_four hI    omega  have hfib := Finset.sum_fiberwise_of_maps_to    (s := petersen_hard_core_var_per_vertex_eq_poly_indepSets)    (t := Finset.range 5) (g := fun I => I.card) hmem    (f := fun I => x ^ I.card * g I.card)  rw [← hfib]  simp only [Finset.sum_range_succ, Finset.sum_range_zero, hstep,    petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_0,    petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_1,    petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_2,    petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_3,    petersen_hard_core_var_per_vertex_eq_poly_indepSets_count_4]  push_cast  ring/-- The hard-core partition function of the Petersen graph at activity `x`. -/lemma petersen_hard_core_var_per_vertex_eq_poly_sum_Z (x : ℝ) :    (∑ I ∈ petersen_hard_core_var_per_vertex_eq_poly_indepSets, x ^ I.card) =      1 + 10 * x + 30 * x ^ 2 + 30 * x ^ 3 + 5 * x ^ 4 := by  have h := petersen_hard_core_var_per_vertex_eq_poly_sum_eq (fun _ => (1 : ℝ)) x  simp only [mul_one] at h  rw [h]  ring/-- The first moment of the independent set size of the Petersen graph at activity `x`. -/lemma petersen_hard_core_var_per_vertex_eq_poly_sum_A1 (x : ℝ) :    (∑ I ∈ petersen_hard_core_var_per_vertex_eq_poly_indepSets, x ^ I.card * (I.card : ℝ)) =      10 * x + 60 * x ^ 2 + 90 * x ^ 3 + 20 * x ^ 4 := by  have h := petersen_hard_core_var_per_vertex_eq_poly_sum_eq (fun k : ℕ => (k : ℝ)) x  rw [h]  push_cast  ring/-- The second moment of the independent set size of the Petersen graph at activity `x`. -/lemma petersen_hard_core_var_per_vertex_eq_poly_sum_A2 (x : ℝ) :    (∑ I ∈ petersen_hard_core_var_per_vertex_eq_poly_indepSets,      x ^ I.card * (I.card : ℝ) ^ 2) =      10 * x + 120 * x ^ 2 + 270 * x ^ 3 + 80 * x ^ 4 := by  have h := petersen_hard_core_var_per_vertex_eq_poly_sum_eq (fun k : ℕ => (k : ℝ) ^ 2) x  rw [h]  push_cast  ring/-- The per-vertex hard-core variance of the Petersen graph equals the variance computedfrom its independence polynomial `1 + 10x + 30x² + 30x³ + 5x⁴`. -/lemma petersen_hard_core_var_per_vertex_eq_poly_main (x : ℝ) :    hardCoreVarSize petersen_graph (fun _ => x) / 10 = petersen_poly_variance_per_vertex x := by  simp only [hardCoreVarSize, petersen_poly_variance_per_vertex, Finset.prod_const]  rw [petersen_hard_core_var_per_vertex_eq_poly_sum_Z,    petersen_hard_core_var_per_vertex_eq_poly_sum_A1,    petersen_hard_core_var_per_vertex_eq_poly_sum_A2]/-- The combinatorial hard-core variance per vertex of the Petersen graph equals its polynomial expression. -/theorem petersen_hard_core_var_per_vertex_eq_poly (x : ℝ) :    letI : DecidableRel petersen_graph.Adj := fun s t => inferInstanceAs (Decidable (Disjoint s.1 t.1))    hardCoreVarSize petersen_graph (fun _ => x) / 10 = petersen_poly_variance_per_vertex x := by  exact petersen_hard_core_var_per_vertex_eq_poly_main x
See it in the graphDiscuss this resultChallenge it