Seminar

Title: Ideal matrices

Abstract:

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

Title: From graph theory to set theory and back

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: Introduction to high-dimensional probability: some basic concentration inequalities and useful distributions

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

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: Entropy and the Upper Matching Conjecture

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

Title: Free subshifts and the Local Lemma

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: Toward a Theory of Crossing-Critical Graphs

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.

Title: Difference-of-SOS and Difference-of-Convex-SOS Decomposition Techniques for Polynomials

Abstract:

We are interested in polynomial decomposition techniques for reformulating any multivariate polynomial into difference-of-sums-of-squares (DSOS) and difference-of-convex-sums-of-squares (DCSOS) polynomials.

Title: MAD and Local Versions of Reed's Conjecture

Abstract:

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

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

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