petersen_hard_core_var_per_vertex_eq_poly
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.
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`.
uses
SimpleGraph.isIndepSet_iff,Set.Pairwise,petersen_hard_core_var_per_vertex_eq_poly_indep,Finset.mem_coesimp only [SimpleGraph.isIndepSet_iff, Set.Pairwise, petersen_hard_core_var_per_vertex_eq_poly_indep, Finset.mem_coe]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.
uses
Finset.filter_filter,Finset.powersetCard_eq_filter,Finset.powerset_univ,Finset.filter_congr,petersen_hard_core_var_per_vertex_eq_poly_isIndepSet_iffrw [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)
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`.
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 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.
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_4rw [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]
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.
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_5by_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 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`.
uses
Finset.mem_filter,petersen_hard_core_var_per_vertex_eq_poly_card_le_four,petersen_hard_core_var_per_vertex_eq_poly_isIndepSet_iffrw [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)
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`.
uses
Finset.sum_const,nsmul_eq_mul,Finset.sum_congr,Finset.mem_filterhave 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])
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`).
uses
Finset.mem_range,petersen_hard_core_var_per_vertex_eq_poly_indepSets_card_le_fourhave 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
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`.
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_4have 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 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`.
uses
petersen_hard_core_var_per_vertex_eq_poly_sum_eq,mul_onehave 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 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`.
uses
petersen_hard_core_var_per_vertex_eq_poly_sum_eqhave h := petersen_hard_core_var_per_vertex_eq_poly_sum_eq (fun k : ℕ => (k : ℝ)) x rw [h] push_cast ring
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`.
uses
petersen_hard_core_var_per_vertex_eq_poly_sum_eqhave 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 `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).
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_A2simp 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 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`.
uses
petersen_hard_core_var_per_vertex_eq_poly_mainexact 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`.
- The counts of independent sets of each size (0 through 5) in the Petersen graph are computed by Lean's `decide` tactic via exhaustive computation over all subsets of vertices, rather than by paper-and-pencil symmetry arguments.
- The partition function and moments of the independent set size are computed using a general fiberwise sum decomposition lemma (`Finset.sum_fiberwise_of_maps_to`) parameterized by an arbitrary weight function `g : ℕ → ℝ`, which is then instantiated for `g(k) = 1`, `g(k) = k`, and `g(k) = k²`.
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.
/-- 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