Playing Sudoku on random 3-regular graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912267859132416 |
|---|---|
| author | Dippel, Jack Eide, Austin Pralat, Pawel Willhalm, Daniel |
| author_facet | Dippel, Jack Eide, Austin Pralat, Pawel Willhalm, Daniel |
| contents | The Sudoku number $s(G)$ of graph $G$ with chromatic number $χ(G)$ is the smallest partial $χ(G)$-colouring of $G$ that determines a unique $χ(G)$-colouring of the entire graph. We show that the Sudoku number of the random $3$-regular graph $\mathcal{G}_{n,3}$ satisfies $s(\mathcal{G}_{n,3}) \leq (1+o(1))\frac{n}{3}$ asymptotically almost surely. We prove this by analyzing an algorithm which $3$-colours $\mathcal{G}_{n,3}$ in a way that produces many locally forced vertices, i.e., vertices which see two distinct colours among their neighbours. The intricacies of the algorithm present some challenges for the analysis, and to overcome these we use a non-standard application of Wormald's differential equations method that incorporates tools from finite Markov chains. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_07335 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Playing Sudoku on random 3-regular graphs Dippel, Jack Eide, Austin Pralat, Pawel Willhalm, Daniel Combinatorics Discrete Mathematics The Sudoku number $s(G)$ of graph $G$ with chromatic number $χ(G)$ is the smallest partial $χ(G)$-colouring of $G$ that determines a unique $χ(G)$-colouring of the entire graph. We show that the Sudoku number of the random $3$-regular graph $\mathcal{G}_{n,3}$ satisfies $s(\mathcal{G}_{n,3}) \leq (1+o(1))\frac{n}{3}$ asymptotically almost surely. We prove this by analyzing an algorithm which $3$-colours $\mathcal{G}_{n,3}$ in a way that produces many locally forced vertices, i.e., vertices which see two distinct colours among their neighbours. The intricacies of the algorithm present some challenges for the analysis, and to overcome these we use a non-standard application of Wormald's differential equations method that incorporates tools from finite Markov chains. |
| title | Playing Sudoku on random 3-regular graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2503.07335 |