AFTD Auto-Formalizing Theoretical Domains

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

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⟩
See it in the graphDiscuss this resultChallenge it