# Discrete Math Seminars

Most Tuesdays on Zoom.  Time TBA

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 on Zoom (Meeting-ID: 224 412 7257). 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: Shuxing Li (shuxingl@sfu.ca)

## 2021 Talks

### Fall 2021

 09 Nov Andrei Bulatov

### 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