#### Contact Info

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

Friday, June 30, 2023 3:30 PM EDT

**Title:** Ramsey degrees, big and small

Speaker: | Andy Zucker |

Affiliation: | University of Waterloo |

Location: | MC 5501 |

**Abstract:** Many of the seminal results in finite Ramsey theory can be phrased by saying that a certain class of finite structures has the *Ramsey property*, such as the ordinary finite Ramsey theorem (the class of finite linear orders), the dual Ramsey theorem (the class of finite lex-ordered Boolean algebras), the Graham-Leeb-Rothschild theorem (the class of lex-ordered, finite-dimensional vector spaces over a fixed finite field), and the Nesetril-Rodl theorem (the class of finite ordered triangle-free graphs, among many others).

Thursday, June 29, 2023 3:00 PM EDT

**Title: **Minors of random representable matroid over finite fields

Speaker: |
Jane Gao |

Affiliation: |
University of Waterloo |

Location: |
MC 5479 |

**Abstract: **Consider a random n by m matrix A over GF(q) where every column has k nonzero elements, and let M[A] be the matroid represented by A. In the case that q=2, Cooper, Frieze and Pegden (RSA 2019) proved that given a fixed binary matroid N, if k is sufficiently large, and m/n is sufficiently large (both depending on N), then whp. M[A] contains N as a minor. We improve their result by determining the sharp threshold (of m/n) for the appearance of a fixed q-nary matroid N as a minor of M[A], for every k\ge 3, and every prime q. This is joint work with Peter Nelson.

Monday, June 26, 2023 2:30 PM EDT

**Title: **Restricted Intersections and the Sunflower Problem

Speaker: |
Jeremy Chizewer |

Affiliation: |
University of Waterloo |

Location: |
MC 5479 |

