Seminar
Parent Program: | |
---|---|
Location: | SLMath: Eisenbud Auditorium, Online/Virtual |
The \textit{Sudoku} number $s(G)$ of graph $G$ with chromatic number $\chi(G)$ is the smallest partial $\chi(G)$-colouring of $G$ that determines a unique $\chi(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 \textit{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 \textit{differential equations method} that incorporates tools from finite Markov chains.
No Notes/Supplements Uploaded No Video Files Uploaded