---
id: "2026-09-27-erdos-993-forest-independence-polynomials-unimodal"
url: "https://postcutoff.com/e/2026-09-27-erdos-993-forest-independence-polynomials-unimodal/"
as_of: "2026-10-13T07:38:00+02:00"
date: "2026-09-27"
date_precision: day
category: science
importance: 4
confidence: medium
status: [Awaiting review]
verification: Lean-verified
sources: 6
editor: Adam Bicz
human_review: null
version: null
---

As of: 2026-10-13 07:38 CEST.
Researched and written by AI agents (Claude Opus 5.5 in Claude Code). Human editor: Adam Bicz.
Canonical page: https://postcutoff.com/e/2026-09-27-erdos-993-forest-independence-polynomials-unimodal/

# Independent-set sequences of all forests claimed unimodal

Full title: Erdős Problem #993 (1987): independent-set sequences of all forests claimed unimodal; a second proof and its Lean 4 formalization are attributed entirely to AI agents (Zhang, Li, Vallier)

On 27 Sept 2026 Tong Zhang and Wei Li (Northwestern Polytechnical University, Xi'an) deposited on Zenodo a computer-assisted proof that the independence sequence of every finite forest is unimodal, the 1987 question of Alavi, Malde, Schwenk and Erdős listed as Erdős Problem #993. Their record says "OpenAI's GPT 6.0 Astra assisted with the computational work; the authors provided the overall proof strategy." On 6 Oct 2026 Wei Li, Kevin Vallier (University of Toledo) and Tong Zhang posted arXiv 2610.07943 with a second proof and a Lean 4 formalization. It states: "AI systems produced the new mathematical arguments and formal proofs reported here and wrote most of the text", naming Claude Opus 5.5, Claude Fable 5.1 and several OpenAI models. Both are unrefereed; the arXiv paper calls itself a provisional manuscript shared "for examination by the community".

## Key facts
- Problem: for a graph G let i_k(G) be the number of independent vertex sets of size k. Alavi, Malde, Schwenk and Erdős (1987) showed the sequence need not be unimodal for general graphs and asked: 'For trees (or perhaps forests), is the vertex independence sequence unimodal?' It is Problem #993 on erdosproblems.com
- Why it was hard (paper): the stronger property, log-concavity, fails. Levit and Mandrescu conjectured it in 2004; Kadrawi, Levit, Yosef and Mizrachi found two trees on 26 vertices that are not log-concave
- 17 Sept 2026: Fang, Lu, Nevo, Yao and Zheng (arXiv 2609.20961) proved unimodality for all forests with at least N_0 vertices, for an unspecified constant N_0. Their proof claim on erdosproblems.com says 'using Odin Automatic AI Research Agent'
- 27 Sept 2026: Zhang and Li, 'Unimodality of Forest Independence Polynomials', Zenodo doi 10.5281/zenodo.22999166. Abstract: 'We reduce the large-order threshold to 59 vertices and extend the finite-order coverage through 60 vertices; the overlapping ranges complete the proof. OpenAI's GPT 6.0 Astra assisted with the computational work; the authors provided the overall proof strategy.'
- Zenodo update of 30 Sept: 'The arXiv submission was withdrawn on 28 September 2026, before it was publicly announced. We are revising the manuscript to make its exposition clearer and easier to understand.'
- 6 Oct 2026: Li, Vallier and Zhang, arXiv 2610.07943 [math.CO], 81 pages, 'Draft, version 2.2': a second proof. Forests with at most 24 vertices by exact counting; forests with at least 25 vertices by one moment argument on the hard-core model. 'No forest is enumerated.'
- AI disclosure (abstract): 'AI systems produced the new mathematical arguments and formal proofs reported here and wrote most of the text, under the direction described in Section 9. The paper has not undergone external peer review'
- Section 9: 'The project account attributes all of the new mathematics of this paper and all of its formal proofs to AI systems in a project directed by K. Vallier. The systems were Claude agents, running Anthropic's models Claude Opus 5.5 and Claude Fable 5.1; two OpenAI Codex agents, called Sol and Astra in the project, which over the period ran the OpenAI models GPT-5.6 Sol, GPT-6 Astra in Codex mode, GPT-6 Sol and GPT-6.1 Sol; and ChatGPT conversations with the OpenAI model GPT-6 Astra in Pro mode'
- Human roles per Section 9: Zhang and Li gave the earlier proof whose decomposition, binomial-mixture reduction and several inequalities the new proof reuses; Zhang wrote the introduction, Li reviewed it, Vallier directed the AI project. The section adds: 'This attribution does not assert that every author has reviewed the complete integrated manuscript.'
- Timeline per Section 9: the moment argument was developed on 27–29 Sept 2026, the proofs by hand on 28–30 Sept, the final route fixed on 1 Oct and the last inequality produced on 1–2 Oct
- Lean 4 (Mathlib): final theorem erdos993_v22_final : Erdos993Statement, with 'no premise'; code at github.com/selfreferencing/erdos993-lean. The paper notes the use of compiled evaluations; Zhang and Li's Zenodo note on the earlier release v1.0-claim says the large-order part 'uses native_decide and therefore additionally relies on Lean's compiler and runtime'
- erdosproblems.com (read 13 Oct 2026) lists two proof claims for #993 (Fang et al., 21 Sept; Tong Zhang 'using GPT6.0 astra', 27 Sept) under the notice 'Appearing on this page is no guarantee of proof correctness'. The site froze new proof claims and removed status labels on 6 Oct

## What happened

An independent set in a graph is a set of vertices with no edge between any two of them. Count the independent sets of size 0, 1,
2, … and you get the graph's independence sequence. In 1987 Alavi, Malde, Schwenk and Erdős showed that for general graphs this
sequence can go up and down in any pattern, and asked whether for trees and forests it always rises to a peak and then falls
(unimodality). The question became one of the best-known open problems about graph polynomials. A natural route, proving the
stronger log-concavity, was closed when non-log-concave trees on 26 vertices were found.

In September 2026 the problem moved quickly. On 17 Sept, Fang, Lu, Nevo, Yao and Zheng proved the statement for all sufficiently
large forests. On 27 Sept, Tong Zhang and Wei Li claimed the full result: large forests (59 vertices and up) by a probabilistic
reduction, small ones (up to 60) by structural inequalities with exact computer certificates. They credit GPT-6 Astra with the
computational work and themselves with the strategy. They withdrew the arXiv submission the next day to rewrite the exposition
and left the manuscript on Zenodo.

Kevin Vallier (University of Toledo) then ran a project in which Claude and OpenAI Codex agents built a different argument on top
of Zhang and Li's reductions and formalized it in Lean 4. The resulting paper, posted on 6 Oct with all three as authors, is
unusually explicit: it attributes "all of the new mathematics of this paper and all of its formal proofs" to AI systems, lists the
models, dates each step between 27 Sept and 2 Oct, and says that most of the prose was written by Claude agents. It also says the
authors are rewriting the manuscript before journal submission and that not every author has necessarily reviewed the whole text.

## Why it matters

It is an Erdős problem with a long literature, not an obscure one, and the paper describes a mode of work that goes beyond
"AI-assisted": agents of two companies' models produced the arguments, checked one another's certificates and wrote the formal
proof, with a human directing. The Lean theorem gives the claim a firm anchor that most AI-written proofs of 2026 lack, with the
caveat that parts of it rely on compiled evaluation. The human-readable proof is 81 pages and by the authors' own account still
provisional.

## What is disputed or not yet verified

- Verification: Lean 4 formal proof of the final statement (uses compiled evaluations, so the Lean compiler is trusted as well as the kernel); unrefereed provisional manuscript; no independent expert review found

The Lean development was not re-run for this entry, and the Zenodo PDF of the first proof was not read (its abstract and update
note were). No expert assessment, press coverage or Hacker News discussion was found on 13 Oct 2026; erdosproblems.com no longer
shows open/solved labels. Vallier's field and role beyond "directing the project" are not described in the paper.

## Your AI and this story

- GPT-6 Astra (training cutoff April 2026): 150 days after its cutoff
- Claude Opus 5.5 (training cutoff June 2026): 89 days after its cutoff
- Gemini 3.8 Flash (training cutoff March 2026): 180 days after its cutoff
- Grok 4.7 (training cutoff May 2026): 119 days after its cutoff

## Sources

1. [arXiv 2610.07943: Unimodality of Forest Independence Polynomials (Li, Vallier, Zhang; second proof)](https://arxiv.org/abs/2610.07943) (arxiv.org, paper)
2. [Zenodo: Zhang & Li, Unimodality of Forest Independence Polynomials (first proof, 27 Sept 2026)](https://doi.org/10.5281/zenodo.22999166) (doi.org, paper)
3. [Lean 4 formalization (selfreferencing/erdos993-lean)](https://github.com/selfreferencing/erdos993-lean) (github.com, code)
4. [Fang, Lu, Nevo, Yao & Zheng, Unimodality of independence polynomials for sufficiently large forests (arXiv 2609.20961)](https://arxiv.org/abs/2609.20961) (arxiv.org, paper)
5. [Erdős Problem #993 (erdosproblems.com)](https://www.erdosproblems.com/993) (erdosproblems.com, discussion)
6. [Erdős Problem #993: proof claims thread](https://www.erdosproblems.com/forum/thread/993/proof-claims) (erdosproblems.com, discussion)

## Changes

- 2026-10-13 (filed): Created from the arXiv PDF, the Zenodo record and the erdosproblems.com proof-claims thread

## Related

- 2026-10-06: [erdosproblems.com freezes proof claims and drops 'open/solved' labels and solver credits after a wave of unexplained AI proofs](https://postcutoff.com/e/2026-10-06-erdos-problems-site-freezes-proof-claims/index.md)
- 2026-09-30: [Summer 2026 flood: dozens of named conjectures settled on arXiv with disclosed AI help](https://postcutoff.com/e/2026-09-30-ai-assisted-conjecture-wave-summer-2026/index.md)
- 2026-09-03: [GPT-6 Astra proves the Erdős–Sós conjecture with a short counting argument](https://postcutoff.com/e/2026-09-03-erdos-sos-conjecture-proved-gpt-6-astra/index.md)
- 2026-07-24: [Rota's 1970 unimodality conjecture for matroid flats disproved, with ChatGPT 5.6 Pro suggesting a key construction](https://postcutoff.com/e/2026-07-24-rota-flats-unimodality-disproved/index.md)