Erdős Problems
Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated

Problem 993

../

claims/: The 2 claim pages of Problem 993, one per claimant's result; the problem's standing derives from them.

Statement. The independent set sequence of any tree or forest is unimodal.

In other words, if ik(G)i_k(G) counts the number of independent sets of vertices of size kk in a graph GG, and TT is any tree or forest, then for some m≥0m\geq 0

i0(T)≤i1(T)≤⋯≤im(T)≥im+1(T)≥im+2(T)≥⋯ .i_{0}(T)\leq i_{1}(T)\leq\cdots\leq i_{m}(T)\geq i_{m+1}(T)\geq i_{m+2}(T)\geq\cdots.

Status. Falsifiable. The label is the site's (FALSIFIABLE on 2026-10-06; page last edited 1 February 2026), and it is a body note, not a standing: a counterexample would be one forest whose sequence is not unimodal, a finite check. Two claims are recorded, neither accepted: Zhang and Li's manuscript, on its claim page, claims the conjecture for every finite forest, revised on 6 October 2026 with Vallier and a Lean development, its first arXiv submission withdrawn before announcement and the revision posted on arXiv on 6 October 2026; Fang, Lu, Nevo, Yao and Zheng's arXiv preprint, on its claim page, claims to prove it for all forests on at least N0N_0 vertices, for an uncomputed N0N_0, with a Lean development. The frontmatter standing is derived from the claim pages: a pending full claim, so claimed.

Source. erdosproblems.com/993, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #993, https://www.erdosproblems.com/993.

References.

  • [AMSE87] Alavi, Yousef and Malde, Paresh J. and Schwenk, Allen J. and Erdős, Paul, The vertex independence sequence of a graph is not constrained. Congr. Numer. (1987), 15-23.
  • [Sc81] Schwenk, Allen J., On unimodal sequences of graphical invariants. J. Combin. Theory Ser. B (1981), 247-250.

Formalization. Author-reported Lean developments are recorded on the claim pages; no build or audit of either by this corpus is recorded. Formal-conjectures had no file ErdosProblems/993.lean on 2026-10-07.

Current assessment

The site's label FALSIFIABLE (2026-10-06) is a body note, not a standing. The compiled source note concerns arbitrary graphs; it gives no tree or forest counterexample. The later literature on the conjecture is linked below and not compiled on this page.

Falsifiability. The site's label records that the conjecture is falsifiable: a single forest whose independence sequence fails to be unimodal refutes it, and the sequence of a given forest is a finite computation. The label says nothing about whether such a forest exists, and the problem's standing is derived from the claim pages, not from the label.

Claims on the site. Two claims, recorded on their claim pages and summarized in the Status paragraph. The partial claim of Fang, Lu, Nevo, Yao and Zheng (claim page) reaches every forest above an existential threshold and leaves the small forests, and so the conjecture itself, open; the full claim of Zhang and Li (claim page) covers every forest, in a manuscript whose authors said on 6 October 2026 that they intend a shorter version. Neither has a referee or a named reviewer, and no build or review of either Lean development is recorded; the developments are described as their READMEs state them. The site labels the problem FALSIFIABLE (2026-10-06), and the page adopts neither claim.

Known Results

