Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 5198884567, ext 33038
PDF files require Adobe Acrobat Reader.
Sun  Mon  Tue  Wed  Thu  Fri  Sat 

30

31

1

2

5








6

8

9

12







13

15

16

19







20

22

23

26







27

29

30

1

2

3








Title: The Hat Guessing Number of Graphs
Speaker: Jeremy Chizewer Affiliation: University of Waterloo Location: MC 5479 in personAbstract: The hat guessing number HG(G) of a graph G on n vertices is defined in terms of the following game: n players are placed on the n vertices of G, each wearing a hat whose color is arbitrarily chosen from a set of q possible colors. Each player can see the hat colors of his neighbors, but not his own hat color. All of the players are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed.
Title: Approximation Algorithms for Stochastic Knapsack
Speaker: David Aleman Affiliation: University of Waterloo Location: MC 6029 or contact Rian NeAbstract: The classical Knapsack problem takes as input a set of items with some fixed nonnegative values and weights. The goal is to compute a subset of items of maximum total value, subject to the constraint that the total weight of these elements is at most a given limit. In this talk we review a paper by Gupta, Krishnaswamy, Molinaro and Ravi, in which the following stochastic variation of this problem is considered: the value and weight of each item are correlated random variables with known, arbitrary distributions.
Title: Sylvester, Gallai, and their complex relatives
Speaker: Jim Geelen Affiliation: University of Waterloo Location: MC 5501 or contact Melissa Cambridge for Zoom linkAbstract: Given any finite set of points in the real plane, not all collinear, there is a line in the plane that contains exactly two of them. This pretty result was conjectured by Sylvester in 1893 and proved by Gallai in 1944. We will present an extension of the result to higher dimensional complex spaces and discuss some related conjectures. This is joint work with Matthew Kroeker.
Title: Cayley graphs, association schemes and state transfer
Speaker: Soffía Árnadóttir Affiliation: Technical University of Denmark Location: contact Sabrina Lato for Zoom linkAbstract: The aim of this talk is to give some examples of how association schemes can be used as a tool to study certain properties of Cayley graphs. In particular, they contribute to our longterm goal of characterizing perfect state transfer in Cayley graphs. The talk is based on the following paper https://arxiv.org/abs/2204.09802.
Title: Recursions and Proofs in CoxeterCatalan combinatorics
Speaker: Theo Douvropoulos Affiliations: U Mass Amherst Location: MC 5479 or contact Olya Mandelshtam for Zoom linkAbstract: The collection of parking functions under a natural Snaction (which has Catalanmany orbits) has been a central object in Algebraic Combinatorics since the work of Haiman more than 30 years ago. One of the lines of research spawned around it was towards defining and studying analogous objects for real and complex reflection groups W; the main candidates are known as the Wnonnesting and Wnoncrossing parking functions.
Title: Stochastic Minimum Norm Combinatorial Optimization
Speaker: Sharat Ibrahimpur Affiliation: Location: MC 6029 or contact Rian Neogi for Zoom linkAbstract: In this work, we introduce and study stochastic minimumnorm optimization. We have an underlying combinatorial optimization problem where the costs involved are random variables with given distributions; each feasible solution induces a random multidimensional cost vector. The goal is to find a solution that minimizes the expected norm of the induced cost vector, for a given monotone, symmetric norm. We give a framework for designing approximation algorithms for stochastic minimumnorm optimization and apply it to give approximation algorithms for stochastic minimumnorm versions of load balancing and spanning tree problems.
Title: Forbidding some induced cycles in a graph
Speaker: Linda Cook Affiliation: Institute for Basic Science, South Korea Location: MC 5501 or contact Melissa Cambridge for Zoom linkAbstract: We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain lengths in a graph has deep structural implications. In 2006, Chudnovksy, Seymour, Robertson, and Thomas famously proved that a graph is perfect if and only if it does not contain an odd hole or a complement of an odd hole. In 2002, Conforti, Cornuéjols, Kapoor, and Vušković provided a structural description of the class of evenholefree graphs.
Title: Graphs, curvature, and local discrepancy
Speaker: Paul Horn Affiliation: University of Denver Location: contact Sabrina Lato for Zoom linkAbstract: Spectral graph theory, the use of eigenvalues to study graphs, gives an important window into many properties of graphs. One of the reasons for this is that the eigenvalues can be used to certify the `pseudorandomness' of the edge set of a graph. In recent years, several notions of discrete curvature have been introduced that gives a 'local' way (depending on the neighborhood structure of vertices) to study some of the same properties that eigenvalues can capture.
Title: The Hat Guessing Number of Graphs
Speaker: Jeremy Chizewer Affiliation: University of Waterloo Location: MC 6029Abstract: The hat guessing number HG(G) of a graph G on n vertices is defined in terms of the following game: n players are placed on the n vertices of G, each wearing a hat whose color is arbitrarily chosen from a set of q possible colors. Each player can see the hat colors of his neighbors, but not his own hat color. All of the players are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed. The hat guessing number HG(G) is the largest integer q such that there exists a guessing strategy guaranteeing at least one correct guess for any hat assignment of q possible colors.
Title: Algorithms for Analytic Combinatorics in Several Variables
Speaker: Josip Smolcic Affiliation: University of Waterloo Location: MC 5479Abstract: In this presentation we will see how to apply the theory of complex analysis to study multivariate generating series by looking at several examples. Specifically, given a rational bivariate generating function G(x, y)/H(x, y) with coefficients f_{i, j} the objective is algorithmically determine asymptotic formulas to approximate f_{rn, sn} as n goes to infinity, for fixed positive integers r and s.
Title: Approximation algorithms for stochastic orienteering
Speaker: Madison Van Dyk Affiliation: University of Waterloo Location: MC 6029 or contact Rian Neogi for Zoom linkAbstract: This week we revisit the stochastic orienteering problem in which we are given a metric graph where each node has a deterministic reward and a random size. The goal is to adaptively decide on which nodes to visit to maximize the expected reward, while not exceeding the budget B on the distance plus the size of jobs processed.
Title: Approximating Weighted Connectivity Augmentation below Factor 2
Speaker: Vera Traub Affiliation: Research Institute for Discrete Mathematics, University of Bonn Location: MC 5501 or contact Melissa Cambridge for Zoom linkAbstract: The Weighted Connectivity Augmentation Problem (WCAP) asks to increase the edgeconnectivity of a graph in the cheapest possible way by adding edges from a given set. It is one of the most elementary network design problems for which no betterthan2 approximation algorithm has been known, whereas 2approximations can be easily obtained through a variety of wellknown techniques.
Title: Exact Zarankiewicz numbers through linear hypergraphs
Speaker: Daniel Horsley Affiliation: Monash University Location: Contact Sabrina Lato for Zoom linkAbstract: The \emph{Zarankiewicz number} $Z_{2,2}(m,n)$ is usually defined as the maximum number of edges in a bipartite graph with parts of sizes $m$ and $n$ that has no $K_{2,2}$ subgraph. An equivalent definition is that $Z_{2,2}(m,n)$ is the greatest total degree of a linear hypergraph with $m$ vertices and $n$ edges. A hypergraph is \emph{linear} if each pair of vertices appear together in at most one edge. The equivalence of the two definitions can be seen by considering the bipartite incidence graph of the linear hypergraph.
Title: Asymptotics of the Euler characteristic of Kontsevich's commutative graph complex
Speaker: Michael Borinsky Affiliation: ETH, Zurich Location: MC 5479 or contact Olya Mandelshtam for Zoom linkAbstract: I will present results on the asymptotic growth rate of the Euler characteristic of Kontsevich's commutative graph complex. By a work of ChanGalatiusPayne, these results imply the same asymptotic growth rate for the topweight Euler characteristic of M_g, the moduli
space of curves, and establish the existence of large amounts of unexplained cohomology in this space. This asymptotic growth rate
follows from new generating functions for the edgealternating sum of graphs without odd automorphisms. I will give an overview on this
interaction between topology and combinatorics and illustrate the combinatorial and analytical tools that were needed to obtain these
generating functions.
Title: Greedy algorithm for stochastic matching is a 2approximatio
Speaker: Ian DeHaan Affiliation: University of Waterloo Location: MC 6029 or contact Rian Neogi for Zoom linkAbstract: We will discuss the greedy algorithm for the stochastic matching problem. In this problem, we are given an undirected graph where each edge is assigned a probability p_e in [0, 1] and each vertex is assigned a patience t_v in Z+. We begin each step by probing an edge e which is not adjacent to any edges in our matching. The probe will succeed with probability p_e, and if it does, we add e to our matching. Otherwise, we may not probe e again. We also may not probe edges adjacent to a vertex v more than t_v times. The goal is to maximize the number of edges we add to our matching.
Title: Integer programs with bounded subdeterminants and two nonzeros per row
Speaker: Stefan Weltge Affiliation: Technical University of Munich Location: MC 5501 or contact Eva Lee for Zoom linkAbstract: Determining the complexity of integer linear programs with integer coefficient matrices whose subdeterminants are bounded by a constant is currently a very actively discussed question in the field. In this talk, I will present a strongly polynomialtime algorithm for such integer programs with the further requirement that every constraint contains at most two variables. The core of our approach is the first polynomialtime algorithm for the weighted stable set problem on graphs that do not contain more than k vertexdisjoint odd cycles, where k is any constant. Previously, polynomialtime algorithms were only known for k = 0 (bipartite graphs) and for k = 1.
This is joint work with Samuel Fiorini, Gwenaël Joret, and Yelena Yuditsky, which recently appeared at FOCS this year.
Title: A recursive spectral bound for independence
Speaker: Bogdan Nica Affiliation: Indiana UniversityPurdue University Indianapolis Location: Contact Sabrina Lato for Zoom linkAbstract: We discuss an upper bound for the independence number of a graph, in the spirit of the wellknown Hoffman bound. Our bound involves the largest Laplacian eigenvalue of the graph; more surprisingly, it also involves the independence number of a certain induced graph. We illustrate the bound on several examples.
Title: kConnectedness and kFactors in the SemiRandom Graph Process
Speaker: Hidde Koerts Affiliation: University of Waterloo Location: MC 6029Abstract: The semirandom graph process is a single player graph game where the player is initially presented an edgeless graph with n vertices. In each round, the player is offered a vertex u uniformly at random and subsequently chooses a second vertex v deterministically according to some strategy, and adds edge uv to the graph. The objective for the player is then to ensure that the graph fulfils some specified property as fast as possible.
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 5198884567, 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 coordinated within the Office of Indigenous Relations.