Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Title: Online edge colouring
Speaker: | David Wajc |
Affiliation: | Technion — Israel Institute of Technology |
Location: | MC 5501 |
Abstract: Vizing's Theorem provides an algorithm that edge colors any graph of maximum degree Δ can be edge-colored using Δ+1 colors, which is necessary for some graphs, and at most one higher than necessary for any graph. In online settings, the trivial greedy algorithm requires 2Δ-1 colors, and Bar-Noy, Motwani and Naor in the early 90s showed that this is best possible, at least in the low-degree regime.
Title: Nash-Williams Orientation for Infinite Graphs
Speaker: | Amena Assem Abd-AlQader Mahmoud |
Affiliation: | University of Waterloo |
Location: | MC 5501 |
Abstract: Nash-Williams proved in 1960 that an edge-connectivity of 2k is sufficient for a finite graph to admit a k-arc-connected orientation and conjectured that the same holds for infinite graphs. We show that the conjecture is true for locally finite graphs with countably many ends.
This is joint work with Max Pitz and Marcel Koloschin.
Title: Prophets, philosophers, and online algorithms
Speaker: | David Wajc |
Affiliation: | Technion |
Location: | MC 6029 |
Abstract: In online Bayesian selection problems, a seller is faced with a stream of buyers arriving sequentially. Each arriving buyer makes, for each item on sale, a take-it-or-leave-it offer drawn from some known distribution, which the seller must immediately either accept or decline. It is common to compare the seller's benefit to the optimal offline solution, obtained by a "prophet'' who knows the future. However, the seller might not even be able to compete with the optimal online algorithm, which may be computationally intractable to run. In this case the optimal online algorithm is obtained by a "philosopher'' with sufficient time to think (compute). In this talk I will discuss some developments on online algorithms efficiently approximating this philosopher.
Title: The Container method for Enumerating Triangle-free graphs
Speaker: | Amitha Vallapuram |
Affiliation: | University of Waterloo |
Location: | MC 5417 |
Abstract: The container method is a tool for bounding the number of independent sets in graphs and can be generalized to hypergraphs. It utilizes the observation that independent sets are found in clusters or “containers” within the graph. One application of this method is to bound the number of finite objects with some forbidden substructure. For example, we can bound the number of graphs on N vertices that do not contain K3 as a subgraph, that is, the number of Triangle-free graphs on N vertices. We will take a look at finding this bound using the container method.
Title: A threshold for fractional Sudoku completion
Speaker: | Peter Dukes |
Affiliation: | University of Victoria |
Location: | Please contact Sabrina Lato for Zoom link. |
Abstract: The popular puzzle game Sudoku presents a player with a 9-by-9 grid having some numbers filled in a few of the cells. The player must finish filling in numbers from 1 to 9 so that every row, column, and 3-by-3 box contains each of these numbers exactly once. We can extend Sudoku so that the boxes are $h$-by-$w$, and the overall array is $n$-by-$n$, where $n=hw$. The puzzle is now similar to completing a latin square of order n, except of course that Sudoku has an additional box condition.
Title: Wires, bits, and the cost of sorting
Speaker: | Samuel Jaques |
Affiliation: | University of Waterloo |
Location: | MC 5501 |
Abstract: How hard is it to sort a list of n integers? A basic course on algorithms says it's O(n log n) time, but what if the list is enormous - so big you would need to cover the surface of the moon just to store it?
Title: Sublinear Regret 101
Speaker: | Nathan Benedetto Proenca |
Affiliation: | University of Waterloo |
Location: | MC 6029 |
Abstract: The purpose of this talk is to look at specific algorithms for online convex optimization attaining sublinear regret. In this way, we can get more familiar with the online learning setup and with the ingredients necessary to attain sublinear regret.
Title: Polarization operators in superspace
Speaker: | Kelvin Chan |
Affiliation: | York University |
Location: | MC 6029 |
There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:00 pm.
Abstract: The classic coinvariant space is a graded representation of the symmetric group with deep connections to permutation statistics and Hall-Littlewood polynomials. Its generalization, the diagonal harmonics, has a rich connection to Macdonald polynomials and the q,t-Catalan numbers. In this talk, we consider the variant of the classical coinvariant story in the superspace. We briefly survey its connections and recent developments. We introduce polarization operators and discuss a new basis for its alternating component. We also discuss a folklore on cocharge and propose a basis for the super harmonics.
Title: On the intersection density of transitive groups with degree 3p
Speaker: | Sarobidy Razafimahatratra |
Affiliation: | University of Primorska |
Location: | Please contact Sabrina Lato for Zoom link. |
Abstract: Given a finite transitive group $G\leq \operatorname{Sym}(\Omega)$, a subset $\mathcal{F}\subset G$ is intersecting if any two elements of $\mathcal{F}$ agree on some elements of $\Omega$. The \emph{intersection density} of $G$ is the rational number $\rho(G)$ given by the maximum ratio $\frac{|\mathcal{F}|}{|G|/|\Omega|}$, where $\mathcal{F}$ runs through all intersecting sets of $G$.
Most results on the intersection density focus on particular families of transitive groups. One can look at problems on the intersection density from another perspective. Given an integer $n\geq 3$, we would like to determine the possible intersection densities of transitive groups of degree $n$. This problem turns out to be extremely difficult even in the case where $n$ is a product of two primes.
Title: Diagonal coefficients, graph invariants with the symmetries of Feynman integrals, and the proof of the c_2 completion conjecture
Speaker: | Karen Yeats |
Affiliation: | University of Waterloo |
Location: | MC 5501 |
Abstract: In a scalar field theory the contribution of a Feynman diagram to the beta function of the theory, the Feynman period, can be written as an integral in terms of the (dual) Kirchhoff polynomial of the graph.
Title: Online Convex Optimization
Speaker: | Victor Sanches Portella |
Affiliation: | University of British Columbia |
Location: | MC 6029 |
Abstract: Online learning (OL) is a theoretical framework for learning with data online. Moreover, we usually make no assumptions on the distribution of the data, allowing it even to be adversarial to the learner. Maybe surprisingly, we can still design algorithms that, in some sense, “successfully learn” in this setting. This level of generality makes many of the ideas, algorithms, and techniques from OL useful in applications in theoretical computer science, optimization in machine learning, and control. In this talk I will give a brief introduction to the key concepts in online learning and mention a few topics within or adjacent to online learning that I believe cover fundamental ideas in OL and/or with interesting open research questions.
Title: Several Gyrafas-Sumner-type results for treewidth
Speaker: | Sepehr Hajebi |
Affiliation: | University of Waterloo |
Location: | MC 5417 |
Abstract: For a graph parameter which goes unbounded at both ends of a robust sparsity spectrum, one naturally asks if it is bounded anywhere in the middle. This is modelled after a well-known conjecture of Gyarfas and Sumner, asking the above question for the chromatic number as the parameter and the girth as the measure of sparsity. We look through this lens at the treewidth as the parameter and present a number of recent results answering the corresponding question in various settings. If time permits, we’ll try to sketch a proof as well as some directions for future work.
This is joint work with Bogdan Alecu, Maria Chudnovsky, Sophie Spirkl and partly with Tara Abrishami.
Title: Filtered deformations of commutative algebras
Speaker: | Jason Bell |
Affiliation: | University of Waterloo |
Location: | MC 6029 |
Note: There will be no pre-seminar.
Abstract: We’ll look at different ways of deforming the multiplicative structure of “classical” algebras to obtain new algebras and explain how this algebraic structure can often be understood combinatorially. We’ll then look at a special class of algebras one can produce this way called filtered deformations and we’ll discuss a conjecture of Etingof which asserts that in positive characteristic that filtered deformations of commutative rings should be in some natural sense very close to being commutative themselves. Not much background will be assumed.
Title: Quantum Automorphism Groups of Trees
Speaker: | Prem Nigam Kar |
Affiliation: | Technical University of Denmark |
Location: | Please contact Sabrina Lato for Zoom link. |
Abstract: We give a characterisation of quantum automorphism groups of trees. In particular, for every tree, we show how to iteratively construct its quantum automorphism group using free products and free wreath products. This can be considered a quantum version of Jordan’s theorem for the automorphism groups of trees. This is one of the first characterisations of quantum automorphism groups of a natural class of graphs with quantum symmetry. This talk is based on the following preprint: https://arxiv.org/abs/2311.04891
Title: Hypergraph Matchings Avoiding Forbidden Submatchings
Speaker: | Luke Postle |
Affiliation: | University of Waterloo |
Location: | MC 5501 |
Abstract: We overview a general theory for finding perfect or almost perfect matchings in a hypergraph G avoiding a given set of forbidden submatchings (which we view as a hypergraph H where V(H)=E(G)).
Title: Multiplicative Weight Update (MWU) Method for Solving Packing/Covering LPs
Speaker: | Sepehr Assadi |
Affiliation: | University of Waterloo |
Location: | MC 6029 |
Abstract: I will present an overview of the MWU technique for solving Packing/Covering LPs easily and efficiently. The talk will be based on a combination of results from the following resources: (1) https://epubs.siam.org/doi/pdf/10.1137/1.9781611976014.11 (2) https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf
Title: Linear relations and Lorentzian property of chromatic symmetric functions
Speaker: | Alejandro Morales Borrero |
Affiliation: | Université du Québec à Montréal |
Location: | MC 6029 |
There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:00 pm.
Abstract: The chromatic symmetric function (CSF) of Dyck paths of Stanley and its Shareshian Wachs q-analogue (q-CSF) have important connections to Hessenberg varieties, diagonal harmonics and LLT polynomials. In the, so called, abelian case they are related to placements of non-attacking rooks by results of Stanley-Stembridge (1993) and Guay-Paquet (2013).
Title: Distance-regular graphs that support a uniform structure
Speaker: | Roghayeh Maleki |
Affiliation: | University of Primorska |
Location: | Please contact Sabrina Lato for Zoom link. |
Abstract: Given a connected bipartite graph $G$, the adjacency matrix $A$ of $G$ can be decomposed as $A=L+R$, where $L=L(x)$ and $R=R(x)$ are respectively the lowering and the raising matrices with respect to a certain vertex $x$. The graph $G$ has a \textit{uniform structure} with respect to $x$ if the matrices $RL^2$, $LRL$, $L^2R$, and $L$ satisfy a certain linear dependency.
Title: Algorithmic Tools for Congressional Districting: Fairness via Analytics
Speaker: | David B. Shmoys |
Affiliation: | Cornell University |
Location: | MC 5501 |
Abstract: The American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. To date, computational solutions mostly focus on drawing unbiased maps by ignoring political and demographic input, and instead simply optimize for compactness and other related metrics.
Title: The Tutte Polynomial, Bipartite Representations of Graphs, and Grid Walking
Speaker: | Josephine Reynes |
Affiliation: | University of Waterloo |
Location: | MC 5417 |
Abstract: The Tutte Polynomial has many equivalent definitions. It can be defined by a deletion-contraction relation with the terms determined by the sequence of contractions, deletions, loops, and isthmi. This definition is independent of edge order. Another definition relies on a fixed edge ordering and examines the edge activities over maximal spanning forests. There is a direct relationship between edge activity and deletion/contraction for a given edge ordering. Furthermore, the monomials of the Tutte polynomial can be interpreted as grid walks. This allows for an approach to the Tutte polynomial on hypergraphs by examining the grid walks of the bipartite representation of the graph.
Title: Extended Schur Functions and Bases Related by Involutions
Speaker: | Spencer Daugherty |
Affiliation: | North Carolina State University |
Location: | MC 6029 |
There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:00 pm.
Abstract: The extended Schur basis and the shin basis generalize the Schur functions to the dual algebras of the quasisymmetric functions and the noncommutative symmetric functions. We define a creation operator and a Jacobi-Trudi rule for certain shin functions and show that a similar matrix determinant expression does not exist for every shin function.
Title: Kemeny’s constant and random walks on graphs
Speaker: | Jane Breen |
Affiliation: | Ontario Tech University |
Location: | Please contact Sabrina Lato for Zoom link. |
Abstract: Kemeny's constant is an interesting and useful quantifier of how well-connected the states of a Markov chain are. This comes to the forefront when the Markov chain in question is a random walk on a graph, in which case Kemeny's constant is interpreted as a measure of how `well-connected' the graph is. Though it was first introduced in the 1960s, interest in this concept has recently exploded. This talk will provide an introduction to Markov chains, an overview of the history of Kemeny’s constant, discussion of some applications, and a survey of recent results, with an emphasis on those that are extensions or generalizations of simple random walks on graphs, to complement Sooyeong’s talk from two weeks ago.
Title: The Chambolle-Pock algorithm revisited: splitting operator and its range with applications
Speaker: | Walaa Moursi |
Affiliation: | University of Waterloo |
Location: | MC 5501 |
Abstract: Primal-dual hybrid gradient (PDHG) is a first-order method for saddle-point problems and convex programming introduced by Chambolle and Pock. Recently, Applegate et al. analyzed the behavior of PDHG when applied to an infeasible or unbounded instance of linear programming, and in particular, showed that PDHG is able to diagnose these conditions.
Title: Snake decompositions of lattice path matroids
Speaker: | Jerónimo Valencia-Porras |
Affiliation: | University of Waterloo |
Location: | MC 6029 |
There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:00 pm.
Abstract: We study Ehrhart theory of lattice path matroid polytopes motivated by a conjecture by De Loera, Haws and Köppe. More specifically, we aim to understand the h*-vector of this family of matroid polytopes. To do so, we subdivide them into smaller matroid polytopes such that each piece is a snake, which are matroids such that their matroid polytope coincides with the order polytope of a fence poset.
Title: Graphs that Admit Orthogonal Matrices
Speaker: | Shaun Fallat |
Affiliation: | University of Regina |
Location: | Please contact Sabrina Lato for Zoom link. |
Abstract: Given a simple graph $G=(\{1,\ldots, n},E), we consider the class $S(G)$ of real symmetric $n \times n$ matrices $A=[a_{ij}]$ such that for $i\neq j$, $a_{ij}\neq 0$ iff $ij \in E$. Under the umbrella of the inverse eigenvalue problem for graphs (IEPG), $q(G)$ - known as the minimum number of distinct eigenvalues of $G$ - has emerged as one of the most well-studied parameters of the IEPG. Naturally, characterizing graphs $G$ for which $q(G) \leq, =, \geq k$ is an important step for studying the IEPG.
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within the Office of Indigenous Relations.