Log-concavity transitions in sums of polynomial powers

Unrefereed research candidate. In one sentence: a tree made of one hub joined to the middles of m three-vertex paths stops having a log-concave independent set sequence exactly when m reaches 16,392, so four is the least diameter at which trees can fail log-concavity, and failures at that diameter can form arbitrarily long runs. The question. An independent set in a network (graph) is a set of nodes no two of which are joined. Counting the independent sets of each size gives the independent set sequence. For trees (networks without cycles) these counts were long expected to rise and then fall smoothly; the precise smoothness property is log-concavity: each count squared is at least the product of its two neighbours. In statistical physics the same numbers describe the hard-core gas, in which particles cannot sit on neighbouring sites. Whether every tree's sequence rises and then falls (unimodality, a question of Alavi, Malde, Schwenk and Erdős from 1987) is still open. What was known. Trees can fail log-concavity: Kadrawi and Levit (2023) gave trees with 26 vertices. Later work gave many failures and long runs of consecutive failures (Galvin; Bautista-Ramos and coauthors; Yu’s runs of order N1/3 in an unrefereed archive). All structured examples have diameter six or eight. Trees of diameter at most three are always log-concave (Galvin and Hilyard, 2018). Results. Let Tm be the tree obtained by joining a hub to the middle vertex of each of m disjoint three-vertex paths (“cherries”); it has 3m+1 vertices and diameter four. (1) The independent set sequence of Tm is log-concave if and only if m ≤ 16,391; T16,392, with 49,177 vertices, fails at exactly one place. (2) For every m from 16,392 to 106, and for all sufficiently large m, the failures form one unbroken block, whose length is (2/log(3/2)) log log m + O(1), about 4.93 log log m; both ends are located to within o(1) by explicit equations. (3) Hence four is the least diameter of a non-log-concave tree, and the least diameter admitting arbitrarily long runs of failures. (4) An exhaustive search finds no non-log-concave tree of diameter four with at most 62 vertices, so the smallest one has between 63 and 49,177 vertices. (5) A general theorem covers the coefficient sequences of (1+x)dm + xP(x)m, where P has only negative real roots, P(0) = 1, leading coefficient at least 1 and P′(0) > d: the failures eventually form one interval of length (2/log r) log log m + O(1), with r = P′(0)/d. How. Counting down from the largest independent sets, the counts split into two parts (hub used or not), each log-concave and each behaving like a Poisson-shaped tail, with rates 2m and 3m. Where the two parts are of equal size their sum behaves like a mixture of two Poisson laws, which is not log-concave over a window of about 4.93 log log m sizes. An exact curvature identity locates the window, and Newton’s inequalities exclude failures elsewhere. The threshold and the one-block statement up to 106 combine explicit estimates with exact integer computation. Limits. The runs are short (17 even at m = 1040), far shorter than Yu’s; the failures sit near the top of the sequence, so nothing follows about unimodality; within this hub construction the cherry is the only module the general theorem covers; the exact threshold and the one-block statement up to 106 are computer-assisted (exact integer arithmetic, scripts included); the general thresholds are not effective. Contents. The paper (LaTeX source and PDF) with its figure; four standard-library Python scripts with recorded outputs (exact checks of the tree polynomial and the failure sets; checks of the general theorem; the threshold certificate, about 12 minutes on one core; the exhaustive diameter-four search to 62 vertices, about 2 minutes); the figure script; the bibliography from registry records; the novelty report, target statement and fingerprints; a machine-readable index; a research-gate record; a rating-free review summary; a replay receipt and SHA-256 sums. Assurance. Theorems 2.1 and 2.3 have written proofs; Theorem 2.4 and Proposition 2.6 are computer-assisted proofs in exact integer arithmetic. Internal AI-assisted review only (five reviewer roles, an adversarial review and audit by a second AI model, clean replays, a re-review and a proof audit): not peer review, independent reproduction or formal verification. Creator: Anonymous. Text and data CC0-1.0; code MIT.

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-15
DOI
https://doi.org/10.5281/zenodo.24238468
Primary Topic
Advanced Combinatorial Mathematics
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Log-concavity transitions in sums of polynomial powers

Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
preprint

