#### Contact Info

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

Visit our COVID-19 information website to learn how Warriors protect Warriors.

Please note: The University of Waterloo is closed for all events until further notice.

Friday, October 19, 2018 — 1:00 PM EDT

**Title**: Primal-dual and Lagrangian relaxation techniques for k-median

Speaker: | Madison Van Dyk |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract**: We will develop primal-dual algorithms to obtain constant-factor approximations for the uncapacitated facility location problem.

Thursday, October 18, 2018 — 3:30 PM EDT

**Title**: Extending Thomassen’s Theorem to Two Faces

Speaker: | Joshua Nevin |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract**:

Let G be a planar graph and let L be a list-assignment for G in which there is a precolored edge on the outer face, every other vertex on the outer face has a list of size at least 3, and every other vertex in G has a list of size at least 5.

Thursday, October 18, 2018 — 1:30 PM EDT

**Title**: Graphs of Homomorphisms

Speaker: | Chris Godsil |

Affiliation: | University of Waterloo |

Room: | MC 6486 |

**Abstract**: If X and Y are graphs and f is a function on V (X) taking values in V (Y ), then the graph of

f is the subset formed by the pairs (x; f(x)) for x in V (X).

Wednesday, October 17, 2018 — 4:00 PM EDT

**Title**: Tutorial on back-propagation and automatic differentiation

Speaker: | Steve Vavasis |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract**: In this presentation, I'll cover the basics of automatic differentiation (AD).

Wednesday, October 17, 2018 — 3:30 PM EDT

**Title: **Basis Shape Loci and the Positive Grassmannian

Speaker: | Cameron Marcot |

Affiliation: | University of Waterloo |

Room: | MC 6483 |

**Abstract:** We study the set of k-dimensional planes in R^n admitting a basis of vectors with prescribed supports.

Friday, October 12, 2018 — 10:30 AM EDT

**Title:** Offline Assisted Group Key Exchange

Speaker: | Gareth Davies |

Affiliation: | Norwegian University of Science and Technology (NTNU) |

Room: | MC 5417 |

**Abstract:**

This talk will focus on the problem of forward secrecy in group key exchange (GKE), where most of the participants remain offline until they wish to compute the key.

Thursday, October 4, 2018 — 3:30 PM EDT

**Title**: Representable orientable matroids that are not real-representable

Speaker: | Rutger Campbell |

Affiliation: | University of Waterllo |

Room: | MC 5417 |

**Abstract**: In this talk we will have a brief introduction to oriented matroids and their relation to real-representability.

Thursday, October 4, 2018 — 1:30 PM EDT

**Title**: Controllable graphs

Speaker: | Chris Godsil |

Affiliation: | University of Waterloo |

Room: | MC 6486 |

**Abstract**: A graph is controllable if no eigenvector is orthogonal to the all-ones vector.

Wednesday, October 3, 2018 — 4:00 PM EDT

**Title**: Review of martingale theory, stochastic gradient descent, and adaptive line-line-search for stochastic optimization.

Speaker: | Courtney Paquette |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract**: With the rise of large data sets, practical algorithms for machine learning often use probability and statistics.

Friday, September 28, 2018 — 3:30 PM EDT

**Title:** The Shapiro-Shapiro Conjecture

Speaker: | Kevin Purbhoo |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

Given four lines in 3-space, can you find a fifth line that intersects the other four? How many?

This is the smallest non-trivial example of a "Schubert problem". The answer, in this case, is not hard to compute: there are two such lines. Generalizations of this fact date back to 19th century work of Schubert.

Thursday, September 27, 2018 — 3:30 PM EDT

**Title**: A characterization of (p,q)-mixing when p/q < 4

Speaker: | Ben Moore |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract**: Let Hom(G,H) be the graph whose vertex set is the set of H-colourings of G, and two H-colourings f and g are adjacent if f differs from g in at most one vertex.

Thursday, September 20, 2018 — 3:30 PM EDT

**Title**: Naji’s characterization of circle graphs

Speaker: | Jim Geelen |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract**: A circle graph is the intersection graph of chords of a circle.

Friday, September 14, 2018 — 3:30 PM EDT

