Events

Connectivity Functions

Abstract: 

For a finite set $E$ a function $\mu:2^E\rightarrow \mathbb Z$ is a {\em connectivity function} if it is symmetric and submodular. Matroid connectivity and vertex connectivity in graphs are captured by associated connectivity functions.

Interior Point Methods I

Abstract:

Continuing from last week's talk, I will give an explicit primal-dual interior-point method and discuss the notion of a primal-dual scaling.  I will give two constructions of primal-dual scalings, one based on classical quasi-Newton updates and the other based on integrati

Interior Point Methods II

Abstract: 

Continuing from last week's talk, I will give an explicit primal-dual interior-point method and discuss the notion of a primal-dual scaling.  I will give two constructions of primal-dual scalings, one based on classical quasi-Newton updates and the other based on integra

Foundations of Primal-Dual Symmetric Interior-Point Methods for Convex Optimization

Abstract:

In the theory of modern interior-point algorithms,
approaches that treat primal and the dual problems in a symmetric way
have led to some of the deepest theoretical results as well as some of the

Extensions of Signed Graphs

Abstract: 

A signed graph is a pair (G, S), where S is a subset of E(G). We can extend a signed graph by adding edges, or by splitting vertices. We will address two questions about extensions of signed graphs.

Duality in the Combinatorics of Posets

Abstract: 

Every 10 years or so, there have been two closely connected theorems in the combinatoricst of posets, one for chains and one for antichains. Typically, the statements are exactly the same when roles are reversed, but the proofs are markedly different.

A Gentle Introduction to Knots and Knot Invariants

Abstract:

How many ways can you embed a circle in 3-space? This question motivates most of knot theory, and the first part of this presentation.

The Set Packing and Set Covering Polyhedra

Abstract:

The set packing and set covering polyhedra are two of the most fundamental objects in combinatorial optimization.

Exponential Improvement in Precision for Simulating Sparse Hamiltonians

Dense Triangle-free Binary Matroids

Abstract:

Brandt and Thomassé proved that a triangle-free graph $G$ with minimum degree greater than $\frac{1}{3}|V(G)|$ has chromatic number at most 4.