Take any tree – the graph kind, dots and lines with no cycles – and count its independent sets by size. The counts always seem to climb to a peak and then fall: a single hill, never a valley. Erdős and his coauthors conjectured in 1987 that this holds for every tree. Nobody has proved it. Nobody has found a valley. Every one of the 8,691,747,673 trees with up to 29 vertices has been checked.
No math background needed. Deeper layers open up when you want them. Sibling page: The First Descent.
One kind of object, one sequence, and one thing that has never been seen.
An independent set is a collection of vertices with no two joined by an edge – a committee with no two members who are neighbours. The three gold vertices form one of size 3.
Count them by size: i0 = 1 (the empty set), i1 = the number of vertices, i2, i3, … up to the largest possible size α.
List the counts in order: 1, n, i2, i3, … For every tree anyone has ever checked, this sequence is unimodal: it rises, tops out, and falls. No dip on the way down.
The 1987 conjecture of Alavi, Malde, Schwenk, and Erdős says it always is – Erdős problem #993.
A valley – a dip that rises again – would disprove the conjecture. Graphs in general do this freely: Alavi, Malde, Schwenk, and Erdős showed the sequence of a general graph can realize any prescribed shape. The bars above are real: a 26-vertex graph whose sequence 1, 26, 15, 20, 15, 6, 1 drops to 15, climbs back to 20, and drops again.
But that graph has cycles. No tree has ever produced a valley. Your job downstairs: try.
Build a tree; the sequence updates live, in exact integer arithmetic. Your score is the near-miss ratio nm: after the sequence first turns downward, the largest later step-up ratio ik+1/ik. Push it toward 1. Crossing 1 is a valley – a counterexample to a 39-year-old conjecture.
Tap a vertex to select it (gold ring), then grow or prune.
Same open problem, three altitudes. Switch whenever you like – nothing below depends on reading the harder ones.
A tree is the simplest kind of network: everything connected, no loops. An independent set is a selection of its vertices with no two adjacent. Count the selections of each size and line the counts up. For every tree ever examined, the line-up climbs to a single peak and descends – like a hill seen side-on.
In 1987, Alavi, Malde, Schwenk, and Erdős proved that networks in general obey no such law: with cycles allowed, you can make the counts zigzag however you please. Trees looked different. They conjectured that a tree's counts always form a single hill. That conjecture is Erdős problem #993, and it is still open.
Here is what makes it tantalizing. A stronger regularity – log-concavity, which says the sequence has no abrupt flattening anywhere – was long believed plausible for trees too, and it is false: in 2025, Kadrawi and Levit found exactly two trees on 26 vertices that break it (both drawn in the field guide below). Nineteen more break it at 28 vertices, and infinite families are now known. The fence between "perfectly regular" and "single hill" is real, and trees walk right up to it. They just never seem to cross.
Computers have checked every tree with up to 29 vertices – 8,691,747,673 of them. No valley. Special families (paths, centipedes, regular caterpillars, spiders, Fibonacci trees) are proved safe. And the best "near-miss" trees – bushy stars with a few long arms – get their post-peak rebound ratio up to 0.9959 without ever touching 1.
The game upstairs puts you in the hunt: build a tree, watch its hill, and try to dent it.
For a tree T, write ik(T) for the number of independent sets of size k, and α(T) for the largest size. The independence polynomial is I(T; x) = Σ ik xk, with i0 = 1.
Unimodal means: rises to a peak, then falls, ties allowed. The stronger property of log-concavity – ik² ≥ ik−1 ik+1 at every interior k – implies unimodality, and for decades every tree tested had it. It fails: Kadrawi and Levit (2025) found exactly two trees on n = 26 (both failing at k = 13, worst ratio i12i14/i13² = 1.145), none exist at n = 27, and 19 exist at n = 28. Infinite non-log-concave families are now known (Galvin 2025; Bautista-Ramos et al.), including failures at several consecutive indices – yet none of these trees loses unimodality.
What is proved safe: paths and centipedes (AMSE 1987), regular caterpillars (Galvin–Hilyard 2018), Fibonacci trees (Bencs 2018), and all spiders, whose independence polynomials are log-concave (Li–Xie–Zhuang 2025), which covers brooms; further families containing the Kadrawi–Levit examples were proved unimodal in 2026. Levit and Mandrescu (2006) showed the tail is always strictly decreasing from k ≥ ⌈(2α−1)/3⌉ on, so any valley must sit in roughly the first two-thirds of the sequence. For a uniformly random labelled tree, Basit and Galvin (2020) proved the initial ≈49.5% of the sequence is increasing and the final ≈38.8% decreasing, asymptotically almost surely.
To measure how close a tree gets to a valley, the companion paper uses the near-miss ratio:
Unimodality says nm ≤ 1; a valley is exactly nm > 1. Exhaustive search puts the best near-miss among all trees through n = 28 at nm ≈ 0.8571 (reached at n = 27). Beyond the exhaustive range, the empirically extremal family is the multi-arm star M(s; a1, …, ak): a hub with s pendant leaves and k short paths. The best known configurations reach nm = 0.9437 at n = 75, 0.9575 at n = 100, 0.9792 at n = 200, and 0.9959 at n = 1000 – creeping toward the wall like 1 − C/s without crossing.
The companion paper attacks the conjecture on three fronts; none closes it, and the paper says so plainly.
Front one: push the mean below the danger zone. For a class of reduced trees (those with at most one "private leaf" per support vertex), a decimation identity plus Steiner peeling on a compensation function proves the mean independent-set size satisfies μ(T) < n/3. If tree independence sequences also satisfied the mode–mean localization mode ≤ ⌈μ⌉, this would control where the peak sits for that whole class. That localization is exactly what Darroch proved in 1964 for Poisson–binomial distributions – the bridge to this page's sibling, The First Descent – but for trees it remains a conjecture, verified for all 931,596 reduced trees on up to 23 vertices and for the log-concavity-breaking trees individually.
Front two: squeeze the shape of a minimal counterexample. A subdivision–contraction identity shows – conditional on a conjectured Edge Contraction Mode Stability property and a tail condition verified through n ≤ 19 – that a minimal counterexample would have to be homeomorphically irreducible: no vertex of degree 2 anywhere. Conditional, and labelled as such in the paper's dependency map.
Front three: brute force and extremal reconnaissance. Exhaustive verification of all 8,691,747,673 trees on n ≤ 29 (the larger orders sharded across 1024 cloud workers), with log-concavity and near-miss audits through n = 28. An evolutionary optimizer over tree space (leaf relocation, prune-and-regraft, pendant concentration) converged on multi-arm stars as the near-miss champions, and a leaf-attachment theorem explains their approach rate 1 − C/s, 4 ≤ C ≤ 8. The valley, if it exists, lives somewhere none of this reaches: bigger than 29 vertices, outside every proved-safe family, and past the frontier every tested family obeys.
Reference: Brett Reynolds, “Mean bounds, structural reductions, and exhaustive verification for tree independence polynomial unimodality” (2026), doi:10.5281/zenodo.19100781.
Real specimens, drawn from the data – not sketches. Load any of them into the workshop and poke.
Three bushy hubs sharing a centre vertex, every spoke ending in a pendant pair. Its sequence ends …, 18683, 2979, 51, 1 – and 51² = 2601 < 2979 × 1, so log-concavity fails at k = 13. The hill itself never dips.
The same three-hub recipe with one spoke rewired. Its sequence ends …, 15498, 2372, 48, 1, and 48² = 2304 < 2372 × 1: a second, gentler failure at k = 13. These two are the only log-concavity breakers among all 279,793,450 trees on 26 vertices.
Sixty-six leaves on one hub plus arms of length 6 and 2: the best near-miss known at 75 vertices, nm = 0.9437. Every champion the evolutionary optimizer ever found is a variation on this dandelion-with-stalks shape.
All 8,691,747,673 trees on up to 29 vertices have been checked in exact arithmetic: not one valley.
Log-concavity fails for exactly two trees at n = 26, none at 27, nineteen at 28 – and for infinite families beyond. Unimodality survived every one of those breaks.
Paths, centipedes, regular caterpillars, spiders (hence brooms), Fibonacci trees, and the families containing the known log-concavity breakers all have proofs. The tail of every tree's sequence is provably decreasing from about two-thirds of the way in.
Bushy multi-arm stars push the rebound to nm = 1 − C/s + O(1/s²) with 4 ≤ C ≤ 8: as close to the wall as you like, never through it. Best known: 0.9959 at n = 1000.
No proof handles all trees. A valley, if one exists, needs more than 29 vertices and a shape outside every family listed above. That is exactly the space the workshop upstairs lets you wander.
The near-miss ratio nm of the best known trees, by vertex count. A single tree with nm > 1 ends the conjecture.
Positions to scale on [0.8, 1]. Every dot is a multi-arm star; each family obeys nm = 1 − C/s with C ≥ 4, so the gap closes like C/s and never vanishes. (This page computes your trees in exact integer arithmetic – a valley shown here would be real. Verify independently anyway.)
Log-concavity implies unimodality, so for decades the safe bet was that trees had both. The 2025 discovery that log-concavity fails – first at exactly n = 26 – while unimodality keeps holding is the sharpest hint that #993 sits in genuinely delicate territory. Load the Kadrawi 26 preset and watch the ratio dots stumble without ever climbing back over 1.
Chasing the mode–mean question for trees leads straight to Darroch's 1964 localization for coin-flip sums – and from there this project proved a new variance-scaled Turán inequality for Poisson–binomial distributions. That result has its own playable page: The First Descent.
Independent-set counts are the tree case of a lattice-gas partition function: selections of non-adjacent sites, weighted by size. The same sequences appear as Merrifield–Simmons indices in chemistry and Fibonacci-style counts in combinatorics – paths give exactly the Fibonacci numbers.