op_1239_subcubic_tree_counterexample
theoremverifiedoriginal
There exists a tree on Fin 36 with maximum degree at most three whose partial Petrial polynomial is not log-concave.
Statement
theorem op_1239_subcubic_tree_counterexample : ∃ G : SimpleGraph (Fin 36), letI : DecidableRel G.Adj := Classical.decRel _; G.IsTree ∧ G.maxDegree ≤ 3 ∧ ¬ petrial_log_concave G- Related work
- Candidate for OP-1239; computations 28328 and 28332 checks the standard leaf-deletion recurrence from arXiv:2611.07503, Lemma 1.
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- op_1239_candidate36_treeThe graph op_1239_candidate36 is a tree.
- op_1239_candidate36_max_degreeThe maximum degree of op_1239_candidate36 is at most 3.
- op_1239_candidate36_not_log_concaveThe partial Petrial polynomial of op_1239_candidate36 is not log-concave.
- 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…
- op_1239_candidate36The simple graph on the 36 vertices Fin 36 with the 35 undirected edges listed in its definition.
Read back from the Lean
There exists a simple graph $G$ on the vertex set $\mathrm{Fin}(36)$ (having 36 vertices) such that:
1. $G$ is a tree (G.IsTree),
2. the maximum degree of $G$ is at most 3 (G.maxDegree ≤ 3), and
3. $G$ is not petrial log-concave (¬ petrial_log_concave G), meaning that the sequence of coefficients $c_k = \text{petrial\_coeff}(G, k)$ fails log-concavity: there is some $k \in \mathbb{N}$ for which there exist indices $i < k$ with $c_i \neq 0$ and $j > k$ with $c_j \neq 0$, but $c_{k-1} \cdot c_{k+1} > c_k^2$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
theorem op_1239_subcubic_tree_counterexample : ∃ G : SimpleGraph (Fin 36), letI : DecidableRel G.Adj := Classical.decRel _; G.IsTree ∧ G.maxDegree ≤ 3 ∧ ¬ petrial_log_concave G := by exact ⟨op_1239_candidate36, op_1239_candidate36_tree, op_1239_candidate36_max_degree, op_1239_candidate36_not_log_concave⟩