Log-concavity transitions in sums of polynomial powers

preprint en

Abstract

Unrefereed research candidate. In one sentence: a tree made of one hub joined to the middles of m three-vertex paths stops having a log-concave independent set sequence exactly when m reaches 16,392, so four is the least diameter at which trees can fail log-concavity, and failures at that diameter can form arbitrarily long runs. The question. An independent set in a network (graph) is a set of nodes no two of which are joined. Counting the independent sets of each size gives the independent set sequence. For trees (networks without cycles) these counts were long expected to rise and then fall smoothly; the precise smoothness property is log-concavity: each count squared is at least the product of its two neighbours. In statistical physics the same numbers describe the hard-core gas, in which particles cannot sit on neighbouring sites. Whether every tree's sequence rises and then falls (unimodality, a question of Alavi, Malde, Schwenk and Erdős from 1987) is still open. What was known. Trees can fail log-concavity: Kadrawi and Levit (2023) gave trees with 26 vertices. Later work gave many failures and long runs of consecutive failures (Galvin; Bautista-Ramos and coauthors; Yu’s runs of order N1/3 in an unrefereed archive). All structured examples have diameter six or eight. Trees of diameter at most three are always log-concave (Galvin and Hilyard, 2018). Results. Let Tm be the tree obtained by joining a hub to the middle vertex of each of m disjoint three-vertex paths (“cherries”); it has 3m+1 vertices and diameter four. (1) The independent set sequence of Tm is log-concave if and only if m ≤ 16,391; T16,392, with 49,177 vertices, fails at exactly one place. (2) For every m from 16,392 to 106, and for all sufficiently large m, the failures form one unbroken block, whose length is (2/log(3/2)) log log m + O(1), about 4.93 log log m; both ends are located to within o(1) by explicit equations. (3) Hence four is the least diameter of a non-log-concave tree, and the least diameter admitting arbitrarily long runs of failures. (4) An exhaustive search finds no non-log-concave tree of diameter four with at most 62 vertices, so the smallest one has between 63 and 49,177 vertices. (5) A general theorem covers the coefficient sequences of (1+x)dm + xP(x)m, where P has only negative real roots, P(0) = 1, leading coefficient at least 1 and P′(0) > d: the failures eventually form one interval of length (2/log r) log log m + O(1), with r = P′(0)/d. How. Counting down from the largest independent sets, the counts split into two parts (hub used or not), each log-concave and each behaving like a Poisson-shaped tail, with rates 2m and 3m. Where the two parts are of equal size their sum behaves like a mixture of two Poisson laws, which is not log-concave over a window of about 4.93 log log m sizes. An exact curvature identity locates the window, and Newton’s inequalities exclude failures elsewhere. The threshold and the one-block statement up to 106 combine explicit estimates with exact integer computation. Limits. The runs are short (17 even at m = 1040), far shorter than Yu’s; the failures sit near the top of the sequence, so nothing follows about unimodality; within this hub construction the cherry is the only module the general theorem covers; the exact threshold and the one-block statement up to 106 are computer-assisted (exact integer arithmetic, scripts included); the general thresholds are not effective. Contents. The paper (LaTeX source and PDF) with its figure; four standard-library Python scripts with recorded outputs (exact checks of the tree polynomial and the failure sets; checks of the general theorem; the threshold certificate, about 12 minutes on one core; the exhaustive diameter-four search to 62 vertices, about 2 minutes); the figure script; the bibliography from registry records; the novelty report, target statement and fingerprints; a machine-readable index; a research-gate record; a rating-free review summary; a replay receipt and SHA-256 sums. Assurance. Theorems 2.1 and 2.3 have written proofs; Theorem 2.4 and Proposition 2.6 are computer-assisted proofs in exact integer arithmetic. Internal AI-assisted review only (five reviewer roles, an adversarial review and audit by a second AI model, clean replays, a re-review and a proof audit): not peer review, independent reproduction or formal verification. Creator: Anonymous. Text and data CC0-1.0; code MIT.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon