Discrete math seminar
The Discrete Mathematics Group holds a weekly seminar on Thursdays at 10:00am PDT.
We will meet in COR A128. 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.
The seminar is co-organized by Joseph Hyde, Natasha Morrison and Jon Noel. We are grateful to The Pacific Institute for the Mathematical Sciences for their support.
Title: Peaceful Colourings
Speaker: Bruce Reed, Academia Sinica
Date and time:
18 Jul 2024,
10:00am -
11:00am
Location: DSB C128
Read full description
A proper conflict-free colouring of a graph is a (vertex-)colouring with no monochromatic edges such that for every nonisolated vertex v, the neighbourhood N(v) contains a vertex w coloured with a colour not appearing on N(v)-{w}. For a real number h, a colouring of a graph with no monochromatic edges is h-conflict-free if for every vertex v, N(v) contains at least min{deg(v), h} vertices coloured with a colour used only once in N(v). For a real number p, we define a p-peaceful colouring to be a colouring f with no monochromatic edges in which for every vertex v,
|{w in N(v) : there exists u in N(v)-{w} with f(u)=f(w)}| ≤ p.
We note that for a d-regular graph, a colouring is an h-conflict-free proper colouring precisely if it is a (d-h)-peaceful colouring. In contrast, if G is an irregular graph of maximum degree Delta then while a p-peaceful colouring and a (\Delta-p)-conflict-free colouring impose the same condition on maximum degree vertices, the peaceful colouring imposes weaker conditions on low degree vertices. We present some results on these three types of colourings. These are joint work with Chun-hung Liu.
Title: Star and monotone factorizations and Jucys-Murphy elements
Speaker: Amarpreet Rattan, Simon Fraser University
Date and time:
16 May 2024,
10:00am -
11:00am
Location: ECS 104
Read full description
Abstract: For fixed n, consider the symmetric group S_n on the symbols 1,...,n and the set of *star* transpositions, the transpositions that contain the symbol n. A *star factorization* of a permutation b in S_n of length k is the writing of b as the product of k star transpositions. Goulden and Jackson (2009) showed that the number of such factorizations only depends on the conjugacy class of b and not on b itself, a remarkable fact given the special role the symbol n plays amongst star transpositions. We supply the first fully combinatorial proof of this fact that works for all lengths k, and our methods connect star factorizations to monotone factorizations. Star transpositions are connected to Jucys-Murphy elements, and we explain how our result can give expressions for the *transitive* image of certain symmetric functions evaluated at Jucys-Murphy elements.
This is joint work with Jesse Campion Loth (Heilbronn Institute and the University of Bristol).
Title: Analytic approach to extremal combinatorics
Date and time:
07 May 2024,
10:00am -
11:00am
Location: DSB C118
Read full description
Title: Cops and Robber on surfaces of constant curvature
Date and time:
04 Apr 2024,
10:00am -
11:00am
Location: COR A128
Read full description
In 2021, Mohar introduced the game of Cops and Robber on geodesic spaces. The game captures the behavior of the Cops and Robber game played on graphs and that of continuous pursuit-evasion games. Analogous to one of the main open problems for the Cops and Robber game on graphs, Mohar conjectured that the cop number of a geodesic surface of genus $g$ is at most $O(\sqrt{g})$. Surprisingly, this upper bound can be significantly improved on surfaces of constant curvature which will be the main focus of this talk.
????????????
It turns out that the cop number of compact spherical and Euclidean surfaces is at most $2$. Even more surprisingly, the cop number of compact hyperbolic surfaces is also at most $2$, independently of their genus. We will also consider the strong cop number of these surfaces and present several generalizations to higher-dimensions.
Joint work with Bojan Mohar and Alexandra Wesolek.
Title: Sidorenko-type inequalities for Trees
Speaker: Lina Simbaqueba, University of Victoria
Date and time:
28 Mar 2024,
10:00am -
11:00am
Location: COR A128
Read full description
Given two graphs H and G, the homomorphism density t(H,G) represents the likelihood that a random mapping from V(H) to V(G) is a homomorphism. Sidorenko Conjecture states that for any bipartite graph H, t(H,G) is greater or equal to t(K_2,G)^{e(H)}.
Introducing a binary relation H \geq T if and only if t(H,G)^{e(T)} \geq t(T,G)^{e(H)} for all graphs G, we establish a partial order on the set of non-empty connected graphs. Employing a technique by Kopparty and Rossman, which involves the use of entropy to define a linear program, we derive several necessary and sufficient conditions for two trees T, F satisfy T\geq F. Furthermore, we show how important results and open problems in extremal graph theory can be reframed using this binary relation.
Joint work with Natalie Behage, Gabriel Crudele, and Jonathan Noel.
Title: Counting X-free sets
Speaker: Ashna Wright, University of Victoria
Date and time:
21 Mar 2024,
10:00am -
11:00am
Location: COR A128
Read full description
Title:
Speaker: Nina Kamcev, University of Zagreb
Date and time:
14 Mar 2024,
10:00am -
11:00am
Location: COR A128
Read full description
Title: Conflict-free hypergraph matchings and generalized Ramsey numbers
Speaker: Emily Heath, Iowa State University
Date and time:
07 Mar 2024,
10:00am -
11:00am
Location: COR A128
Read full description
Title: Oriented Colouring Graphs of Bounded Euler Genus
Speaker: Alexander Clow, SFU
Date and time:
29 Feb 2024,
10:00am -
11:00am
Location: COR A128
Read full description
Abstract: In this talk we consider the oriented colouring problem for graphs with bounded Euler genus. That is we consider the smallest $k$ such that all oriented graphs embeddable on surfaces of Euler genus at most $g$ necessarily have an oriented homomorphism to a graph of order $k$. For convenience given a fixed $g$ and $k$, we let $\chi_o(g) = k$. We will discuss our proofs that $\Omega((\frac{g^2}{\log{g}})^{\frac{1}{3}}) \leq \chi_o(g) \leq (1+o(1))g^{6400}$, which improves the prior upper bound of order $2^{O(g^{\frac{1}{2}+o(1)})}$ and lower bound of order $\Omega(\sqrt{g})$, as well as exploring how our bounds might be improved in future work.
Joint work with Peter Bradshaw (University of Illinois Urbana Champaign), and Jingwei Xu (University of Illinois Urbana Champaign).
Title: Broadcast Independence and Broadcast Packing in Various Subclasses of Trees
Speaker: Kiara McDonald, University of Victoria
Date and time:
15 Feb 2024,
10:00am -
11:00am
Location: COR A128
Read full description
Title: Clique number of Paley graphs and Paley-like graphs
Speaker: Kyle Yip, UBC
Date and time:
08 Feb 2024,
10:00am -
11:00am
Location: COR A128
Read full description
Abstract: Let q=1 mod 4 be a prime power and let F_q be the finite field of q elements. The Paley graph of order q is the graph with vertex set F_q, such that two vertices are adjacent if and only if their difference is a square in F_q. Paley graphs play an important role in many branches of combinatorics and number theory. Among many exciting questions related to Paley graphs, estimating their clique number is of importance. In this talk, I will report recent progress on the lower bounds and upper bounds on the clique number of Paley graphs and Paley-like graphs. Joint work with Seoyoung Kim, Jozsef Solymosi, and Semin Yoo.
Title:
Date and time:
01 Feb 2024,
10:00am -
11:00am
Location: COR A128
Read full description
Since suggested by Tur\'an in 1941, determining the Tur\'an density of hypergraphs has been a notoriously difficult problem at the center of extremal combinatorics.
Subsequently, several natural variants of this problem have been suggested, most prominently the uniform Tur\'an density by Erd\H{o}s and S\'os and the codegree Tur\'an density by Mubayi and Zhao.
Roughly speaking, the Tur\'an density is the threshold of the edge density above which large hypergraphs are guaranteed to contain a copy of a fixed hypergraph~$F$.
Similarly, the uniform Tur\'an density and the codegree Tur\'an density are the thresholds of the local density and the minimum codegree, respectively, above which large hypergraphs are guaranteed to contain a copy of~$F$.
In this talk, we will discuss recent results which determine several variants of the Tur\'an density in new instances and make progress towards a problem of Erd\H{o}s and S\'os.
Further, we will present our recent result with Piga which states that there are hypergraphs with arbitrarily small codegree Tur\'an density.
This is in contrast to the behaviour of the classical Tur\'an density and the uniform Tur\'an density due to results by Erd\H{o}s and by Reiher, R\"odl, and Schacht, respectively.
Based on joint works with Chen, Conlon, Piga, and Sales.
Title: Correspondence Packing Planar Graphs
Speaker: Evelyne Smith-Roberge, Georgia Tech
Date and time:
25 Jan 2024,
10:00am -
11:00am
Location: COR A128 and Zoom
Read full description
Evelyne will be giving her talk remotely (on Zoom). Local participants are still encouraged to come to COR A128 to view it on the projector.
Abstract: Suppose a graph G has list chromatic number k. It is easy to see that if L is a (k+1)-list assignment for G, then G admits two L-colourings f and g where f(v) =/= g(v) for every vertex v in the graph. But what if we want still more disjoint L-colourings? In this talk, I will discuss recent progress towards determining the list packing number of various classes of planar graphs: that is, the smallest number k such that if L is a k-list assignment for an arbitrary graph G in the class under study, then L can be decomposed into k disjoint L-colourings. All results I will discuss also hold in the correspondence colouring framework. Joint work with Daniel Cranston.
Title: The Erd?s-Rothschild problem for dichromatic triangles
Speaker: Yani Pehova, London School of Economics
Date and time:
18 Jan 2024,
10:00am -
11:00am
Location: COR A128
Read full description