**Title:** Rapid mixing of Glauber dynamics for colorings below Vigoda’s 11/6 threshold

Speaker: | Michelle Delcourt |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of *k*-colorings of a graph *G* on *n* vertices with maximum degree Δ is rapidly mixing for *k* **≥ **Δ+2.

Friday, September 14, 2018 — 11:30 AM EDT

Title: Science of Security-- Could Such a Thing Exist?

Speaker: | Paul van Oorschot |

Affiliation: | Carelton University |

Room: | MC 5501 |

Abstract: Recent years have seen increasing calls to make security research more "scientific". Who can argue with science being desirable?

Thursday, September 13, 2018 — 3:30 PM EDT

Title: Entropy and enumeration

Speaker: | Jorn van der Pol |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

Abstract: The information-theoretic concept of entropy is closely related to enumeration;

Friday, September 7, 2018 — 3:30 PM EDT

**Title:** The smallest eigenvalues of Hamming, Johnson and other graphs

Speaker: | Sebastian Cioaba |

Affiliation: | University of Delaware |

Room: | MC 5501 |

**Abstract:**

The smallest eigenvalue of graphs is closely related to other graph parameters such as the independence number, the chromatic number or the max-cut.

Thursday, August 16, 2018 — 11:30 AM EDT

**Title**: Counting Partitions Inside a Rectangle

Speaker: | Steve Melczer |

Affiliation: | University of Pennsylvania |

Room: | MC 6486 |

**Abstract:**

The study of integer partitions is a classic subject with applications ranging from number theory to representation theory and combinatorics.

Friday, August 3, 2018 — 3:30 PM EDT

**Title:** The geometry of matroids

Speaker: | Federico Ardila |

Affiliation: | San Francisco State University |

Room: | MC 5501 |

**Abstract:**

Matroid theory is a combinatorial theory of independence which has its origins in linear algebra and graph theory, and turns out to have deep connections with many other fields.

Friday, July 27, 2018 — 3:30 PM EDT

**Title: **Algorithms for Rank-1 Bimatrix Games

Speaker: | Bernhard von Stengel |

Affiliation: | London School of Economics |

Room: | MC 5501 |

**Abstract:**

The rank of a bimatrix game is the matrix rank of the sum of the two payoff matrices.

Thursday, July 26, 2018 — 3:30 PM EDT

**Title**: Acyclic Colouring of Graphs on Surfaces

Speaker: | Shayla Redlin |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract**: An acyclic k-colouring of a graph G is a proper k-colouring of G with no

Friday, July 20, 2018 — 3:30 PM EDT

**Title: **Claw-free matroids

Speaker: | Peter Nelson |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:** A simple binary matroid is claw-free if it has no independent rank-3 flat. I will discuss a structure theorem, obtained jointly with Kazuhiro Nomoto, that classifies these objects exactly.

Thursday, July 19, 2018 — 3:30 PM EDT

**Title:** Density and Structure of Homomorphism-Critical Graphs

Speaker: | Evelyne Smith-Roberge |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract: **

Let H be a graph. A graph G is H-critical if every proper subgraph of G admits a homomor-

phism to H, but G itself does not.

Tuesday, July 17, 2018 — 3:00 PM EDT

**Title:** Using Linear Algebra to do Matching Theory

Speaker: | Justin Toth |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

A matching in a graph is a set of edges with each vertex contained in at most one edge. A perfect matching is a matching in which each vertex is contained in some edge.

Thursday, July 12, 2018 — 3:30 PM EDT

**Title**: Gaps in the crossing numbers of drawings of the complete graph

Speaker: | Bruce Richter |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract**: In the late 1990’s, a 5-author manuscript circulated proving the existence of intervals of integers that connot occur as the crossing number of a “good” drawing of the complete graph.

Thursday, July 12, 2018 — 1:30 PM EDT

**Title**: Periodicity on Oriented Graphs by way of Transcendental Number Theory

Speaker: | Sabrina Lato |

Affiliation: | University of Waterloo |

Room: | MC 6486 |

**Abstract**: Using the adjacency matrix of a graph, it is straightforward to show that perfect state transfer between two vertices at some time t implies that both vertices will be periodic at time 2t.

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 centralized within our Indigenous Initiatives Office.