Deterministic nonbipartite Ramanujan graphs in every fixed degree at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages

A
D
V
E
R
T

I
S
E
M
E
N
T

Deterministic nonbipartite Ramanujan graphs in every fixed degree

at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages

thinking... about 3 hours remaining

If this game doesn't work on your computer, we can't help you. No Lean version yet. Some unformalized games could have issues!

expertly designed by an internal OpenAI model

Difficulty:	🧠🧠🧠🧠🧠	Ages:	13 - ∞
Skills:	counting, coloring	Levels:	1
Category:	Combinatorics	Lean version:	not yet
Rate this game! 4.3 out of 5 (4,379 votes)

>>> How to Play <<<

Deterministic nonbipartite Ramanujan graphs in every fixed degree. For every fixed d ≥ 3, constructs a simple d-regular nonbipartite Ramanujan graph on every sufficiently large even number n of vertices, with every nonconstant adjacency eigenvalue strictly between $-2\sqrt{d-1}$ and $2\sqrt{d-1}$. A deterministic algorithm outputs the full adjacency list in polynomial bit time, with exponent depending on d.

>>> Level Select <<<

LEVEL 1 Deterministic nonbipartite Ramanujan graphs in every fixed degree

released 2026-09-23 | 2 theorems · 27 lemmas · 33 proofs · 39,354 words | PLAY LEVEL 1 » (pdf)

For every fixed integer d ≥ 3, we give a deterministic algorithm that constructs a simple nonbipartite d-regular Ramanujan graph on every sufficiently large even number n of vertices. It outputs the full adjacency list in polynomially many bit operations, with an exponent that may depend on d. Every nonconstant adjacency eigenvalue lies strictly between $-2\sqrt{d-1}$ and $2\sqrt{d-1}$.

More Combinatorics Games!
A power improvement in the Heilbronn triangle problem	A counterexample to the Gopalan–Servedio conjecture	A counterexample to periodic tiling in dimension three HOT!	Borsuk's conjecture fails in dimension nine HOT!
Counterexamples to the Hadwiger and Colin de Verdière conjectures	The Euclidean plane cannot be colored with five colors PLAYABLE!	Erdős's reciprocal-sum conjecture and quasipolynomial Szemerédi bounds	Superexponential van der Waerden numbers HOT!

COOLMAITH GAMES SPONSORS: (not real)
Big Al's USED GPUs	Epsilon & Delta LLP attorneys at limit	QED Bail Bonds	Hilbert's Hotel always a vacancy!

Cool Links: openai/math Lean Mathlib arXiv the real Coolmath Games

You are visitor number 000719

Thanks for visiting CoolmAIth Games
© 1997-2026 CoolmAIth Games. A parody. Not affiliated with Coolmath.com LLC or OpenAI.
Every proof here was written by an internal OpenAI model and lives at github.com/openai/math.
Best viewed in Netscape Navigator 4.0 at 800x600