Alavi, Malde, Schwenk and Erdős prove that arbitrary graphs can realize every strict ordering of their independent-set counts (1987, printed p. 16). This does not provide a tree or forest counterexample. Their Problem 3 on p. 21 poses that restricted question separately.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (62)
Unimodality for all sufficiently large forestsUnimodality for every finite forestproblems/extremal_graph_theory/E0993/claimsExtremal and Structural Graph Theoryextremal_graph_theory/alavi_1987_vertex_independence_sequence_graph_is_notExample (p. 21): a disjoint union of two unimodal graphs that is not unimodalProblem 3 (p. 21): is the independence sequence of a tree or forest unimodalTheorem (p. 16): every strict ordering of the independent-set counts occursBasit–Galvin: On the independent set sequence of a treeClaim 1.10 (p. 6): (i_k) is ordered log-concave exactly when the average extension counts (e_k) weakly decreaseTheorem 1.3 (p. 2): the independent set sequence of any graph is weakly decreasing from ⌈α(n−1)/(α+n)⌉ to αTheorem 1.4 (p. 3): a.a.s. the independent set sequence of a uniform random labelled tree is weakly decreasing from 0.347nTheorem 1.5 (p. 3): if every maximal independent set has at least λ vertices, i_0 ≤ … ≤ i_⌈λ/2⌉Theorem 1.6 (p. 4): the independent set sequence of a tree is weakly increasing up to ⌈(n−α+1)/4⌉Theorem 1.7 (p. 4): a.a.s. the independent set sequence of a uniform random labelled tree is weakly increasing up to 0.280nBencs: On trees with real rooted independence polynomialCorollary 3.1 (p. 7): stable-path trees of claw-free graphs have real-rooted independence polynomialsProposition 2.7 (p. 7): I(G,x) divides the independence polynomial of a stable-path tree of connected GProposition 3.3 (p. 8): the n-centipede has a real-rooted independence polynomialProposition 3.4 (p. 9): the n-caterpillar has a real-rooted independence polynomialProposition 3.5 (p. 9): Fibonacci trees have real-rooted independence polynomialsTheorem 2.3 (p. 4): the stable-path tree preserves the ratio I(G-u,x)/I(G,x)Galvin: Trees with non log-concave independent set sequencesHeilman: Independent Sets of Random Trees and of Sparse Random GraphsLemma 5.1 (p. 16): summing over independent k-sets the number of vertices not joined to the set gives (k+1) x_{k+1}Theorem 1.17 (p. 5): with probability at least 1 - e^{-cn} a uniform random labelled tree has x_0 < x_1 < ... < x_{floor(0.26543n)}Theorem 1.18 (p. 6): for d >= 10^{10/eps}, G(n,d/n) has independent set counts increasing below beta(1-eps)/2 and decreasing above beta(1+eps)/2Theorem 1.19 (p. 6): ranges of unimodality for the independent set counts of G(n,d/n) when d = 1, 2, eTheorem 1.20 (p. 6): for d >= 10^{10/eps}, a uniform random d-regular graph has independent set counts increasing up to beta(1-eps)/2Kadrawi–Levit: The independence polynomial of trees is not always log-concave starting from order 26Examples on p. 4: two 26-vertex trees whose independence polynomials are not log-concaveLemma 4.2 (p. 13): the 3*,k,k+2 trees have non-log-concave independence polynomials for k ≥ 3Lemma 4.3 (p. 16): the 3*,k,k+3 trees have non-log-concave independence polynomials for k ≥ 4Lemma 4.4 (p. 19): the 3*,k,k trees have non-log-concave independence polynomials for k ≥ 4Theorem 3.2 (p. 6): the 3,k,k+1 trees have non-log-concave independence polynomials for k ≥ 4Theorem 3.3 (p. 9): the 3,k,k+2 trees have non-log-concave independence polynomials for k ≥ 4Levit–Mandrescu: On Unimodality of Independence Polynomials of some Well-Covered TreesConjecture 1.2 (p. 4): independence polynomials of trees are unimodalLemma 2.1 (p. 6): a unimodal polynomial times a polynomial of degree one is unimodalLemma 2.5 (p. 8): replacing the edge cd of an attached P_4 by ac preserves the independence polynomialProposition 4.4 (p. 15): G_{2,4}, alone or edge-joined to claw-free graphs at simplicial vertices, shares its independence polynomial with a claw-free graphTheorem 3.1 (p. 10): every well-covered spider has a unimodal independence polynomial, with an explicit polynomial and unique mode for S_nTheorem 4.2 (p. 14): the centipede W_n has the independence polynomial of a claw-free graph, and it is unimodalTheorem 4.5 (p. 17): the joined centipedes G_{m,n} have unimodal independence polynomialsLevit–Mandrescu: Very well-covered graphs and the unimodality conjectureCorollary 2.7 (p. 8): the stable-set counts of a bipartite graph do not increase from ⌈(2α−1)/3⌉ onCorollary 2.8 (p. 8): the independent-set counts of a tree do not increase from ⌈(2α−1)/3⌉ onTheorem 2.5 (p. 6): independence polynomials of very well-covered graphs rise to ⌈α/2⌉, fall from ⌈(2α−1)/3⌉, and are unimodal for α ≤ 9Li: Unimodality of independence polynomials of two family of treesTheorem 1.4: the independence polynomial of T_{3,m,n} is unimodal for m, n >= 1
Graph