-
PSDS Seminar: Playing Sudoku on random 3-regular graphs
Location: SLMath: Eisenbud Auditorium, Online/Virtual Speakers: Pawel Pralat (Toronto Metropolitan University)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.
Updated on May 12, 2025 08:02 AM PDT -
PSDS Open Problem Session
Location: SLMath: Eisenbud Auditorium Speakers: Pawel Pralat (Toronto Metropolitan University)Updated on Feb 28, 2025 08:01 AM PST -
ADJOINT/MSRI-UP panel
Location: SLMath: Eisenbud AuditoriumCreated on May 13, 2025 11:33 AM PDT
-
ADJOINT 2025
ADJOINT is a yearlong program that provides opportunities for U.S. mathematicians to conduct collaborative research on topics at the forefront of mathematical and statistical research. Participants will spend two weeks taking part in an intensive collaborative summer session at SLMath. The two-week summer session for ADJOINT 2025 will take place June 30 - July 11, 2025 in Berkeley, California. Researchers can participate in either of the following ways: (1) joining ADJOINT small groups under the guidance of some of the nation's foremost mathematicians and statisticians to expand their research portfolio into new areas, or (2) applying to Self-ADJOINT as part of an existing or newly-formed independent research group ((three-to-five participants is preferred) to work on a new or established research project. Throughout the following academic year, the program provides conference and travel support to increase opportunities for collaboration, maximize researcher visibility, and engender a sense of community among participants.
Updated on Apr 04, 2025 12:25 PM PDT