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

PDF files require Adobe Acrobat Reader.

Friday, March 29, 2019 — 3:30 PM EDT

**Title:** Toward a Theory of Crossing-Critical Graphs

Speaker: | Bojan Mohar |

Affiliation: | Simon Fraser University |

Room: | MC 5501 |

**Abstract:**

The crossing number of a graph is defined as the minimum number of crossings of edges in a drawing of the graph in the plane. In his seminal 1970 paper Toward a Theory of Crossing Numbers, Tutte made a fundamental contribution by proving what is known today as the Hanani-Tutte Theorem.

Friday, March 29, 2019 — 1:00 PM EDT

**Title:** Using Lasserre Hierarchy for Graph Coloring

Speaker: | Julian Romero Barbosa |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

In this talk, I will go over a technique introduced by Arora and Ge for coloring 3-colorable graphs having low *threshold rank* (i.e., graphs with few eigenvalues below certain negative constant).

Thursday, March 28, 2019 — 4:00 PM EDT

**Title:** High-dimensional probability: Bernstein's Inequality

Speaker: | Jimit Majmudar |

Affiliation: | University of waterloo |

Room: | MC 5417 |

**Abstract:**

We will extend our study of concentration inequalities so far to random matrices.

Thursday, March 28, 2019 — 1:30 PM EDT

**Title:** Not colouring the 3-sphere

Speaker: | Chris Godsil |

Affiliation: | Unioversity of Waterloo |

Room: | MC 6486 |

**Abstract:**

Let S(3) be the graph formed by the unit vectors in R^{3}, two vectors adjacent if they are orthogonal. I will prove that S(3) has no 3-colouring.

Wednesday, March 27, 2019 — 3:30 PM EDT

**Title:** Decomposing graphs into rooted odd trails

Speaker: | Rose McCarty |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

We give a precise characterization of when the edge set of a graph can be partitioned into k trails so that every trail begins and ends at a specified vertex v and has an odd number of edges.

Tuesday, March 26, 2019 — 2:00 PM EDT

**Title:** On the average size of independent sets in triangle-free graphs

Speaker: | John Schanck |

Affiliation: | University of Waterloo |

Room: | MC 6486 |

**Abstract:**

Some of the results that we've seen in this reading group have been improved recently using the "hard-core model" from statistical physics.

Friday, March 22, 2019 — 3:30 PM EDT

**Title:** Optimization in Data Analysis: Some Recent Developments

Speaker: | Stephen J. Wright |

Affiliation: |
Computer Sciences Department and Wisconsin Institute for Discovery University of Wisconsin-Madison |

Room: | MC 5501 |

**Abstract:**

Optimization is vital to the modern revolution in data science, and techniques from optimization have become essential in formulating and solving a wide variety of data analysis problems. In turn, data science has caused a ferment of new research activity in optimization by posing challenging new problems and new contexts.

Thursday, March 21, 2019 — 1:30 PM EDT

**Title:** Introduction to Quantum Cocliques

Speaker: | Mariia Sobchuk |

Affiliation: | University of Waterloo |

Room: | MC 6486 |

**Abstract:**

Quantum coclique is a generalisation of the notion of classical coclique.

Wednesday, March 20, 2019 — 4:30 PM EDT

**Title:** Is any knot not the unknot?

Speaker: | Patrick Naylor |

Affiliation: | University of Waterloo |

Room: | MC 4064 |

**Abstract:**

Ever wanted to learn something about knots? This is your chance! We'll talk about some basics of knot theory, including how to prove some intuitively `obvious' but mathematically tricky results.

Wednesday, March 20, 2019 — 4:30 PM EDT

**Title:** High-dimensional probability: Random vectors in high dimensions

Speaker: | Courtney Paquette |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

In this talk, I will finish our discussion of concentration inequalities, particularly, I will discuss the sub-exponential distribution and state Bernstein’s inequality; thereby completing our study of large deviations.

Wednesday, March 20, 2019 — 3:30 PM EDT

**Title:** The Iterated Local Model for Social Networks

Speaker: | Erin Meger |

Affiliation: | Ryerson University |

Room: | MC 5501 |

**Abstract:**

On-line social networks such as Facebook and Twitter are often studied through friendships between users. Adversarial relationships also play an important role in the structure of these social networks.

Tuesday, March 19, 2019 — 2:00 PM EDT

