Discrete math seminar
The Discrete Mathematics Group holds a weekly seminar on Thursdays at 10am PDT.
We will meet in CLE C115. Some of the lectures will be available through Zoom and this will be indicated below.
If you would like to join the mailing list to receive the Zoom link, please email
Gary MacGillivray.
We are grateful to The Pacific Institute for the Mathematical Sciences for their support.
Title: Dependent Random Choice: A Pretty Powerful Probabilistic Proof Technique
Speaker: Shannon Ogden, University of Victoria
Date and time:
14 Apr 2022,
10:00am -
11:00am
Location: CLE C115
Read full description
The talk will be based on the survey paper "Dependent Random Choice" by Jacob Fox and Benny Sudakov.
Title: How to Lose at Tic-Tac-Toe, and Other (More Transitive) Games
Speaker: Shannon Ogden, University of Victoria
Date and time:
07 Apr 2022,
10:00am -
11:00am
Location: CLE C115
Read full description
Abstract: Achievement games are a class of combinatorial games in which two players take turns selecting points from a set (the board), with the goal of being the first to occupy one of the previously designated "winning" subsets. In this talk, we will consider the avoidance variant, in which the first player to occupy such a set loses the game. As a strategy-stealing argument can be used to show that an achievement game cannot be a second-player win, one might expect that the avoidance variant cannot be a first-player win. However, it turns out that we can find transitive avoidance games that are first-player wins for all board sizes which are not primes or powers of two. This talk is based on the paper "Transitive Avoidance Games" by J. Robert Johnson, Imre Leader, and Mark Walters.
Title: $P_4$-sparse graphs of arboricity 2
Speaker: Hugo Borges Carneiro
Date and time:
31 Mar 2022,
10:00am -
11:00am
Location: CANCELLED
Read full description
Abstract: A graph is $P_4$-sparse if every set of five vertices induces at most one $P_4$. $P_4$-sparse graphs generalize cographs and admit a tree representation. We consider the problem of deciding whether a $P_4$-sparse graph can be partitioned into two forests (or equivalently, has vertex arboricity 2). We give a characterization in terms of minimal obstructions for $P_4$-sparse graphs of vertex arboricity 2. We also show how these minimal obstructions can be extended for constructing $P_4$-sparse graphs of higher vertex arboricity.
Zoom link.
Title: Planar Graphs are Local Girth Choosable
Speaker: Evelyne Smith-Roberge, Waterloo
Date and time:
24 Mar 2022,
10:00am -
11:00am
Location: via Zoom and viewable in CLE C115
Read full description
Zoom link.
Abstract: Thomassen famously showed that every planar graph is 5-choosable, and that every planar graph of girth at least five is 3-choosable. These theorems are best possible for uniform list assignments: Voigt gave a construction of a planar graph that is not 4-choosable, and of a planar graph of girth four that is not 3-choosable. In this talk, I will introduce the concept of a local girth list assignment: a list assignment wherein the list size of each vertex depends not on the girth of the graph, but only on the length of the shortest cycle in which the vertex is contained. I will present a local choosability theorem that unifies the two theorems of Thomassen mentioned above. This is joint work with Luke Postle.
Title: Erd\H{o}s-Deep Families
Speaker: Tao Gaede, University of Victoria
Date and time:
17 Mar 2022,
10:00am -
11:00am
Location:
Read full description
Abstract:
One of the $\geq 10^{10^{10}}$ things Erd\H{o}s did in 1982 was ask the following question: for which values $k$ do there exist a set of $k$ points on the plane, no three on a line and no four on a circle, such that for every $i \in \{1,\ldots,k-1\}$, there exists a pairwise distance between its points that occurs exactly $i$ times. A set satisfying the above property is called Erd\H{o}s-deep. Using this problem as a launch point, I will introduce a related problem about finding families of $s$ Erd\H{o}s-deep sets in $\mathbb{Z}_n$ that, as a family, also satisfy a version of the Erd\H{o}s-deep property. After building the context for this related problem, I will present an overview of our argument proving the classification of the case when $s=2$. I will then briefly mention a construction for square $s$ that leverages a nice binomial identity.
Time permitting: A significant non-mathematical motivation for classifying Erd\H{o}s-deep families is that they have a nice musical interpretation as systems of rhythms, so if there is time, I hope to share some thoughts on that (and possibly a brief and humble .midi example!).
Based on joint work with Peter Dukes.
Title: Squaring the Circle with Graph Theory
Speaker: Jon Noel, University of Victoria
Date and time:
10 Mar 2022,
10:00am -
11:00am
Location: Clearihue C115 and Zoom
Read full description
Abstract: Is it possible to partition a disk in the plane into finitely many pieces and re-assemble those pieces (without distortion) to yield a partition of the square? This question was asked by Tarski back in 1925 and answered by Laczkovich some 65 years later. Spoiler alert: the answer is "yes."
Laczkovich's proof uses the Axiom of Choice in a strong way and so the pieces of his partition can be very hard to imagine. In 2017, two new proofs emerged which achieve pieces that are Lebesgue measurable or even Borel; the latter result is fully "constructive." We improve on these results by constructively achieving pieces which have (a) lower Borel complexity and (b) "small" boundaries. A benefit of the second condition is that, in contrast to the previous results, the pieces of our partition can, in some sense, be "visualized." The proof uses three concepts that are familiar to any graph-theorist: matchings, network flows and Euler circuits. Based on joint work with András Máthé and Oleg Pikhurko.
The talk will be live, in-person in Clearihue C115, and also available (livestreamed) on Zoom via the link below. The speaker will be in the seminar room.
Zoom link.
Title: CANCELLED: How to Lose at Tic-Tac-Toe, and Other (More Transitive) Games
Speaker: Shannon Ogden, University of Victoria
Date and time:
03 Mar 2022,
10:00am -
11:00am
Location: CLE C115
Read full description
Abstract. Achievement games are a class of combinatorial games in which two players take turns selecting points from a set (the board), with the goal of being the first to occupy one of the previously designated "winning" subsets. In this talk, we will consider the avoidance variant, in which the first player to occupy such a set loses the game. As a strategy-stealing argument can be used to show that an achievement game cannot be a second-player win, one might expect that the avoidance variant cannot be a first-player win. However, it turns out that we can find transitive avoidance games that are first-player wins for all board sizes which are not primes or powers of two. This talk is based on the paper "Transitive Avoidance Games" by J. Robert Johnson, Imre Leader, and Mark Walters.
Title: List homomrphisms for signed trees
Speaker:
Rick Brewster,
Thompson Rivers University
Date and time:
17 Feb 2022,
10:00am -
11:00am
Location: Clearihue C115
Read full description
The list homomorphism problem for a fixed signed graph $(H,\pi)$ takes as input a signed graph $(G, \sigma)$, equipped with lists $L(v) \subseteq V(H)$, $v \in V(G)$, of allowed images, and asks if there is a homomorphism $\varphi: (G, \sigma) \to (H, \pi)$ classify the computational complexity of this problem when $H$ is a tree (irreflexive, reflexive, and general). The polynomial targets exhibit interesting structures. The tools developed are useful for general targets, and the patterns discovered for trees suggest nice families (such as the bi-arc graphs which characterize
the problem for graphs) may classify the polynomial cases in general.
This is joint work with Jan Bok, Tom\'{a}s Feder, Pavol Hell, and Nikola Jedli\v{c}kov\'{a}
Title: Subgraphs in Semi-random Graphs (and Hypergraphs)
Speaker:
Natalie Behague,
University of Victoria
Date and time:
10 Feb 2022,
10:00am -
11:00am
Location: Clearihue C115
Read full description
Abstract: The semi-random graph process can be thought of as a one player game. Starting with an empty graph on n vertices, in each round a random vertex u is presented to the player, who chooses a vertex v and adds the edge uv to the graph. Given a graph property, the objective of the player is to force the graph to satisfy this property in as few rounds as possible.
We will consider the property of constructing a fixed graph G as a subgraph of the semi-random graph. Ben-Eliezer, Gishboliner, Hefetz and Krivelevich proved that the player can asymptotically almost surely construct G given n^{1 – 1/d}w rounds, where w is any function tending to infinity with n and d is the degeneracy of the graph G. We have proved a matching lower bound. I will talk about this result, and also discuss a generalisation of our approach to semi-random hypergraphs. I will finish with some open questions.
This is joint work with Trent Marbach, Pawel Pralat and Andrzej Rucinski.
Title: A decomposition problem of planar graphs into graphs with degree restriction
Speaker: Boram Park, Ajou University
Date and time:
03 Feb 2022,
10:00am -
11:00am
Location: via Zoom
Read full description
Abstract: Given a graph G, a decomposition of G is a partition of its edges. A graph is (d, h)-decomposable if its edge set can be partitioned into a d-degenerate graph and a graph with maximum degree at most h. In this talk, we present results related to the (d,h)-decomposition problem of planar graphs.
Please contact the organizer if you need the Zoom link.
Title: Paint by Numbers: Investigating List Colourings of Plane Graphs
Speaker:
Shannon Ogden,
University of Victoria
Date and time:
27 Jan 2022,
10:00am -
11:00am
Location: Clearihue C115
Read full description
Title: Reconfiguring paired dominating sets of paths and cycles
Speaker: Pannawat (Timmy) Eakawinrujee
Date and time:
20 Jan 2022,
10:00am -
11:00am
Location: via Zoom
Read full description
Please contact the organizer for the Zoom link.
Title: Reconfiguration of maximum irredundant sets, Part 2
Speaker: Kieka Mynhardt, University of Victoria
Date and time:
13 Jan 2022,
10:00am -
11:00am
Location: via Zoom
Read full description
Please contact the organizer for the Zoom link.
Title: An introduction to the discharging method via graph coloring
Speaker: Aaron Slobodin, University of Victoria
Date and time:
02 Dec 2021,
10:00am -
11:00am
Location: Clearihue A325
Read full description
Aaron will speak on the paper "An introduction to the discharging method via graph coloring” by Dan Cranston and Doug West.
Title: Extensions of the cycle matroid of a complete graph
Speaker: Shayla Redlin, Waterloo
Date and time:
25 Nov 2021,
10:00am -
11:00am
Location: via Zoom
Read full description
Abstract: In this talk, we will investigate the extensions of the cycle matroid of a complete graph. I will show that the number of these extensions is surprisingly large.
Please contact the organizer for the Zoom link.