# Discrete Math Seminars

Most Fridays in K9509 - 11:30am to 12:30pm

Please join us for this weekly seminar on a wide variety of topics under the umbrella of discrete mathematics. We gratefully acknowledge the Pacific Institute of Mathematical Sciences for their generous funding since 2010.

Watch for upcoming Seminars listed below, offered in SCK 9509 and/or on Zoom. We welcome remote participation from groups at other universities.

All talks will be announced on this page, on the department calendar (found at the bottom of the Math homepage), and on the DM Seminar mailing list. If you have an SFU email address, you can subscribe or unsubscribe to the mailing list by logging in to maillist.sfu.ca and searching for the math-dmsem list. Otherwise, you can ask any discrete math faculty member to manually add you to the list. With the permission of the speaker, we will record the talk video and upload it to the SFU Discrete Math Seminar Youtube Channel

Current organizer: Bojan Mohar (mohar@sfu.ca) & Jesse Campion Loth

## 2022 Talks

### Fall 2022

 07 Oct Special Time: 11am Bojan Mohar. Simon Fraser University Beyond the Four-Color Theorem The speaker will discuss the Four-Color Theorem and some of the outstanding problems left open after the proof. 14 Oct Peter Bradshaw, Simon Fraser University A small step forward in bipartite list coloring The choosability of a graph G is the minimum value k such that G has a proper list coloring whenever each vertex of G has a list of k colors. Molloy showed that if G is a triangle-free graph of maximum degree d, then the choosability of G is at most (1 + o(1)) d / log d and that this bound is tight within a factor of roughly 2. It is widely believed that this upper bound can be greatly improved in the special case that G is bipartite, and Alon and Krivelevich conjectured an upper bound of O(log d) in this case. However, little progress has been made toward solving this conjecture, and it is currently unknown whether the optimal upper bound for bipartite graphs is different from the optimal upper bound for triangle-free graphs. In this talk, we will use a modification of a coupon-collector argument from Alon, Cambie, and Kang to show that every bipartite graph of maximum degree d has choosability at most 0.797 d / log d. Our result provides strong evidence that the list-coloring problem is fundamentally easier in bipartite graphs than in triangle-free graphs and hence takes an important step toward solving the conjecture of Alon and Krivelevich. (The content of this talk is part of ongoing work with Bojan Mohar and Ladislav Stacho.) 21 Oct Harmony Zhan, Simon Fraser University An introduction to discrete quantum walks A discrete quantum walk is determined by a unitary matrix representation of a graph. In this talk, I will give an overview of different quantum walks, and show how the spectral information of the unitary matrix representation links properties of the walks to properties of the graphs. Part of this talk will be based on the book, Discrete Quantum Walks on Graphs and Digraphs, by Chris Godsil and me. 28 Oct Zhouningxin Wang Circular flows in mono-directed Eulerian signed graphs In this talk, we consider analogs of Jaeger's circular flow  conjecture and its dual Jaeger-Zhang conjecture in signed graphs. We  will first give the notions of circular coloring and circular flow in  signed graphs, and then show that every (6k-2)-edge-connected Eulerian signed graph admits a circular 4k/(2k-1)-flow and that every  signed bipartite planar graph of negative-girth at least 6k-2 admits a  circular 4k/(2k-1)-coloring (equivalently, admits a homomorphism to a  negative cycle of length 2k). We also provide some recent results about circular flow indices of signed graphs with  high edge-connectivities.  This is based on joint work with Jiaao Li, Reza Naserasr, and Xuding Zhu.

