Discrete math seminar
The Discrete Mathematics Group holds a weekly seminar on Thursdays at 10:00am PDT.
We will meet in COR A121. 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
Jon Noel.
We are grateful to The Pacific Institute for the Mathematical Sciences for their support.
Title: Two Equivalent Results on Plane Triangulations
Speaker: Kieka Mynhardt, University of Victoria
Date and time:
16 Feb 2023,
10:00am -
11:00am
Location: COR A121
Read full description
Abstract: It is well known that a maximal planar graph of order at least 3 is 3-colourable if and only if it is Eulerian. It is also known that if a maximal planar graph of order at least 3 has exactly two vertices of odd degree, then these vertices are nonadjacent. I will show that these two results are equivalent.
The talk should be accessible to undergraduate students with a basic knowledge of graph theory.
Title: Permutations, probability and graph embeddings
Speaker: Jesse Campion Loth, Simon Fraser University
Date and time:
09 Feb 2023,
10:00am -
11:00am
Location: COR A121
Read full description
Abstract: Products of permutations are used to model problems in fields ranging from representation theory and algebraic geometry to topological graph theory. I will show how probability can be used to study such problems, with a focus on how graphs may be embedded on different surfaces.
Title: Sliding into My DMS
Speaker: Kate Nimegeers, University of Victoria
Date and time:
02 Feb 2023,
10:00am -
11:00am
Location: COR A121
Read full description
Abstract
The 15-puzzle which acts as an inspiration for this talk is a simple game consisting of 15 square tiles numbered 1–15 in a frame that is 4 tiles high and 4 tiles wide, leaving one unoccupied tile position. Tiles in the same row or column of the open position can be moved by sliding them horizontally or vertically. Like the popular Rubik's cube, the sliding puzzle is often ‘jumbled up‘ and the goal of the puzzle is to place the tiles in numerical order from left to right and top to bottom with the empty tile in the bottom right corner. In the late 1980’s a famous American puzzler named Sam Loyd offered $1000 to anyone who could provide him with a series of moves that would swap only the tiles labelled 14 and 15 while leaving all other positions in their standard numerical order. In this talk we will discuss which mathematical principles guaranteed that Sam Loyd would keep his money and discuss how the mathematician Richard Wilson used graph theory ‘inception’ to generalize this notion to all sliding puzzles, determining exactly which solutions were possible and which could never be obtained.
Title: Helly numbers of exponential lattices
Speaker: Nora Frankl, Open University
Date and time:
26 Jan 2023,
10:00am -
11:00am
Location: COR A121
Read full description
The Helly number of a set in the plane is the smallest N such that the following is true. If any N members of a finite family of convex sets contains a point of S, then there is a point of S which is contained in all members of the family. An exponential lattice with base x consists of points whose coordinates are positive integer powers of x. We prove lower and upper bounds on Helly numbers of exponential lattices in terms of x, and we determine their values exactly in some cases. We also consider asymmetric exponential lattices, and characterise those that have finite Helly numbers.
Joint work with Gergely Ambrus, Martin Balko, Attila Jung and Márton Naszódi.
Title: 3-colouring via flows
Speaker: Benjamin Moore, Charles University
Date and time:
19 Jan 2023,
10:00am -
11:00am
Location: COR A121
Read full description
Abstract: I'll show an algorithm for 3 colouring triangle free graphs embedded on the Klein bottle that runs in polynomial time if most of the faces are 4 faces. Joint work with Jean-Sebastian Sereni and Zdenek Dvorak.
Title: The Strong Nine Dragon Tree Conjecture for d <= k+1
Speaker: Sebastian Mies
Date and time:
12 Jan 2023,
10:00am -
11:00am
Location: COR A121
Read full description
Abstract:
The arboricity \Gamma(G) of an undirected graph G = (V,E) is the minimal number such that E can be partitioned into \Gamma(G) forests. Nash-Williams' formula states that \Gamma(G) = \ceil{ \gamma(G) }, where \gamma(G) is the maximum of |E_H|/(|V_H|-1) over all subgraphs (V_H, E_H) of G with |V_H| ≥ 2.
The Strong Nine Dragon Tree Conjecture states that if \gamma(G) ≤ k + d / (d+k+1) for natural numbers k, d, then there is a partition of the edge set of G into k+1 forests such that one forest has at most d edges in each connected component.
We settle the conjecture for d ≤ k + 1. For d ≤ 2(k+1), we cannot prove the conjecture, however we show that there exists a partition in which the connected components in one forest have at most d + \ceil{kd/(k+1)} - k edges.
As an application of this theorem, we show that every 5-edge-connected planar graph G has a 5/6-thin spanning tree, a spanning trees whose edges fill up at most 5/6 of every cut. This theorem is best possible, in the sense that we cannot replace 5-edge-connected with 4-edge-connected, even if we replace 5/6 with any positive real number less than 1. This strengthens a result of Merker and Postle which showed 6-edge-connected planar graphs have a 18/19-thin spanning tree.
This is joint work with Benjamin Moore.
Title: Saturate the Rainbow. Taste the Rainbow
Speaker: Shannon Ogden, University of Victoria
Date and time:
01 Dec 2022,
3:30pm -
4:30pm
Location: MAC D116
Read full description
Abstract: Given a graph H, an edge-coloured graph G is H-rainbow saturated if it does not contain a rainbow copy of H, but the addition of any non-edge in any colour creates a rainbow copy of H. The rainbow saturation number, denoted by rsat(n,H), is the minimum number of edges among all H-rainbow saturated edge-coloured graphs on n vertices. We prove that, for any non-empty graph H, the rainbow saturation number is linear in n. This confirms a recent conjecture of Girão, Lewis, and Popielarz. Based on joint work with Natalie Behague, Tom Johnston, Shoham Letzter, and Natasha Morrison.
Title: Odd covers of graphs
Speaker: Jiaxi Nie, Shanghai Centre for Mathematical Sciences
Date and time:
24 Nov 2022,
3:30pm -
4:20pm
Location: MAC D116 to watch talk on Zoom
Read full description
Abstract: Given a finite simple graph $G$, an {\em odd cover of $G$} is a collection of complete bipartite graphs, or bicliques, in which each edge of $G$ appears in an odd number of bicliques and each non-edge of $G$ appears in an even number of bicliques. We denote the minimum cardinality of an odd cover of $G$ by $b_2(G)$ and prove that $b_2(G)$ is bounded below by half of the rank over $\mathbb{F}_2$ of the adjacency matrix of $G$. We show that this lower bound is tight in the case when $G$ is a bipartite graph and almost tight when $G$ is an odd cycle. However, we also present an infinite family of graphs which shows that this lower bound can be arbitrarily far away from $b_2(G)$. Babai and Frankl (1992) proposed the ``odd cover problem," which in our language is equivalent to determining $b_2(K_n)$. Radhakrishnan, Sen, and Vishwanathan (2000) determined $b_2(K_n)$ for an infinite but density zero subset of positive integers $n$. In this paper, we determine $b_2(K_n)$ for a density $3/8$ subset of the positive integers. This is joint work with Calum Buchanan, Alexander Clifton, Jason O'Neil, Puck Rombach, and Mei Yin.
Title: Maximal Independent Broadcasts in Graphs and their Spanning Trees
Speaker: Jules Hoepner, University of Victoria
Date and time:
17 Nov 2022,
3:30pm -
4:30pm
Location: MAC D116
Read full description
A broadcast on a connected graph G with vertex set V(G) is a function f:V(G) ➛ {0, 1, ..., diam(G)} such that f(v) ≤ e(v), where e(v) denotes the eccentricity of v. If f(v) > 0, the vertex v is said to broadcast at strength f(v). In generalizing independent sets to broadcasts, Erwin (2001) introduced the concept of hearing independent broadcasts, in which no broadcasting vertex u lies within distance f(v) of another broadcasting vertex v. If instead we require that the distance d(u, v) is at least f(u)+f(v) for all u, v with f(u), f(v) > 1, we obtain the definition of boundary independence introduced by Mynhardt and Neilson in 2019.
In this talk, we consider the minimum costs of maximal hearing independent and boundary independent broadcasts on graphs and show these parameters are comparable, solving an open problem posed by Marchessault and Mynhardt in 2021. We further prove that the minimum cost of a maximal boundary independent broadcast on a connected graph equals the minimum among those of its spanning trees, and that the same is true for hearing independent broadcasts.
Title: Cops and Robber Game on Surfaces of Euclidean, Spherical and Hyperbolic Metric
Speaker: Alexandra Wesolek, Simon Fraser University
Date and time:
03 Nov 2022,
3:30pm -
4:30pm
Location: MAC D116
Read full description
Recently, Mohar introduced a variant of the cops and robber game that is played on geodesic spaces. The game combines properties of pursuit-evasion games with the classical cops and robber game played on graphs. In this talk we discuss the rules of the game and strategies for the players when the game is played on compact surfaces of constant curvature. Joint work with Vesna Iršič and Bojan Mohar.
Title: Iterative Constructions in Extremal Combinatorics
Speaker: Felix Clemen, University of Illinois Urbana-Champaign
Date and time:
27 Oct 2022,
3:30pm -
4:30pm
Location: MAC D116 to watch talk on Zoom
Read full description
The first two problems are concerning edge-colorings of complete graphs. Erd\H{o}s and Tuza asked in 1993 whether for any graph F on l edges and any completely balanced coloring of any sufficiently large complete graph using l colors contains a rainbow copy of F. We answer this and a related question. This is joint work with Maria Axenovich.
The third problem concerns point sets in the plane. Bárány and Füredi asked to determine the maximum number of triangles being almost similar to a given triangle in a planar point set of fixed size. Exploring connections to hypergraph Turán problems, we answer this question for almost all triangles. This is joint work with József Balogh and Bernard Lidick\'{y}.
Title: Circular flows in mono-directed Eulerian signed graphs
Speaker: Zhouningxin Wang, IRIF, Université Paris Cité
Date and time:
20 Oct 2022,
3:30pm -
4:30pm
Location: MAC D116
Read full description
Abstract: Given positive integers $p,q$ where $p$ is even and $p\geq 2q$, a circular $\frac{p}{q}$-flow in a mono-directed signed graph $(G, \sigma)$ is a pair $(D, f)$ where $D$ is an orientation on $G$ and $f: E(G)\to \mathbb{Z}$ satisfies that for each positive edge $e$, $q\leq |f(e)|\leq p-q$ and for each negative edge $e$, either $0\leq |f(e)|\leq \frac{p}{2}-q$ or $\frac{p}{2}+q\leq |f(e)|\leq p-1$, and the total in-flow equals the total out-flow at each vertex. This is the dual notion of circular $\frac{p}{q}$-coloring of signed graphs recently introduced in ``Circular chromatic number of signed graphs. R. Naserasr, Z. Wang, and X. Zhu. Electronic Journal of Combinatorics, 28(2)(2021), \#P2.44''.
In this talk, we consider bipartite analogs of Jaeger's circular flow conjecture and its dual, Jaeger-Zhang conjecture. We show that every $(6k-2)$-edge-connected Eulerian signed graph admits a circular $\frac{4k}{2k-1}$-flow and every signed bipartite planar graph of negative-girth at least $6k-2$ admits a circular $\frac{4k}{2k-1}$-coloring. We also provide some recent results about the circular flow index of signed graphs with high edge-connectivities.
This is joint work with Jiaao Li, Reza Naserasr, and Xuding Zhu.
Title: Stable Matchings
Speaker: Ndiamé Ndiaye, McGill University
Date and time:
06 Oct 2022,
3:30pm -
4:30pm
Location: MAC D116 to watch talk on Zoom
Read full description
Abstract:
The set of stable matchings induces a distributive lattice. The supremum of the stable matching lattice is the boy-optimal (girl-pessimal) stable matching and the infimum is the girl-optimal (boy-pessimal) stable matching. The classical boy-proposal deferred-acceptance algorithm returns the supremum of the lattice, that is, the boy-optimal stable matching.
In this paper, we study the smallest group of girls, called the minimum winning coalition of girls, that can act strategically, but independently, to force the boy-proposal deferred-acceptance algorithm to output the girl-optimal stable matching. We characterize the minimum winning coalition in terms of stable matching rotations and show that its cardinality can take on any value between $0$ and $\floor{\frac{n}{2}}$, for instances with $n$ boys and $n$ girls.
Our two main results concern the random matching model. First, the expected cardinality of the minimum winning coalition is small, specifically $(\frac{1}{2}+o(1))\log{n}$. This resolves a conjecture of Kupfer. Second, in contrast, a randomly selected coalition must contain nearly every girl to ensure it is a winning coalition asymptotically almost surely. Equivalently, for any $\varepsilon>0$, the probability a random group of $(1-\varepsilon)n$ girls is not a winning coalition is at least $\delta(\varepsilon)>0$.
This is joint work with Sergey Norin and Adrian Vetta.
Title: Product structure of graph classes with bounded treewidth
Speaker: Robert Hickingbotham, Monash University
Date and time:
29 Sep 2022,
3:30pm -
4:30pm
Location: MAC D116
Read full description
Abstract: This talk will introduce the topic of graph product structure theory. I will show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the \emph{underlying treewidth} of a graph class \GG to be the minimum non-negative integer c such that, for some function f, for every graph G \in \GG there is a graph H with \tw(H) \leq c such that G is isomorphic to a subgraph of H \boxtimes K_{f(\tw(G))}. I'll introduce \emph{disjointed partitions} of graphs and show they determine the underlying treewidth of any graph class. Using this result, I will show that the class of planar graphs has underlying treewidth 3; the class of K_{s,t}-minor-free graphs has underlying treewidth s (for {t \geq \max\{s,3\}}); and the class of K_t-minor-free graphs has underlying treewidth t-2. This is joint work with Rutger Campbell, Katie Clinch, Marc Distel, Pascal Gollin, Kevin Hendrey, Tony Huynh, Freddie Illingworth, Youri Tamitegama, Jane Tan and David Wood [https://arxiv.org/abs/2206.02395].
Title: Spanning trees and loop soups on surfaces
Speaker: Gourab Ray, University of Victoria
Date and time:
22 Sep 2022,
3:30pm -
4:30pm
Location: MAC D116
Read full description
Abstract: A spanning tree is a connected subgraph of a graph with no cycles. I will explain some well-known connection between such collection of trees and some Poissonian collection of loops, and a magical algorithm (known as Wilson's alorithm) to sample such trees very fast. Then I will try to explain a recent extension to the multiply connected setting, and pose an open question in the end. Joint work with N. Berestycki and B. Laslier.
Title: Disjoint isomorphic balanced clique subdivisions
Speaker: Joseph Hyde, University of Victoria
Date and time:
15 Sep 2022,
3:30pm -
4:30pm
Location: MAC D116
Read full description
Abstract: A classical result, due to Bollobás and Thomason, and independently Komlós and Szemerédi, states that a graph with average degree O(k^2) guarantees the existence of a K_k-subdivision. We study two directions extending this result.
Firstly, Verstraëte conjectured in 2002 that the quadratic bound O(k^2) would guarantee already two vertex-disjoint isomorphic copies of a K_k-subdivision. Secondly, Thomassen conjectured in 1984 that for each k \in \mathbb{N} there is some d = d(k) such that every graph with average degree at least d contains a balanced subdivision of K_k. Recently, Liu and Montgomery confirmed Thomassen's conjecture, but the optimal bound on d(k) remains open.
In this talk, we show that the quadratic bound O(k^2) suffices to force a balanced K_k-subdivision. This gives the optimal bound on d(k) needed in Thomassen's conjecture and implies the existence of O(1) many vertex-disjoint isomorphic K_k-subdivisions, confirming Verstraëte's conjecture in a strong sense.
Title: The Speed and Threshold of the Biased Hamilton Cycle Game.
Speaker: Bruce Reed, McGill University
Date and time:
25 Aug 2022,
2:30pm -
3:30pm
Location: DSB C108
Read full description
Abstract:
In the biased Hamilton Cycle Maker-Breaker game, two players alternate choosing edges from
a complete graph. In the game with bias b, Maker chooses one previously unchosen edge
in each turn and Breaker chooses b. The game is Maker-win for the given bias if Maker can
ensure she chooses the edges of a Hamilton Cycle and Breaker-win otherwise.
Letting n be the number of vertices, if the bias is 0 then Maker wins the game in n moves.
On the other hand, if the bias b=b(n) is {n choose 2}-1 then Breaker wins.
Furthermore, if Breaker wins for some bias b, then she also wins for bias b+1. We discuss
the threshold at which the game becomes Breaker win, and the number of moves
maker needs to ensure she wins for b below this threshold, which is called the speed of the
game.
Warmup: What bounds can you obtain on the threshold and speed without a literature search?
Any ideas how to proceed?