Playing Sudoku on random 3-regular graphs
Jack Dippel, Austin Eide, Paweł Prałat, Daniel Willhalm · 2025
Read Playing Sudoku on random 3-regular graphs by Jack Dippel, Austin Eide, Paweł Prałat, Daniel Willhalm (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-07335.txt.
Description
A Sudoku puzzle gives away just enough cells to force one full solution, and graph theorists ask the same question of colored networks. Jack Dippel, Austin Eide, Paweł Prałat, and Daniel Willhalm study that number in this 2025 paper for random graphs where every node has exactly three neighbors. Such graphs need three colors, and the question is how few precolored nodes force the rest.
They show the number stays near one third of the nodes, for large random graphs, almost surely. Their proof runs an algorithm that colors the graph so as to create many locally forced nodes, those that already see two colors next door. The analysis leans on a fresh use of a differential equations method joined with Markov chain tools.
Catalog record
| CREATOR | Jack Dippel, Austin Eide, Paweł Prałat, Daniel Willhalm |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 99 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-07335