Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
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 R3, 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