We hope you are enjoying your time in our graduate programs. Check out our course offerings, information about degree completion, the PhD qualifying exams, the PhD lecturing requirement, and instructions on submitting your PhD annual activity report. If you still have some years ahead in your grad studies, you might be interested in applying for scholarships.
If you have any administrative questions, please contact us at cograd@uwaterloo.ca.
Seminars in Combinatorics and Optimization
Tutte Colloquium - Jason Gao
Title: Graph Embeddings and Map Colorings
Speaker: | Jason Gao |
Affiliation: | Carleton University |
Location: | MC 5501 |
Abstract: The famous Map Color Theorem says that the chromatic number of a surface of Euler characteristic $c<0$ is equal to $\displaystyle \left\lfloor \frac{1}{2}\left(7+\sqrt{49-24c}\right)\right\rfloor $. This was proved in 1969 by Ringel and Youngs who showed that $K_n$ can be embedded on surfaces of Euler characteristic $c$ such that $\displaystyle n= \left\lfloor \frac{1}{2}\left(7+\sqrt{49-24c}\right)\right\rfloor $. This leads to the study about the genus distribution of a graph $G$, that is, the number of embeddings of $G$ on surfaces. This talk will go through some recent results about genus distributions of bouquets and cubic graphs. Some results and conjectures will also be given about the distribution of the chromatic number of a random map on a given surface.
URA Seminar - Thomas Lesgourgues
Title: On the use of senders in Ramsey Theory
Speaker: | Thomas Lesgourgus |
Affiliation: | University of Waterloo |
Location: | MC 5479 |
Abstract: In this talk I will introduce and investigate some parameters in Graph Ramsey theory, beyond the traditional Ramsey numbers. A crucial ingredient for their analysis is the existence of gadget graphs, called signal senders, that were initially developed by Burr, Erdős and Lovász in 1976. I will explain their origin, properties, and try to convey their surprising strength. Using probabilistic methods, we will see how to build such gadgets, and how to use them to prove some theorems, previously out of reach without these tools.
Graphs and Matroids - Bertrand Guenin
Title: A relaxation of Woodall’s conjecture
Speaker: | Bertrand Guenin |
Affiliation: | University of Waterloo |
Location: | MC 5479 |
Abstract: In a directed graph, a directed cut (dicut for short) is a cut where all arcs are directed from one shore to the other; a directed join (dijoin for short) is a set of arcs whose contraction makes the digraph strongly connected. The celebrated Lucchesi–Younger theorem states that for any directed graph the size of the smallest dijoin equals the maximum number of pairwise disjoint dicuts. Woodall’s conjecture posits that the size of the smallest dicut equals the maximum number of pairwise disjoint dijoins.