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: Pancyclicity of highly-connected graphs
Speaker: Shoham Letzter, University College London
Date and time:
01 Jun 2023,
1:30pm -
2:30pm
Location: Cornet B129
Read full description
Abstract: A classic result of Chvatál and Erdős (1972) asserts that, if the vertex-connectivity of a graph G is at least as large as its independence number, then G has a Hamilton cycle. We prove a similar result, implying that a graph G is pancyclic, namely it contains cycles of all lengths between 3 and |G|: we show that if |G| is large and the vertex-connectivity of G is larger than its independence number, then G is pancyclic. This confirms a conjecture of Jackson and Ordaz (1990) for large graphs.
Title: Typical Ramsey properties in abelian group
Speaker: Robert Hancock, Heidelberg University
Date and time:
01 Jun 2023,
10:00am -
11:00am
Location: DSB C108
Read full description
Abstract: A famous result of Rado characterises those integer matrices $A$ which are partition regular, that is, for which any finite colouring of $[n]:=\{1,2,\dots,n\}$ (for $n$ sufficiently large) gives rise to a monochromatic solution to the equation $Ax=0$. The probability threshold for when the binomial random set $[n]_p$ has the property above was established via results of R\"odl and Ruci\'nski (for the 0-statement), and Friedgut, R\"odl and Schacht (for the 1-statement). Collectively these results form the Random Rado Theorem.
There has also been interest in Rado-type results in the setting of abelian groups. In this talk we prove an analogue of the Random Rado Theorem in the setting of sequences of (subsets of) abelian groups.
Joint work with Andrea Freschi and Andrew Treglown.
Title: Sum-Thing to Talk About
Speaker: Kate Nimegeers, University of Victoria
Date and time:
06 Apr 2023,
10:00am -
11:00am
Location: COR A121
Read full description
Abstract: The Manickam-Miklós-Singhi Conjecture states that for positive integers n and k with n > (4k - 1), a multi-set X = {x_1,x_2, … ,x_n} with real entries and nonnegative sum has at least \binom{n-1}{k-1} subsets of size k with nonnegative sum.
This talk will cover the simple arguments necessary to motivate the conjecture, an overview of recent progress towards proving the conjecture, and a sketch of the proof by Chowdhury, Sarkis, and Shahriari from 2014 that shows the conjecture holds for the quadratic bound, n > (8k^2 – 1).
Title: Aharoni's rainbow cycle conjecture holds up to an additive constant
Speaker: Tony Huynh, Sapienza Università di Roma
Date and time:
30 Mar 2023,
10:00am -
11:00am
Location: COR A121 to watch via Zoom
Read full description
Abstract: In 2017, Ron Aharoni proposed the following generalization of the Caccetta-Häggkvist conjecture: if G is a simple n-vertex edge-colored graph with n color classes of size at least r, then G contains a rainbow cycle of length at most the ceiling of n/r.
I will begin with a summary of recent progress on Aharoni's conjecture based on a new survey article of Katie Clinch, Jackson Goerner, Freddie Illingworth, and myself. I will then sketch a proof that Aharoni's conjecture holds up to an additive constant for each fixed r. The last result is joint work with Patrick Hompe.
Title: Keeping up with the Cross-Sperners: An Introduction to Cross-Sperner Systems
Speaker: Akina Kuperus, University of Victoria
Date and time:
23 Mar 2023,
10:00am -
11:00am
Location: COR A121
Read full description
Abstract:
A collection of families $(\F_{1}, \F_{2} , \cdots , \F_{k}) \in \mathcal{P}([n])^k$ is \emph{cross-Sperner} if there is no pair $i \not= j$ for which some $F_i \in \F_i$ is comparable to some $F_j \in \F_j$.
Two natural measures of the `size' of such a family are the sum $\sum_{i = 1}^k |\F_i|$ and the product $\prod_{i = 1}^k |\F_i|$. We prove upper and lower bounds on the sum measure for general $n$ and $k \ge 2$. In the process, we consider minimizing the number of sets comparable to a family $\F \subseteq \mathcal{P}([n])$ of a given size.
Title: On the Nonexistence of Generalized Bent Functions
Speaker: Shuxing Li, SFU
Date and time:
16 Mar 2023,
10:00am -
11:00am
Location: COR A121
Read full description
Abstract: An $(m,n)$-generalized bent function is a function from $\mathbb{Z}_2^n$ to $\mathbb{Z}_m$ so that its associated Fourier transformations have constant absolute value. It is known that an $(m,n)$-generalized bent function exists whenever one of the following holds:
- both $m$ and $n$ are even.
- $4 \mid m$.
Title: Pseudoku: The Ongoing Hunt for Fractional Sudoku Completion Conditions
Speaker: Kate Nimegeers, University of Victoria
Date and time:
09 Mar 2023,
10:00am -
11:00am
Location: COR A121
Read full description
Abstract: If a tricky devil challenged you to complete a Sudoku puzzle of their design, what restrictions could you place on their design to guarantee it was impossible for them to thwart your attempts? More specifically, if you could dictate exactly how many times that devil could use each symbol or pre-fill any one row, column, or box, could you safely bet that their deviously designed puzzle was still completable? This notion of seeking out guaranteed completability conditions for Sudoku drives the discussion as we delve into various graph and matrix representations of the Sudoku, explore relaxed notions of completability such as fractional completability, and use these tools to approach an answer. Due to the ongoing nature of this research, this talk is designed to serve as an introduction to the machinery of the argument being employed but does not conclude with a definitive answer.
Title: Additive structure in convex translates
Speaker: Gabriel Currier, University of British Columbia
Date and time:
02 Mar 2023,
10:00am -
11:00am
Location: COR A121
Read full description
Abstract: Suppose we have a set P of n points in the plane, and another set
S of n^{1/3} points in convex position. What can we say about the structure
of this arrangement if P contains many translates of the set S? I will
discuss a recent result showing that if P contains around n translates of
S, then the translation vectors must come from a generalized arithmetic
progression of low dimension.
The motivation for this problem comes from incidence geometry, where many
constructions for strictly convex curves having many incidences with
pointsets follow this general outline. In particular, I will discuss
applications to the Erdos unit distance conjecture. This is joint work with
Jozsef Solymosi and Ethan White.
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 1880’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.