#### Contact Info

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

Thursday, October 31, 2019 4:00 PM EDT

**Title:** Edge-maximal graphs on surfaces

Speaker: | James Davies |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

It is straightforward to show that, with the exception of small complete graphs, every edge-maximal planar graph triangulates the plane.

Thursday, October 31, 2019 3:00 PM EDT

**Title:** Interpolated versions of the Central Limit Theorem, and crossings of pair-partitions

Speaker: | Alexandru Nica |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

Thursday, October 31, 2019 1:00 PM EDT

**Title:** Perfect state transfer on Cayley graphs

Speaker: | Soffia Arnadottir |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

Perfect state transfer on Cayley graphs

Wednesday, October 30, 2019 3:30 PM EDT

**Title:** Cutting a square into triangles of equal area

Speaker: | Hayley Reid |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

Suppose you are given a square and asked to cut it into n triangles of equal area. If n is even the problem is almost trivial, but when n is odd the problem becomes much harder.

Thursday, October 24, 2019 4:00 PM EDT

**Title:** Sublinear separators in intersection graphs of convex shapes

Speaker: | Rose McCarty |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

A balanced separator of an n-vertex graph is set of vertices whose deletion leaves only components of size at most 2n/3.

Thursday, October 24, 2019 3:00 PM EDT

**Title:** Boundary measurement and sign variation in real projective space

Speaker: | John Machacek |

Affiliation: | York University |

Room: | MC 5417 |

**Abstract****:**

Thursday, October 24, 2019 1:00 PM EDT

**Title:** Perfect state transfer on Hadamard diagonalizable graphs

Speaker: | Xiaohong Zhang |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

A (weighted) graph whose Laplacian matrix is diagonalizable by a Hadamard matrix is said to be Hadamard diagonalizable.

Thursday, October 17, 2019 1:00 PM EDT

**Title:** Discrete quantum walks, embeddings and designs

Speaker: | Harmony Zhan |

Affiliation: | York University |

Room: | MC 5479 |

**Abstract:**

We construct a quantum walk from an embedding of a graph.

Friday, October 11, 2019 3:30 PM EDT

**Title:** On the depth of cutting planesOn the depth of cutting planes

Speaker: | Laurent Poirrier |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

We tackle one of the most important open problems in computational integer programming: cut selection.

For four decades, cutting planes were believed to be useful only for structured combinatorial problems. This changed in 1995 when Balas, Ceria and Cornuéjols showed that Gomory cuts could helpfully strengthen the formulation of general integer programming problems. Since then, many other cut generation techniques have been developed, but their practical success has been moderate at best.

Friday, October 11, 2019 1:00 PM EDT

**Title:** Maximizing a Monotone Submodular Function subject to a Matroid Constraint

Speaker: | Justin Toth |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

Based on the paper by Calinescu, Chekuri, Pál, and Vondrák of the same title. We will study a randomized $(1-\frac{1}{e})$-approximation algorithm for the titular problem.

Thursday, October 10, 2019 4:00 PM EDT

**Title:** A Pseudoforest Analogue of the Strong Nine Dragon Tree Conjecture

Speaker: | Logan Grout |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

In 2016, Jiang and Yang proved the Nine Dragon Tree Conjecture, a strengthening of the classical arboricity result of Nash-Williams (1964). On the way to developing this proof, Fan, Lim Song, and Yang proved an analogous result for decomposing graphs into pseudoforests, which is a strengthening of Hakimi’s Theorem.

Thursday, October 10, 2019 3:00 PM EDT

**Title:** Scattering amplitudes and associahedra

Speaker: | Hugh Thomas |

Affiliation: | UQAM |

Room: | MC 5417 |

**Abstract:**

The classic approach to scattering amplitudes sums a contribution from a (potentially very large) number of Feynman diagrams.

Thursday, October 10, 2019 1:00 PM EDT

**Title:** Quantum Colouring and Derangements

Speaker: | Chris Godsil |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

Work in quantum information has lead to the introduction of quantum colourings.

Friday, October 4, 2019 3:30 PM EDT

**Title:** Extending drawings of K(n) to pseudolines and pseudocircles

Speaker: | Bruce Richter |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

In the early part of the 21st century, it was shown that the number of crossings in a straight-line drawing of K(n) is at least the number H(n), which is conjectured to be the crossing number of K(n). In fact, it is now known that, for n at least 10, the inequality is strict.

Friday, October 4, 2019 1:00 PM EDT

**Title:** Greedy Heuristic for Maximizing Submodular Set Functions

Speaker: | Ishan Bansal |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

Several hard combinatorial optimization problems can be posed in the following framework: maximize a submodular function over its domain subject to a cardinality constraint.

Thursday, October 3, 2019 4:00 PM EDT

**Title:**

Speaker: | Lise Turner |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

There are several different notions of what it means for a graph to converge. One popular notion for sparse graphs is Benjamini-Schramm convergence which focuses on local properties of the graphs.

Thursday, October 3, 2019 3:00 PM EDT

**Title:** Discrete diffusion on graphs and real hyperplane arrangements

Speaker: | David Wagner |

Affiliation: | University of Waterloo |

Room: | MC 6483 |

**Abstract:**

In 2016, Duffy et al. introduced the following process on a graph. Initially, each vertex has some integer number of ``chips'' placed there (possibly negative).

Thursday, October 3, 2019 1:00 PM EDT

**Title:** Type II Matrices

Speaker: | Ada Chan |

Affiliation: | York University |

Room: | MC 5479 |

**Abstract:**

In 1867, Sylvester defined an {\sl inverse orthogonal matrix} as an $n\times n$ complex matrix $W$ satisfying

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.