### Spring 2022

 18 Jan  (ZOOM) Jiaxi Nie, University of California San Diego On Asymptotic Packing of Geometric Graphs A set of geometric graphs is geometric-packable if it can be asymptotically packed into every sequence of drawings of the complete graph $K_n$. For example, the set of geometric triangles is geometric-packable due to the existence of Steiner Triple Systems. When G is the 4-cycle (or 4-cycle with a chord), we show that the set of plane drawings of G is geometric-packable. In contrast, the analogous statement is false when G is nearly any other planar Hamiltonian graph (with at most 3 possible exceptions). A convex geometric graph is convex-packable if it can be asymptotically packed into the convex drawings of the complete graphs.  For each planar Hamiltonian graph G, we determine whether or not a plane G is convex-packable. Many of our proofs explicitly construct these packings; in these cases, the packings exhibit a symmetry that mirrors the vertex transitivity of $K_n$.    here is the link. (ID: 668 0051 2140, password: Graph) 25 Jan Kathryn Nurse, Simon Fraser University Toward Bouchet’s conjecture on nowhere-zero flows in signed graphs. I will present a work in progress. In 1954, Tutte proved flow-colouring duality and made a conjecture that every graph without a cut-edge has a nowhere-zero 5-flow. A parallel conjecture to this, but for signed graphs is Bouchet's conjecture (1983) that every signed graph without the obvious obstruction has a nowhere-zero 6-flow. We have been able to show that Bouchet's conjecture holds for 3-connected graphs when 6 is replaced with 8. This is joint with Matt DeVos and Robert Šámal. 01 Feb Annie Raymond (UMass) Tropicalization of graph profiles The number of homomorphisms from a graph H to a graph G, denoted by hom(H;G), is the number of maps from V(H) to V(G) that yield a graph homomorphism, i.e., that map every edge of H to an edge of G. Given a fixed collection of finite simple graphs {H_1, ..., H_s}, the graph profile is the set of all vectors (hom(H_1; G), ..., hom(H_s; G)) as G varies over all graphs.  Graph profiles essentially allow us to understand all polynomial inequalities in homomorphism numbers that are valid on all graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected graphs is not known. To simplify these objects, we introduce their tropicalization which we show is a closed convex cone that still captures interesting combinatorial information. We explicitly compute these tropicalizations for some sets of graphs, and relate the results to some questions in extremal graph theory. This is joint work with Greg Blekherman, Mohit Singh and Rekha Thomas. 08 Feb Vesna Iršič (Simon Fraser University) Winning vs. catching in the game of cops and robber on manifolds 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 the game, cops win if they can get arbitrarily close to the robber. On the other hand, cops catch the robber if one of them occupies the same point as the robber. In this talk we will discuss several strategies for players in the game, and observe the difference between the number of cops needed to catch the robber and the number of cops needed to win the game. Joint work with Bojan Mohar and Alexandra Wesolek. 15 Mar Bojan Mohar (Simon Fraser University) Proper orientations and proper chromatic number It is an interesting (and not entirely obvious) fact that every graph admits an orientation of its edges so that the outdegrees at vertices form a "coloring" (outdegrees of any two adjacent vertices are different). The proper chromatic number $\Vec{\chi}(G)$ of a graph $G$ is the minimum $k$ such that there exists an orientation of the edges of $G$ with all vertex-outdegrees at most $k$ and such that for any adjacent vertices, the outdegrees are different. Two major conjectures about the proper chromatic number are resolved. First it is shown, that $\Vec{\chi}(G)$ of any planar graph $G$ is bounded (in fact, it is at most 14). Secondly, it is shown that for every graph, $\Vec{\chi}(G)$ is at most $O(\frac{r\log r}{\log\log r})+\tfrac{1}{2}\MAD(G)$, where $r=\chi(G)$ is the usual chromatic number of the graph, and $\MAD(G)$ is the maximum average degree taken over all subgraphs of $G$. Several other related results are derived. Our proofs are based on a novel notion of fractional orientations. This is joint work with Yaobin Chen and Hehui Wu. 05 Apr Zdenek Dvorak (Charles University) 3-coloring near-quadrangulations of the plane and the torus using flows (joint work with C. Bang, E. Heath, and B. Lidicky) A graph drawn in a surface is a k-near-quadrangulation if the product of the lengths of its faces, except for 4-faces, is at most k. Near-quadrangulations play a fundamental role in the theory of 3-colorability of triangle-free graphs on surfaces.  We show how the well-known duality between colorings and flows can be used to design * a 3-precoloring extension algorithm for k-near-quadrangulations of the plane, and * a 3-coloring algorithm for k-near-quadrangulations of the torus, with time complexity polynomial in k and the number of vertices.

