March 2019

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

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).

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,

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,

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,

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.

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.

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.

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. 

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.

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.

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.

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).

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.

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.

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.

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.

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.

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.

Joint work with Jim Geelen and Paul Wollan.

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.

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.

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).

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.

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 (141)
    1. October (12)
    2. September (15)
    3. August (9)
    4. July (17)
    5. June (18)
    6. May (16)
    7. April (9)
    8. March (24)
    9. February (13)
    10. 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)