op_1239_at_most_two_nonzero_coeffs_log_concave
Every simple graph G on a finite type V with decidable equality and decidable adjacency for which the number of k in the range from 0 to Fintype.card V + 1 with petrial_coeff G k ≠ 0 is at most 2 satisfies petrial_log_concave G.
Statement
theorem op_1239_at_most_two_nonzero_coeffs_log_concave {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (h : ((Finset.range (Fintype.card V + 1)).filter (fun k => petrial_coeff G k ≠ 0)).card ≤ 2) : petrial_log_concave G
- Formalizes
- arXiv:2611.07503, Section 2
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- petrial_log_concaveA simple graph G on a finite type V with decidable equality and decidable adjacency has a log-concave partial Petrial polynomial if for…
- petrial_coeffGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and k : ℕ, petrial_coeff G k is the…
- petrial_matrixGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite subset F : Finset V,…
Read back from the Lean
Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$ with decidable adjacency. Suppose that the number of natural numbers $k \in \{0, 1, \dots, |V|\}$ such that $\operatorname{petrial\_coeff}(G, k) \neq 0$ is at most $2$. Then $G$ is $\operatorname{petrial\_log\_concave}$, meaning that for every $k \in \mathbb{N}$, if there exists $i < k$ with $\operatorname{petrial\_coeff}(G, i) \neq 0$ and there exists $j > k$ with $\operatorname{petrial\_coeff}(G, j) \neq 0$, then $\operatorname{petrial\_coeff}(G, k - 1) \cdot \operatorname{petrial\_coeff}(G, k + 1) \le (\operatorname{petrial\_coeff}(G, k))^2$.
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 shows that any graph with at most two non-zero Petrial coefficients satisfies the log-concavity condition vacuously, because the condition's premise can never be met. By induction on the symmetric difference between vertex subsets, the rank of the Petrial matrix over ℤ/2ℤ satisfies an intermediate value theorem: adding or deleting a single vertex changes the rank by at most 1, so every integer between two realizable ranks is also realized by some subset. Therefore, having non-zero coefficients at indices i < k and j > k forces the intermediate coefficient at k to be non-zero as well. This would yield at least three distinct non-zero coefficients, directly contradicting the hypothesis that at most two coefficients are non-zero.
The rank of the sum of two matrices is at most the sum of their ranks: (A + B).rank ≤ A.rank + B.rank.
Unfolding the definition of rank as the dimension of the range of the corresponding linear map, the range of A + B is contained in the sum of the ranges of A and B. Monotonicity of submodule dimension and subadditivity of the dimension of a submodule sum bound the rank of A + B by the sum of the ranks.
uses
Matrix.mulVecLin_add,LinearMap.range_add_le,Submodule.finrank_mono,Submodule.finrank_add_le_finrank_add_finrankunfold Matrix.rank rw [Matrix.mulVecLin_add] have hle : LinearMap.range (A.mulVecLin + B.mulVecLin) ≤ LinearMap.range A.mulVecLin ⊔ LinearMap.range B.mulVecLin := LinearMap.range_add_le _ _ have h1 := Submodule.finrank_mono hle have h2 := Submodule.finrank_add_le_finrank_add_finrank (LinearMap.range A.mulVecLin) (LinearMap.range B.mulVecLin) omega
A diagonal matrix over ℤ/2ℤ with at most one non-zero entry on the diagonal has rank at most 1.
The rank of a diagonal matrix equals the number of non-zero diagonal entries. Since the entries are 0 everywhere except possibly at index v, the set of non-zero entries is contained in the singleton {v}, whose cardinality is 1.
uses
Matrix.rank_diagonal,Fintype.card_subtype,Finset.card_le_card,Finset.card_singletonrw [Matrix.rank_diagonal] rw [Fintype.card_subtype] have : (Finset.univ.filter (fun w => (if w = v then (1 : ZMod 2) else 0) ≠ 0)) ⊆ {v} := by intro w hw simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hw split_ifs at hw with h · exact Finset.mem_singleton.mpr h · contradiction have hsub := Finset.card_le_card this simp only [Finset.card_singleton] at hsub exact hsub
For any vertex subset F and vertex v ∉ F, the Petrial matrix of F ∪ {v} equals the Petrial matrix of F plus the diagonal matrix with 1 at entry (v, v).
The Petrial matrix adds a diagonal indicator of the subset to the adjacency matrix. Inserting v into F changes only the diagonal entry at (v, v) from 0 to 1, which equals adding the single-entry diagonal matrix for v.
uses
Matrix.add_apply,Matrix.diagonal_apply,Finset.mem_insertunfold petrial_matrix ext i j simp only [Matrix.add_apply, Matrix.diagonal_apply, Finset.mem_insert] by_cases hij : i = j · subst hij by_cases hiv : i = v · subst hiv simp [hv] · simp [hiv] · simp [hij]
For any vertex subset F and vertex v ∉ F, the Petrial matrix of F equals the Petrial matrix of F ∪ {v} plus the diagonal matrix with 1 at entry (v, v).
Over the field ℤ/2ℤ, addition and subtraction coincide since 1 + 1 = 0. Adding the diagonal matrix at v to the Petrial matrix of F ∪ {v} resets the (v, v) entry from 1 to 0 while leaving all other entries unchanged, recovering the Petrial matrix of F.
uses
Matrix.add_apply,Matrix.diagonal_apply,Finset.mem_insertunfold petrial_matrix ext i j simp only [Matrix.add_apply, Matrix.diagonal_apply, Finset.mem_insert] by_cases hij : i = j · subst hij by_cases hiv : i = v · subst hiv have : (1 : ZMod 2) + 1 = 0 := rfl simp [hv, this] · simp [hiv] · simp [hij]
Inserting a vertex v ∉ F increases the Petrial matrix rank by at most 1: (petrial_matrix G (insert v F)).rank ≤ (petrial_matrix G F).rank + 1.
Rewriting the Petrial matrix of F ∪ {v} as the sum of the Petrial matrix of F and the single-entry diagonal matrix at v, the claim follows from rank subadditivity and the fact that the single-entry diagonal matrix has rank at most 1.
uses
op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_insert,op_1239_at_most_two_nonzero_coeffs_log_concave_matrix_rank_add_le,op_1239_at_most_two_nonzero_coeffs_log_concave_rank_single_diag_lerw [op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_insert G F v hv] have := op_1239_at_most_two_nonzero_coeffs_log_concave_matrix_rank_add_le (petrial_matrix G F) (Matrix.diagonal (fun w => if w = v then (1 : ZMod 2) else 0)) have h1 := op_1239_at_most_two_nonzero_coeffs_log_concave_rank_single_diag_le v omega
Removing a vertex v from F ∪ {v} changes the Petrial matrix rank by at most 1: (petrial_matrix G F).rank ≤ (petrial_matrix G (insert v F)).rank + 1.
Expressing the Petrial matrix of F as the Petrial matrix of F ∪ {v} plus the single-entry diagonal matrix at v over ℤ/2ℤ, subadditivity of rank bounds the rank of F by that of F ∪ {v} plus 1.
uses
op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_remove,op_1239_at_most_two_nonzero_coeffs_log_concave_matrix_rank_add_le,op_1239_at_most_two_nonzero_coeffs_log_concave_rank_single_diag_lerw [op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_remove G F v hv] have := op_1239_at_most_two_nonzero_coeffs_log_concave_matrix_rank_add_le (petrial_matrix G (insert v F)) (Matrix.diagonal (fun w => if w = v then (1 : ZMod 2) else 0)) have h1 := op_1239_at_most_two_nonzero_coeffs_log_concave_rank_single_diag_le v omega
For any v ∈ A, erasing v from A increases the Petrial matrix rank by at most 1: (petrial_matrix G (A.erase v)).rank ≤ (petrial_matrix G A).rank + 1.
Setting F = A \ {v}, the element v is not in F and insert v F = A. Applying the previous lemma with F immediately yields the bound.
uses
Finset.insert_erase,op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_lehave hnot : v ∉ A.erase v := by simp have hins : insert v (A.erase v) = A := Finset.insert_erase hv have := op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le G (A.erase v) v hnot rwa [hins] at this
The intermediate rank theorem holds in the base case where A = B.
We proceed by strong induction on the size of the symmetric difference n = |A \ B| + |B \ A|. When both differences have cardinality 0, mutual subset inclusion forces A = B. The given bounds rank(A) ≤ k ≤ rank(B) = rank(A) imply rank(A) = k, so A itself is the witness.
uses
Nat.strong_induction_on,Finset.card_eq_zero,Finset.sdiff_eq_empty_iff_subset,Finset.Subset.antisymmintro n induction' n using Nat.strong_induction_on with n ih intro A B hn k hA hB by_cases hAB_sdiff : (A \ B).card = 0 · by_cases hBA_sdiff : (B \ A).card = 0 · have h_eq : A = B := by rw [Finset.card_eq_zero, Finset.sdiff_eq_empty_iff_subset] at hAB_sdiff hBA_sdiff exact Finset.Subset.antisymm hAB_sdiff hBA_sdiff subst h_eq exact ⟨A, by omega⟩
When A ⊊ B, there exists a vertex subset C with Petrial matrix rank exactly k.
Pick v ∈ B \ A and set A' = A ∪ {v}. Adding v decreases the symmetric difference size |A' \ B| + |B \ A'| by 1, so the induction hypothesis applies. Since rank(A') ≤ rank(A) + 1, either rank(A') ≤ k, in which case the induction hypothesis on (A', B) provides the witness, or rank(A') > k ≥ rank(A), in which case rank(A) must equal k, making A the witness.
uses
Finset.card_erase_of_mem,op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_insert_le· obtain ⟨v, hv⟩ := Finset.card_pos.mp (Nat.pos_of_ne_zero hBA_sdiff) have hvB : v ∈ B := (Finset.mem_sdiff.mp hv).1 have hvA : v ∉ A := (Finset.mem_sdiff.mp hv).2 have hstep : ((insert v A) \ B).card + (B \ (insert v A)).card + 1 = (A \ B).card + (B \ A).card := by have h1 : (insert v A) \ B = A \ B := by ext x simp only [Finset.mem_sdiff, Finset.mem_insert] constructor · rintro ⟨h1 | h1, h2⟩ · subst h1; contradiction · exact ⟨h1, h2⟩ · rintro ⟨h1, h2⟩ exact ⟨Or.inr h1, h2⟩ have h2 : B \ (insert v A) = (B \ A).erase v := by ext x simp only [Finset.mem_sdiff, Finset.mem_insert, Finset.mem_erase] tauto rw [h1, h2] have hcard := Finset.card_erase_of_mem hv have hpos : 1 ≤ (B \ A).card := Finset.card_pos.mpr ⟨v, hv⟩ omega have hlt : ((insert v A) \ B).card + (B \ (insert v A)).card < n := by omega have hle_ins := op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_insert_le G A v hvA by_cases hk_ins : (petrial_matrix G (insert v A)).rank ≤ k · exact ih _ hlt (insert v A) B rfl k hk_ins hB · have : (petrial_matrix G A).rank = k := by omega exact ⟨A, this⟩
When A \ B is non-empty, there exists a vertex subset C with Petrial matrix rank exactly k.
Pick v ∈ A \ B and set A' = A \ {v}. Erasing v decreases the symmetric difference size by 1. Since rank(A') ≤ rank(A) + 1, either rank(A') ≤ k and the induction hypothesis on (A', B) yields the witness, or rank(A) = k and A is the witness.
uses
Finset.card_erase_of_mem,op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le'· obtain ⟨v, hv⟩ := Finset.card_pos.mp (Nat.pos_of_ne_zero hAB_sdiff) have hvA : v ∈ A := (Finset.mem_sdiff.mp hv).1 have hvB : v ∉ B := (Finset.mem_sdiff.mp hv).2 have hstep : ((A.erase v) \ B).card + (B \ (A.erase v)).card + 1 = (A \ B).card + (B \ A).card := by have h1 : (A.erase v) \ B = (A \ B).erase v := by ext x simp only [Finset.mem_sdiff, Finset.mem_erase] tauto have h2 : B \ (A.erase v) = B \ A := by ext x simp only [Finset.mem_sdiff, Finset.mem_erase] constructor · rintro ⟨hxB, hx⟩ refine ⟨hxB, ?_⟩ rintro hxA exact hx ⟨fun hxv => hvB (hxv ▸ hxB), hxA⟩ · rintro ⟨hxB, hxA⟩ exact ⟨hxB, fun ⟨_, h⟩ => hxA h⟩ rw [h1, h2] have hcard := Finset.card_erase_of_mem hv have hpos : 1 ≤ (A \ B).card := Finset.card_pos.mpr ⟨v, hv⟩ omega have hlt : ((A.erase v) \ B).card + (B \ (A.erase v)).card < n := by omega have hle_erase := op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le' G A v hvA by_cases hk_erase : (petrial_matrix G (A.erase v)).rank ≤ k · exact ih _ hlt (A.erase v) B rfl k hk_erase hB · have : (petrial_matrix G A).rank = k := by omega exact ⟨A, this⟩
If there exist i < k and j > k with non-zero Petrial coefficients, then the k-th Petrial coefficient is also non-zero.
Non-vanishing of the i-th and j-th coefficients yields subsets Fi and Fj with Petrial matrix ranks i and j. By the intermediate rank theorem, there exists a subset Fk whose Petrial matrix rank is exactly k. Hence the set of subsets with Petrial rank k is non-empty, so petrial_coeff G k ≠ 0.
uses
op_1239_at_most_two_nonzero_coeffs_log_concave_exists_intermediate_rankintro k hi hj obtain ⟨i, hik, hic⟩ := hi obtain ⟨j, hkj, hjc⟩ := hj obtain ⟨Fi, hFi⟩ := Finset.card_ne_zero.mp hic simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hFi obtain ⟨Fj, hFj⟩ := Finset.card_ne_zero.mp hjc simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hFj have hFi_rank : (petrial_matrix G Fi).rank ≤ k := by rw [hFi]; omega have hFj_rank : k ≤ (petrial_matrix G Fj).rank := by rw [hFj]; omega obtain ⟨Fk, hFk⟩ := op_1239_at_most_two_nonzero_coeffs_log_concave_exists_intermediate_rank G ((Fi \ Fj).card + (Fj \ Fi).card) Fi Fj rfl k hFi_rank hFj_rank have hkc : petrial_coeff G k ≠ 0 := by unfold petrial_coeff intro h0 have hmem : Fk ∈ (Finset.univ : Finset (Finset V)).filter (fun F' => (petrial_matrix G F').rank = k) := by simp [hFk] have : (Finset.univ.filter (fun F' => (petrial_matrix G F').rank = k)).card ≠ 0 := Finset.card_ne_zero.mpr ⟨Fk, hmem⟩ exact this h0
Graph G satisfies petrial_log_concave G because the premise of the log-concavity condition is vacuous.
The matrix ranks are bounded by the number of vertices. If there were indices i < k < j with non-zero coefficients, then all three would belong to the support S of the Petrial polynomial. Since i < k < j, the set {i, k, j} has cardinality 3, so |S| ≥ 3, contradicting the hypothesis |S| ≤ 2. Hence no such indices can exist and the implication holds vacuously.
uses
Matrix.rank_le_card_width,Finset.card_insert_of_notMem,Finset.card_singleton,Finset.card_le_cardhave hi_le : i ≤ Fintype.card V := by have := Matrix.rank_le_card_width (petrial_matrix G Fi) omega have hj_le : j ≤ Fintype.card V := by have := Matrix.rank_le_card_width (petrial_matrix G Fj) omega let S := (Finset.range (Fintype.card V + 1)).filter (fun m => petrial_coeff G m ≠ 0) have hi_in : i ∈ S := by simp only [Finset.mem_filter, Finset.mem_range, S] exact ⟨by omega, hic⟩ have hj_in : j ∈ S := by simp only [Finset.mem_filter, Finset.mem_range, S] exact ⟨by omega, hjc⟩ have hk_in : k ∈ S := by simp only [Finset.mem_filter, Finset.mem_range, S] exact ⟨by omega, hkc⟩ have h_sub : {i, k, j} ⊆ S := by intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl | rfl · exact hi_in · exact hk_in · exact hj_in have h_card_three : ({i, k, j} : Finset ℕ).card = 3 := by rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] · simp only [Finset.mem_singleton] omega · simp only [Finset.mem_insert, Finset.mem_singleton] rintro (rfl | rfl) <;> omega have h_le := Finset.card_le_card h_sub rw [h_card_three] at h_le change S.card ≤ 2 at h exfalso omega
Matrix.mulVecLin_add- The linear map associated with the sum of two matrices is the sum of their individual linear maps.
LinearMap.range_add_le- The range of the sum of two linear maps is contained in the supremum (span) of their individual ranges.
Submodule.finrank_mono- If one submodule is contained in another, its dimension (finrank) is at most the dimension of the containing submodule.
Submodule.finrank_add_le_finrank_add_finrank- The dimension of the sum (supremum) of two submodules is at most the sum of their individual dimensions.
Matrix.rank_diagonal- The rank of a diagonal matrix equals the number of non-zero entries on its diagonal.
Fintype.card_subtype- The cardinality of a subtype defined by a predicate equals the cardinality of the finset of elements satisfying the predicate.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is at most the cardinality of the superset.
Finset.card_singleton- A singleton set has cardinality 1.
Matrix.add_apply- The (i, j)-th entry of the sum of two matrices is the sum of their (i, j)-th entries.
Matrix.diagonal_apply- The (i, j)-th entry of a diagonal matrix is the diagonal element if i = j and 0 otherwise.
Finset.mem_insert- An element belongs to the insertion of an element into a set if and only if it equals the inserted element or belongs to the original set.
op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_insert- Adding a vertex v ∉ F to F changes the Petrial matrix by adding a diagonal matrix with 1 at (v, v) and 0 elsewhere.
op_1239_at_most_two_nonzero_coeffs_log_concave_matrix_rank_add_le- The rank of the sum of two matrices is at most the sum of their individual ranks.
op_1239_at_most_two_nonzero_coeffs_log_concave_rank_single_diag_le- A diagonal matrix with at most one non-zero entry on the diagonal has rank at most 1.
op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_remove- Over ℤ/2ℤ, the Petrial matrix of F equals the Petrial matrix of F ∪ {v} plus the diagonal matrix with 1 at (v, v).
Finset.insert_erase- Inserting an element into a finite set from which it was removed recovers the original set.
op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le- Removing a vertex from F ∪ {v} changes the rank of the Petrial matrix by at most 1.
Nat.strong_induction_on- The principle of strong mathematical induction on ℕ.
Finset.card_eq_zero- A finite set has cardinality zero if and only if it is empty.
Finset.sdiff_eq_empty_iff_subset- The difference of two sets is empty if and only if the first is a subset of the second.
Finset.Subset.antisymm- If two finite sets are subsets of each other, they are equal.
Finset.card_erase_of_mem- Removing an element from a finite set containing it decreases its cardinality by 1.
op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_insert_le- Inserting a vertex into a vertex subset increases the rank of the Petrial matrix by at most 1.
op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le'- Erasing a vertex from a vertex subset increases the rank of the Petrial matrix by at most 1.
op_1239_at_most_two_nonzero_coeffs_log_concave_exists_intermediate_rank- For any two vertex subsets, every integer between their Petrial matrix ranks is realized as the rank of some intermediate vertex subset.
Matrix.rank_le_card_width- The rank of a matrix is at most the number of its columns.
Finset.card_insert_of_notMem- Inserting an element into a finite set that does not contain it increases its cardinality by 1.
- The property petrial_log_concave G is defined as an implication: whenever there exist indices i < k and j > k with non-zero Petrial coefficients, the inequality petrial_coeff G (k - 1) * petrial_coeff G (k + 1) ≤ petrial_coeff G k ^ 2 must hold. Because the intermediate value theorem establishes that any rank between two realizable ranks is also realizable, having two non-zero coefficients separated by an index k forces the k-th coefficient to be non-zero as well, yielding at least three non-zero coefficients. Consequently, if a graph has at most two non-zero coefficients, the premise of log-concavity cannot be satisfied, so the property holds vacuously by contradiction.
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.
lemma op_1239_at_most_two_nonzero_coeffs_log_concave_matrix_rank_add_le {m n : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n] {K : Type*} [Field K] (A B : Matrix m n K) : (A + B).rank ≤ A.rank + B.rank := by unfold Matrix.rank rw [Matrix.mulVecLin_add] have hle : LinearMap.range (A.mulVecLin + B.mulVecLin) ≤ LinearMap.range A.mulVecLin ⊔ LinearMap.range B.mulVecLin := LinearMap.range_add_le _ _ have h1 := Submodule.finrank_mono hle have h2 := Submodule.finrank_add_le_finrank_add_finrank (LinearMap.range A.mulVecLin) (LinearMap.range B.mulVecLin) omegalemma op_1239_at_most_two_nonzero_coeffs_log_concave_rank_single_diag_le {V : Type*} [Fintype V] [DecidableEq V] (v : V) : (Matrix.diagonal (fun w => if w = v then (1 : ZMod 2) else 0)).rank ≤ 1 := by rw [Matrix.rank_diagonal] rw [Fintype.card_subtype] have : (Finset.univ.filter (fun w => (if w = v then (1 : ZMod 2) else 0) ≠ 0)) ⊆ {v} := by intro w hw simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hw split_ifs at hw with h · exact Finset.mem_singleton.mpr h · contradiction have hsub := Finset.card_le_card this simp only [Finset.card_singleton] at hsub exact hsublemma op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_insert {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (F : Finset V) (v : V) (hv : v ∉ F) : petrial_matrix G (insert v F) = petrial_matrix G F + Matrix.diagonal (fun w => if w = v then (1 : ZMod 2) else 0) := by unfold petrial_matrix ext i j simp only [Matrix.add_apply, Matrix.diagonal_apply, Finset.mem_insert] by_cases hij : i = j · subst hij by_cases hiv : i = v · subst hiv simp [hv] · simp [hiv] · simp [hij]lemma op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_remove {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (F : Finset V) (v : V) (hv : v ∉ F) : petrial_matrix G F = petrial_matrix G (insert v F) + Matrix.diagonal (fun w => if w = v then (1 : ZMod 2) else 0) := by unfold petrial_matrix ext i j simp only [Matrix.add_apply, Matrix.diagonal_apply, Finset.mem_insert] by_cases hij : i = j · subst hij by_cases hiv : i = v · subst hiv have : (1 : ZMod 2) + 1 = 0 := rfl simp [hv, this] · simp [hiv] · simp [hij]lemma op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_insert_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (F : Finset V) (v : V) (hv : v ∉ F) : (petrial_matrix G (insert v F)).rank ≤ (petrial_matrix G F).rank + 1 := by rw [op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_insert G F v hv] have := op_1239_at_most_two_nonzero_coeffs_log_concave_matrix_rank_add_le (petrial_matrix G F) (Matrix.diagonal (fun w => if w = v then (1 : ZMod 2) else 0)) have h1 := op_1239_at_most_two_nonzero_coeffs_log_concave_rank_single_diag_le v omegalemma op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (F : Finset V) (v : V) (hv : v ∉ F) : (petrial_matrix G F).rank ≤ (petrial_matrix G (insert v F)).rank + 1 := by rw [op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_remove G F v hv] have := op_1239_at_most_two_nonzero_coeffs_log_concave_matrix_rank_add_le (petrial_matrix G (insert v F)) (Matrix.diagonal (fun w => if w = v then (1 : ZMod 2) else 0)) have h1 := op_1239_at_most_two_nonzero_coeffs_log_concave_rank_single_diag_le v omegalemma op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le' {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (A : Finset V) (v : V) (hv : v ∈ A) : (petrial_matrix G (A.erase v)).rank ≤ (petrial_matrix G A).rank + 1 := by have hnot : v ∉ A.erase v := by simp have hins : insert v (A.erase v) = A := Finset.insert_erase hv have := op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le G (A.erase v) v hnot rwa [hins] at thislemma op_1239_at_most_two_nonzero_coeffs_log_concave_exists_intermediate_rank {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : ∀ (n : ℕ) (A B : Finset V), (A \ B).card + (B \ A).card = n → ∀ k : ℕ, (petrial_matrix G A).rank ≤ k → k ≤ (petrial_matrix G B).rank → ∃ C : Finset V, (petrial_matrix G C).rank = k := by intro n induction' n using Nat.strong_induction_on with n ih intro A B hn k hA hB by_cases hAB_sdiff : (A \ B).card = 0 · by_cases hBA_sdiff : (B \ A).card = 0 · have h_eq : A = B := by rw [Finset.card_eq_zero, Finset.sdiff_eq_empty_iff_subset] at hAB_sdiff hBA_sdiff exact Finset.Subset.antisymm hAB_sdiff hBA_sdiff subst h_eq exact ⟨A, by omega⟩ · obtain ⟨v, hv⟩ := Finset.card_pos.mp (Nat.pos_of_ne_zero hBA_sdiff) have hvB : v ∈ B := (Finset.mem_sdiff.mp hv).1 have hvA : v ∉ A := (Finset.mem_sdiff.mp hv).2 have hstep : ((insert v A) \ B).card + (B \ (insert v A)).card + 1 = (A \ B).card + (B \ A).card := by have h1 : (insert v A) \ B = A \ B := by ext x simp only [Finset.mem_sdiff, Finset.mem_insert] constructor · rintro ⟨h1 | h1, h2⟩ · subst h1; contradiction · exact ⟨h1, h2⟩ · rintro ⟨h1, h2⟩ exact ⟨Or.inr h1, h2⟩ have h2 : B \ (insert v A) = (B \ A).erase v := by ext x simp only [Finset.mem_sdiff, Finset.mem_insert, Finset.mem_erase] tauto rw [h1, h2] have hcard := Finset.card_erase_of_mem hv have hpos : 1 ≤ (B \ A).card := Finset.card_pos.mpr ⟨v, hv⟩ omega have hlt : ((insert v A) \ B).card + (B \ (insert v A)).card < n := by omega have hle_ins := op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_insert_le G A v hvA by_cases hk_ins : (petrial_matrix G (insert v A)).rank ≤ k · exact ih _ hlt (insert v A) B rfl k hk_ins hB · have : (petrial_matrix G A).rank = k := by omega exact ⟨A, this⟩ · obtain ⟨v, hv⟩ := Finset.card_pos.mp (Nat.pos_of_ne_zero hAB_sdiff) have hvA : v ∈ A := (Finset.mem_sdiff.mp hv).1 have hvB : v ∉ B := (Finset.mem_sdiff.mp hv).2 have hstep : ((A.erase v) \ B).card + (B \ (A.erase v)).card + 1 = (A \ B).card + (B \ A).card := by have h1 : (A.erase v) \ B = (A \ B).erase v := by ext x simp only [Finset.mem_sdiff, Finset.mem_erase] tauto have h2 : B \ (A.erase v) = B \ A := by ext x simp only [Finset.mem_sdiff, Finset.mem_erase] constructor · rintro ⟨hxB, hx⟩ refine ⟨hxB, ?_⟩ rintro hxA exact hx ⟨fun hxv => hvB (hxv ▸ hxB), hxA⟩ · rintro ⟨hxB, hxA⟩ exact ⟨hxB, fun ⟨_, h⟩ => hxA h⟩ rw [h1, h2] have hcard := Finset.card_erase_of_mem hv have hpos : 1 ≤ (A \ B).card := Finset.card_pos.mpr ⟨v, hv⟩ omega have hlt : ((A.erase v) \ B).card + (B \ (A.erase v)).card < n := by omega have hle_erase := op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le' G A v hvA by_cases hk_erase : (petrial_matrix G (A.erase v)).rank ≤ k · exact ih _ hlt (A.erase v) B rfl k hk_erase hB · have : (petrial_matrix G A).rank = k := by omega exact ⟨A, this⟩/-- Graphs with at most two nonzero Petrial coefficients have log-concave partial Petrial polynomials. -/theorem op_1239_at_most_two_nonzero_coeffs_log_concave {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (h : ((Finset.range (Fintype.card V + 1)).filter (fun k => petrial_coeff G k ≠ 0)).card ≤ 2) : petrial_log_concave G := by intro k hi hj obtain ⟨i, hik, hic⟩ := hi obtain ⟨j, hkj, hjc⟩ := hj obtain ⟨Fi, hFi⟩ := Finset.card_ne_zero.mp hic simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hFi obtain ⟨Fj, hFj⟩ := Finset.card_ne_zero.mp hjc simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hFj have hFi_rank : (petrial_matrix G Fi).rank ≤ k := by rw [hFi]; omega have hFj_rank : k ≤ (petrial_matrix G Fj).rank := by rw [hFj]; omega obtain ⟨Fk, hFk⟩ := op_1239_at_most_two_nonzero_coeffs_log_concave_exists_intermediate_rank G ((Fi \ Fj).card + (Fj \ Fi).card) Fi Fj rfl k hFi_rank hFj_rank have hkc : petrial_coeff G k ≠ 0 := by unfold petrial_coeff intro h0 have hmem : Fk ∈ (Finset.univ : Finset (Finset V)).filter (fun F' => (petrial_matrix G F').rank = k) := by simp [hFk] have : (Finset.univ.filter (fun F' => (petrial_matrix G F').rank = k)).card ≠ 0 := Finset.card_ne_zero.mpr ⟨Fk, hmem⟩ exact this h0 have hi_le : i ≤ Fintype.card V := by have := Matrix.rank_le_card_width (petrial_matrix G Fi) omega have hj_le : j ≤ Fintype.card V := by have := Matrix.rank_le_card_width (petrial_matrix G Fj) omega let S := (Finset.range (Fintype.card V + 1)).filter (fun m => petrial_coeff G m ≠ 0) have hi_in : i ∈ S := by simp only [Finset.mem_filter, Finset.mem_range, S] exact ⟨by omega, hic⟩ have hj_in : j ∈ S := by simp only [Finset.mem_filter, Finset.mem_range, S] exact ⟨by omega, hjc⟩ have hk_in : k ∈ S := by simp only [Finset.mem_filter, Finset.mem_range, S] exact ⟨by omega, hkc⟩ have h_sub : {i, k, j} ⊆ S := by intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl | rfl · exact hi_in · exact hk_in · exact hj_in have h_card_three : ({i, k, j} : Finset ℕ).card = 3 := by rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] · simp only [Finset.mem_singleton] omega · simp only [Finset.mem_insert, Finset.mem_singleton] rintro (rfl | rfl) <;> omega have h_le := Finset.card_le_card h_sub rw [h_card_three] at h_le change S.card ≤ 2 at h exfalso omega