## 2021 Talks

### Fall 2021

 09 Nov Andrei Bulatov, Simon Fraser University The complexity of counting homomorphisms The Constraint Satisfaction Problem (CSP) provides a general framework for a wide range of combinatorial problems. The simplest way to state the problem is: Given relational structures (say, graphs) G and H, decide if there is a homomorphism from G to H. The counting version of the CSP, #CSP, asks for the number of such homomorphisms. In order to represent specific problems, the CSP is often restricted in various ways, in particular by fixing the target structure H. Thus, CSP(H) asks if, for a given structure G, there is a homomorphism from G to H. If H is a graph such a problem is often called H-Coloring. The counting versions #CSP(H), #H-Coloring of these problems are defined accordingly. In this talk we survey the developments in the study of the complexity of #CSP(H) that eventually led to a complete classification of such problems and their various generalizations.   ZOOM Information: https://sfu.zoom.us/j/66800512140?pwd=N011dU5ZNThSWnVzMFBjYnBidDdmUT09  (ID: 668 0051 2140  Password: Graph) 16 Nov Peter Bradshaw, Simon Fraser University A rainbow connectivity threshold for random graph families Given a family G of graphs on a common vertex set X, we say that G is rainbow connected if for every vertex pair u, v ∈ X, there exists a path from u to v that uses at most one edge from each graph of G. We consider the case that G contains s graphs, each sampled randomly from G(n, p), with n = |X| and p = c log n / sn , where c > 1 is a constant. We show that there exists a threshold of at most three consecutive integer values such that when s is greater than or equal to this threshold, G is a.a.s. rainbow connected, and when s is below this threshold, G is a.a.s. not rainbow connected. Joint work with Bojan Mohar.

### Summer 2021

##### Joy Morris, University of Lethbridge
Lexicographic products and wreath products
Abstract: I will present a history and overview of some of the work that has been done on the lexicographic product of graphs, and related generalisations. The focus of my talk will be on the automorphism groups of such graphs, and the relationship to the wreath product of permutation groups.
##### Xiang-dong Hou, University of South Florida
On the number of equivalence classes of boolean functions
Abstract: Two Boolean functions from $\Bbb F_2^n$ to $\Bbb F_2$ are called (affine) equivalent if one can be obtained from the other through an invertible affine transformation of the variables followed by an addition of an affine function. Most coding theoretic and cryptographic properties of Boolean functions are preserved under this equivalence. Let $N_n$ denote the number of equivalence classes of Boolean functions in $n$ variable. No explicit formula for $N_n$ is known. A long-standing open question by MacWilliams and Sloane asks for an asymptotic formula for $N_n$ as $n\to\infty$. Recently, we find a solution to this question. (Abstract in PDF)
##### Fan Chung, University of California San Diego
Trees and forests in Green's functions of a graph

Abstract: The Green's functions of a graph are the pseudo inverses of the Laplacians and therefore are useful for solving many types of Laplace equations in discrete settings.In this talk, we will give  combinatorial interpretations of Green's functions in terms of counting trees and forests in a graph. We will also mention several applications concerning the pagerank algorithms and the hitting time for random walks.

