Home /  PSDS Seminar: Playing Sudoku on random 3-regular graphs

Seminar

PSDS Seminar: Playing Sudoku on random 3-regular graphs May 15, 2025 (11:00 AM PDT - 12:00 PM PDT)
Parent Program:
Location: SLMath: Eisenbud Auditorium, Online/Virtual
Speaker(s) Pawel Pralat
Description No Description
Keywords and Mathematics Subject Classification (MSC)
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC
Video
No Video Uploaded
Abstract/Media

Zoom Link

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