Open Research Index

On Expansion of Random Regular Graphs: Improved Lower Bounds for Small Even Degrees

Pasin Manurangsi

arXivarxiv/2604.00488Apr 1, 2026math.COscore 0

We show that a simple scoring-based tie-breaking can help improve lower bounds for the expansion (aka isoperimetric number) of random regular graphs with small even degrees. Specifically, for degrees 4, 6 and 8, we show that, with high probability, the expansions are at least 0.489, 1.120 and 1.813 respectively.

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2604.00488
curl -X POST /api/v1/records/arxiv/2604.00488/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.00488/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'