##### Akbar Rafiey, SFU
Fast and Private Submodular and k-Submodular Functions Maximization with Matroid Constraints
Abstract: The problem of maximizing nonnegative monotone submodular functions under a certain constraint has been intensively studied in the last decade, and a wide range of efficient approximation algorithms have been developed for this problem. Many machine learning problems, including data summarization and influence maximization, can be naturally modeled as the problem of maximizing monotone submodular functions. However, when such applications involve sensitive data about individuals, their privacy concerns should be addressed.
In this paper, we study the problem of maximizing monotone submodular functions subject to matroid constraints in the framework of differential privacy. We provide (1−1/e)-approximation algorithm which improves upon the previous results in terms of approximation guarantee. This is done with an almost cubic number of function evaluations in our algorithm. Moreover, we study k-submodularity, a natural generalization of submodularity. We give the first 1/2-approximation algorithm that preserves differential privacy for maximizing monotone k-submodular functions subject to matroid constraints. The approximation ratio is asymptotically tight and is obtained with an almost linear number of function evaluations.
Joint work with Yuichi Yoshida (http://proceedings.mlr.press/v119/rafiey20a.html)
##### Rebecca Patrias, University of St Thomas
Webs and tableau promotion
Abstract: We will start with an introduction to webs, standard Young tableau promotion, and the relationship between web rotation and tableau promotion. We will then discuss increasing tableaux---a K-theoretic analogue of SYT---and K-promotion. A big open question in this area deals with the order of K-promotion on increasing tableaux. We will talk about results in the 3-row case (in joint work with O. Pechenik) as well as current efforts to relate this problem to web promotion (joint with O. Pechenik, J. Striker, and J. Tymoczko).
##### Haggai Liu
Enumerative Properties of Cogrowth Series on Free products of Finite Groups
Abstract: Given a group G with a finite set of generators, S, it is natural to ask if the product of n generators from S evaluate to the identity. The enumerative version of this problem, known as the cogrowth problem, counts the number of such products and studies the associated counting sequence. Many cogrowth sequences are known. We focus on the free products of finite groups: Specifically, cyclic and dihedral groups. Such groups have the property that their cogrowth generating functions are algebraic functions, and thus, are solutions to implicit polynomial equations. Using algebraic elimination techniquesand free probability theory, we establish upper bounds on the degrees of the polynomial equations that they satisfy. This has implications for asymptotic enumeration, and makes it theoretically possible to determine the functions explicitly.
##### Christin Bibby, Louisiana State University
Combinatorics of orbit configuration spaces
Abstract: From a group action on a space, define a variant of the configuration space by insisting that no two points inhabit the same orbit. When the action is almost free, this "orbit configuration space" is the complement of an arrangement of subvarieties inside the cartesian product, and we use this structure to study its topology. We give an abstract combinatorial description of its poset of layers (connected components of intersections from the arrangement) which turns out to be of much independent interest as a generalization of partition and Dowling lattices. The close relationship to these classical posets is then exploited to give explicit cohomological calculations.
##### Yifan Jing, UIUC
Minimal and nearly minimal measure expansions in locally compact groups
Abstract: In 1964, Kemperman proved the following continuous nonabelian counterpart of the Cauchy-Davenport theorem: If G is a connected unimodular locally compact group with a left (and hence right) Haar measure \mu, A, B \subseteq G are nonempty and compact, and AB is their product set, then \mu(AB) \geq \min\{ \mu(A) + \mu(B), \mu(G)\}.
I will present the recent joint works with Jinpeng An, Chieu-Minh Tran and Ruixiang Zhang where we determine the conditions for the equality to happen or nearly happen in the above inequality. Our results and methods answer several questions by Griesmer, Henstock, Hrushovski, Kemperman, Macbeath, McCrudden, and Tao.
##### Sophie Spirkl, Waterloo
The complexity of list-5-colouring with a forbidden induced sugbraph
Abstract: A k-list-assignment for a graph G is a function L from V(G) to the set of subsets of {1,…,k}. The list-k-colouring problem asks, given G and a k-list-assignment L, is there a colouring f of G with f(v) in L(v) for all v in V(G)? This generalizes the k-colouring problem (where we use L(v)={1,…,k} for every vertex). For k at least 3, both k-colouring and list-k-colouring are NP-hard, which motivates studying the complexity of these problems when the input is restricted to H-free graphs (for a fixed H, excluded as an induced subgraph).
I will present an algorithm for list-5-colouring restricted to H-free graphs for all H which consist of connected components each of which is a 3-vertex path. This, together with previous results, gives a complete answer to the question, “for which H is list-5-colouring restricted to H-free graphs NP-hard? Joint work with Sepehr Hajebi and Yanjia Li.
##### Anurag Bishnoi, TU Delft
The minimum degree of minimal Ramsey graphs for cliques