Record Lower Bounds for the Shannon Capacity of Odd Cycles

Determine the Shannon capacities of odd cycles beyond $C_5$ , or improve the best explicit bounds. New independent sets in strong graph powers give $\Theta(C_7) > 3.258020$ , $\Theta(C_{11}) > 5.289773$ , $\Theta(C_{13}) > 6.300109$ and $\Theta(C_{15}) > 7.301399$ .

Result: Proved (four record lower bounds; the exact capacities remain open for every odd cycle beyond C5)
Status: Partial result
AI contribution: AI-discovered
Method: Construction
Field: Zero-error information theory
Posed by: Claude Shannon
Year posed: 1956
Years open: 70y
Solved: 2026-07-30
Model: ChatGPT-5.6 Sol Pro
Vendor: OpenAI
Collaborators: —
Verification: Unreviewed
Publication: Preprint
Significance: 35 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What the AI did

The model generated and executed search programs across repeated prompts and returned the explicit independent-set constructions; the four authors checked that every reported set is independent.

Verification

Author-checked constructions with public data, prompts and checking code; arXiv preprint (the C15 record was added in the 30 July revision). Not yet peer-reviewed.

Source

arXiv:2607.21517 - Improved lower bounds for the Shannon capacity of odd cycles

Record Lower Bounds for the Shannon Capacity of Odd Cycles

What the AI did

Verification

Source

Discussion