**Title:** Hypergraphs, Entropy, and Inequalities

Speaker: | Alessandra Graf |

Affiliation: | University of Waterloo |

Room: | MC 6486 |

**Abstract:**

In this talk, we discuss a generalization of Shearer's entropy lemma for weighted hypergraphs due to Friedgut (2004).

Friday, March 15, 2019 — 3:30 PM EDT

**Title:** Ideal matrices

Speaker: | Ahmad Abdi |

Affiliation: | Carnegie Mellon University |

Room: | MC 5501 |

**Abstract:**

A 0,1 matrix M is *ideal* if the set covering system Mx>=1, x>=0 gives an integral polyhedron.

Friday, March 15, 2019 — 1:00 PM EDT

**Title:** Approximate Coloring of 2-Colorable 4-Uniform Hypergraphs

Speaker: | Joshua Nevin |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

In this talk, we discuss several inapproximability results of Bhangale for 2-colorable 4-uniform hypergraphs.

Thursday, March 14, 2019 — 4:00 PM EDT

**Title:** High-dimensional probability: Random vectors in high dimensions

Speaker: | Courtney Paquette |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

In this talk, I will finish our discussion of concentration inequalities, particularly, I will discuss the sub-exponential distribution and state Bernstein’s inequality; thereby completing our study of large deviations.

Wednesday, March 13, 2019 — 3:30 PM EDT

**Title:** Ideal clutters and k-wise intersecting families

Speaker: | Ahmad Abdi |

Affiliation: | Carnegie Mellon University |

Room: | MC 5501 |

**Abstract:**

A clutter is *ideal* if the corresponding set covering polyhedron has no fractional vertices, and it is *k-wise intersecting* if the members don’t have a common element but every k members do.

Tuesday, March 12, 2019 — 2:00 PM EDT

**Title:** Counting maximal independent sets in the hypercube

Speaker: | Richard Lang |

Affiliation: | University of Waterloo |

Room: | MC 6486 |

**Abstract:**

In this talk we count the number of maximal independent set in the hypercube. It is not hard to see that the n-dimensional hypercube contains at least 2^{(n-2)} maximal independent sets.

Friday, March 8, 2019 — 3:30 PM EST

**Title:** From graph theory to set theory and back

Speaker: | Anton Bernshteyn |

Affiliation: | Carnegie Mellon University |

Room: | MC 5501 |

**Abstract:**

Many results in finite combinatorics can be extended to infinite structures via compactness---but this transfer is powered by the Axiom of Choice and leads, in general, to highly "pathological" objects.

Friday, March 8, 2019 — 1:00 PM EST

**Title**: On the Hardness of 4-coloring a 3-colorable graph

Speaker: | Akshay Ramachandran |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract**: A consequence of the PCP theorem is that it is NP-hard to approximate the chromatic number of a general graph to within \n^{1-\eps} for any constant epsilon.

Thursday, March 7, 2019 — 4:00 PM EST

**Title**: Introduction to high-dimensional probability: some basic concentration inequalities and useful distributions

Speaker: | Courtney Paquette |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract**: In this seminar, we introduce important tools from high-dimensional probability useful in studying applications in data science such as covariance estimation, matrix completion,

Wednesday, March 6, 2019 — 3:30 PM EST

**Title:** Free subshifts and the Local Lemma

Speaker: | Anton Bernshteyn |

Affiliation: | Carnegie Mellon University |

Room: | MC 5501 |

**Abstract:** The purpose of this talk is to demonstrate how combinatorial tools and techniques can be used to tackle problems in other areas of mathematics, specifically,

Tuesday, March 5, 2019 — 2:00 PM EST

**Title**: Entropy and the Upper Matching Conjecture

Speaker: | Connor Paddock |

Affiliation: | University of Waterloo |

Room: | MC 6486 |

**Abstract**: In this talk we examine the 2013 work of Ilinca and Kahn,

Friday, March 1, 2019 — 3:30 PM EST

**Title:** MAD and Local Versions of Reed's Conjecture

Speaker: | Luke Postle |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

Graph coloring is a widely studied area of graph theory dating from the time of the Four Color Conjecture (now theorem).

Friday, March 1, 2019 — 1:00 PM EST

**Title**: Fixed-parameter tractability with respect to tree-widt

Speaker: | Rose McCarty |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract**: Courcelle’s Theorem says that a very general class of decision problems on graphs is FPT with

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