Events - March 2019

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

Image of Professor Bojan Mohar

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

S M T W T F S
24
25
26
27
28
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
  1. 2019 (157)
    1. November (10)
    2. October (18)
    3. September (15)
    4. August (9)
    5. July (17)
    6. June (18)
    7. May (16)
    8. April (9)
    9. March (24)
    10. February (13)
    11. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)