Please email any errors or updates to our website support/editor.

PDF files require Adobe Acrobat Reader.

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.

Wednesday, September 26, 2018 — 4:00 PM EDT

**Title**: Classification, Regularization and Logistic Regression

Speaker: | Haesol Im |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract**: For the first two seminar series in machine learning,

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

**Title:** Quantum advantage with shallow circuits

Speaker: | David Gosset |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

A constant-depth quantum circuit is a parallel quantum computation that proceeds for a constant number of time steps. In this work we prove that constant-depth quantum circuits are more powerful than their classical counterparts.

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.

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

**Title:** The coloring problem for restricted graph classes

Speaker: | Chinh T. Hoang |

Affiliation: | Wilfred Laurier University |

Room: | MC 5501 |

**Abstract:**

Let L be a set of graphs. Free(L) is the set of graphs that do not contain any graph in L as an induced subgraph.

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

**Title**:Generalizing the problem of packing disjoint cycles

Speaker: | Paul Wollan |

Affiliation: | University of Rome "La Sapienza" |

Room: | MC 5479 |

**Abstract**: A classic result of Erdos and Posa states that there exists a function f such that for all k,

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

**Title**: Edge State Transfer

Speaker: | Tina Chen |

Affiliation: | University of Waterloo |

Room: | MC 6486 |

**Abstract**: Most research about quantum state transfer on graphs use adjacency matrices as their Hamiltonians and investigate the transfers between single vertex states.

Friday, June 29, 2018 — 3:30 PM EDT

**Title:** The c_{2} invariant at p=2 by counting edge bipartitions

Speaker: | Karen Yeats |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

Since no one provided a visitor or volunteered for this week, I will explain how to prove a special case of a conjecture about the c_{2} invariant.

Thursday, June 28, 2018 — 3:30 PM EDT

**Title**: Stretching drawings of graphs

Speaker: | Alan Arroyo |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract**: Given a drawing D of a graph (where vertices are dots in the plane and edges are arbitrary curves connecting some pairs of dots),

Thursday, June 28, 2018 — 11:30 AM EDT

**Title**: The Many Faces of Circulation Algebras

Speaker: | Nick Olson-Harris |

Affiliation: | University of Waterloo |

Room: | MC 6486 |

**Abstract**: The circulation algebra is a commutative graded algebra associated to a graph, introduced by Wagner in 1998 to study flows.

Friday, June 22, 2018 — 3:30 PM EDT

**Title:** Two-level polytopes

Speaker: | Kanstantsin Pashkovich |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

This talk is dedicated to two-level polytopes. On one side, two-level polytopes form a well structured family of polytopes.

Please email any errors or updates to our website support/editor.

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