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