**Abstract: **A sunflower with $r$ petals is a collection of $r$ sets over a ground set $X$ such that every element in $X$ is in no set, every set, or exactly one set. Erdos and Rado showed that a family of sets of size $n$ contains a sunflower if there are more than $n!(r-1)^n$ sets in the family. Alweiss et al. and subsequently Rao improved this bound to $(O(r \log(rn))^n$.

Monday, June 26, 2023 1:00 PM EDT

**Title: **A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut Covering Problem, Part II

Speaker: |
Nathan Benedetto Proenca |

Affiliation: |
University of Waterloo |

Location: |
MC 6029 |

**Abstract: **A cut in a graph \(G = (V, E)\) is a set of edges which has precisely one endpoint in \(S\), for a given subset \(S\) of \(V\). The fractional cut-covering number is the optimal value of a linear programming relaxation for the problem of covering each edge by a set of cuts. We define a semidefinite programming relaxation of fractional cut covering whose approximate optimal solutions may be rounded into a fractional cut cover via a randomized algorithm.

Monday, June 26, 2023 11:30 AM EDT

**Title: **Diagonal coefficients of Kirchhoff polynomials of 2k-regular graphs and the proof of the c_2 completion conjecture

Speaker: |
Karen Yeats |

Affiliation: |
University of Waterloo and Perimeter Institute |

Location: |
Please contact Sabrina Lato for Zoom link |

**Abstract: **I have for many years been interested in graph invariants with the same symmetries as the Feynman period. Recently Erik Panzer found a new such invariant coming from a particular coefficient of the Martin polynomial. Together we used this to prove an over 10 year old conjecture on an arithmetic graph invariant known as the c_2 invariant, and came to understand that diagonal coefficients of Kirchhoff polynomials tie together many of the known graph invariants with the symmetries of Feynman periods and unlock previously inaccessible proofs.

Joint work with Erik Panzer.

Friday, June 23, 2023 1:00 PM EDT

**Title:** The rank of sparse symmetric matrices over arbitrary fields

Speaker: | Noela Müller |

Affiliation: | TU/e Eindhoven University of Technology |

Location: | MC 5501 |

**Abstract:** Consider a sequence of sparse Erdös-Rényi random graphs (G_{n,d/n})_n on n vertices with edge probability d/n. Moreover, we equip the edges of G_{n,d/n} with prescribed non-zero edge weights chosen from an arbitrary field F.

Thursday, June 22, 2023 1:00 PM EDT

**Title: **Poset subHopf algebras from growth models in causal set theory and quantum field theory

Speaker: |
Karen Yeats |

Affiliation: |
University of Waterloo |

Location: |
MC 5501 and Zoom - please contact Oliver Pechenik for the Zoom link |

**Abstract: **In a story some of you have heard from me before, we get subHopf algebras of the Connes-Kreimer Hopf algebra of rooted trees from certain simple tree classes which correspond to solutions to combinatorial analogues of Dyson-Schwinger equations in quantum field theory. Another important subHopf algebra of the Connes-Kreimer Hopf algebra is the Connes-Moscovici Hopf algebra which can be viewed as coming from rooted trees grown by adding leaves.

Monday, June 19, 2023 2:30 PM EDT

**Title:** An invitation to monotone operators and their applications in optimization

Speaker: |
Walaa Moursi |

Affiliation: |
University of Waterloo |

Location: |
MC 5479 |

**Abstract: **In this talk, I give an overview of the theory of monotone operators and its connection to optimization algorithms. This talk is a good introduction to how abstract theoretical results serve as bases for successful algorithms in practice.

Monday, June 19, 2023 1:00 PM EDT

**Title:** A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut Covering Problem

Speaker: |
Nathan Benedetto Proenca |

Affiliation: |
University of Waterloo |

Location: |
MC 6029 |

**Abstract: **

A cut in a graph \(G = (V, E)\) is a set of edges which has precisely one endpoint in \(S\), for a given subset \(S\) of \(V\). The fractional cut-covering number is the optimal value of a linear programming relaxation for the problem of covering each edge by a set of cuts. We define a semidefinite programming relaxation of fractional cut covering whose approximate optimal solutions may be rounded into a fractional cut cover via a randomized algorithm.

Monday, June 19, 2023 11:30 AM EDT

**Title: **Partial geometric designs, directed strongly regular graphs, and association scheme

Speaker: |
Sung Song |

Affiliation: |
Iowa State University |

Location: |
Please contact Sabrina Lato for Zoom link |

**Abstract: **A partial geometric design with parameters $(v, b, k, r; \alpha, \beta)$ is a tactical configuration $(P, \mathcal{B})$ (with $|P|=v$, $|\mathcal{B}|=b$, every point $p\in P$ belonging to $r$ blocks, and every block $B\in\mathcal{B}$ consisting of $k$ points) satisfying the property:

{for any pair $(p, B)\in P\times \mathcal{B}$, the number of flags $(q, C)$ with $q\in B$ and $C\ni p$ equals to $\alpha \mbox{ if } p\notin B$ and to $\beta \mbox{ if } p\in B$.}

Neumaier studied partial geometric designs in detail in his article, ``$t\frac12$-designs," [JCT A {\bf 28}, 226-248 (1980)]. He investigated their connection with strongly-regular graphs and gave various characterizations of partial geometries, bipartite graphs, symmetric 2-designs, and transversal designs in terms of partial geometric designs.

Friday, June 16, 2023 3:30 PM EDT

**Title:** Error bounds for conic feasibility problems: case studies on the exponential cone

Speaker: | Ting Kei Pong |

Affiliation: | The Hong Kong Polytechnic University |

Location: | MC 5501 |

**Abstract:** Conic feasibility problems naturally arise from linear conic programming problems. An understanding of error bounds for these problems is instrumental in the design of termination criteria for conic solvers and the study of convergence rate of algorithms.

Thursday, June 15, 2023 3:00 PM EDT

**Title: **To be announced

Speaker: |
Rutger Campbell |

Affiliation: |
University of Waterloo |

Location: |
MC 5501 |

Thursday, June 15, 2023 1:00 PM EDT

**Title: **Monomial ideals, Galois closures, and Hilbert schemes of points

Speaker: |
Matthew Satriano |

Affiliation: |
University of Waterloo |

Location: |
MC 5501 and Zoom - please contact Oliver Pechenik for the Zoom link |

**Abstract: **Manjul Bhargava and the speaker introduced a functorial Galois closure operation for finite-rank ring extensions, generalizing constructions of Grothendieck and Katz-Mazur. In this talk, we use Galois closures to construct new components of Hilbert schemes of points, which are fundamental objects in algebraic geometry whose component structure is largely mysterious. We answer a 35 year old open problem posed by Iarrobino by constructing an infinite family of low dimensional components. This talk is based on joint work with Andrew Staal. **No prior knowledge of Hilbert schemes will be assumed.**

Monday, June 12, 2023 2:30 PM EDT

**Title: **Research in Applications

Speaker: |
Ricardo Fukasawa |

Affiliation: |
University of Waterloo |

Location: |
MC 5479 |

**Abstract: **In this talk I will present my personal experiences in doing research involving applications. I will go over some of my work, presenting some of the key aspects that are involved, and trying to take stock of a few lessons learned.

Monday, June 12, 2023 11:30 AM EDT

**Title: **L-systems and the Lovasz number

Speaker: |
William Linz |

Affiliation: |
University of South Carolina |

Location: |
Please contact Sabrina Lato for Zoom link |

**Abstract: **For positive integers n and k, an L-system is a collection of k-uniform subsets of a set of size n whose pairwise intersection sizes all lie in in the set L. The maximum size of an L-system is equal to the independence number of a certain union of graphs in the Johnson scheme. The Lovasz number is a semidefinite programming approximation of the independence number of a graph. In this talk, we survey the relationship between the maximum size of an L-system and the Lovasz number, illustrating examples both where the Lovasz number is a good approximation and where it is a bad approximation.

Friday, June 9, 2023 3:30 PM EDT

**Title:** Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse

Speaker: | Shi Li |

Affiliation: | University at Buffalo |

Location: | MC 5501 |

**Abstract:** I will present the online algorithms for unrelated-machine load balancing problem with recourse. First, we shall present a (2+\epsilon)-competitive algorithm for the problem with O_\epsilon(\log n) amortized recourse per job.

Monday, June 5, 2023 1:00 PM EDT

**Title: **Extended Formulations for the Colonel Blotto Game

Speaker: |
Ian DeHaan |

Affiliation: |
University of Waterloo |

Location: |
MC 6029 |

**Abstract: **Suppose you want to replace Doug Ford as premier. To beat him, you need to win as many seats as possible. You have some finite amount of resources to allocate across all seats - if you spend more on a seat than Ford does, you will win that seat. How should you allocate your resources to maximize your expected number of seats?

Monday, June 5, 2023 11:30 AM EDT

**Title: **Quantum walk state transfer on a hypercube

Speaker: |
Martin Stefanak |

Affiliation: |
Czech Technical University |

Location: |
Please contact Sabrina Lato for Zoom link |

**Abstract: **We investigate state transfer on a hypercube by means of a quantum walk where the sender and the receiver vertices are marked by weighted loops.

Monday, June 5, 2023 10:00 AM EDT

**Title: **Approximation algorithms for dense quantum Hamiltonians using convex relaxations

Speaker: |
Anirban Chowdhury |

Affiliation: |
University of Waterloo |

Location: |
MC 5479 |

**Abstract: **Computing ground-state energy and partition functions for quantum Hamiltonian systems are problems of broad applicability in physics. These are also natural generalizations of well-studied classical computational tasks such as maximum constraint satisfaction and computing partition functions of Ising models. In this talk, I will present new classical approximation algorithms for these problems in the case of dense quantum Hamiltonians.

Friday, June 2, 2023 3:30 PM EDT

**Title:** On the complexity of quantum partition functions

Speaker: | David Gosset |

Affiliation: | University of Waterloo |

Location: | MC 5501 |

**Abstract:** Quantum complexity theory has been intertwined with the study of quantum many-body systems ever since Kitaev's insight that computing their ground energies is an intractable quantum constraint satisfaction problem that is complete for a quantum generalization of NP.

Thursday, June 1, 2023 3:00 PM EDT

**Title: **Excluded-minor characteristics

Speaker: | Jim Geelen |

Affiliation: | University of Waterloo |

Location: | MC 5501 |

**Abstract: **We review the excluded-minor characterizations for matroids over small fields and discuss the obstacles towards finding such a characterization for GF(5)-representability.

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1

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 our Office of Indigenous Relations.