Events

Pfaffian Bipartite Graphs

Abstract:  

A graph is Pfaffian if it admits a Pfaffian orientation. Little (1975) showed that a bipartite graph is Pfaffian if and only if it does not "contain" $K_{3,3}$. This implies that the problem of deciding whether a bipartite graph is Pfaffian is in co-NP.

Understanding Structure in Conic Mixed Integer Programs: From Minimal Inequalities to Conic Disjunctive Cuts

Abstract: 

We study nonlinear mixed integer sets involving a general regular (closed, convex, full dimensional, and pointed) cone $K$ such as the nonnegative orthant, the Lorentz cone or the positive semidefin

Permutations and Book Embeddings of Graphs

Abstract:

Additive Number Theory, Graphs and Matroids

Abstract:

Cauchy in 1813 and Davenport in 1935 proved the following fundamental result in Additive Number Theory: given prime p and two subsets A and B of Z_p, the number of elements produced as a sum of an element from A and an element from B is at least the minimum

The Gindikin-Karpelevich Formula and Combinatorics of Crystals

Abstract: 

The Gindikin-Karpelevich formula computes the constant of proportionality for the intertwining integral between two induced spherical representation of a p-adic reductive group G.

The Potential Technique in Graph Coloring

Abstract: 

We discuss recent advancements and applications of the

A Proof of Lehman's Theorem

Abstract: 

Lehman proved that if the set covering polyhedron has a fractional extreme point, then it has one with a very special structure. I will give a proof of this result and describe an algorithmic version of it.

A Survey on Multi-flows in Graphs and Matroids

Abstract: 

In a multi-flow problem we are given a weighted graph where the edges are partitioned into demand and capacity edges. Every edge e is assigned a non-negative value.

A Glimpse of the Unique Games Conjecture

Abstract: 

The Unique Games Conjecture (UGC) asserts that one type of constraint satisfaction problem (related to a gap version of the max-cut problem) is NP-hard. This is an informal talk on the UGC. It will address some of the following: Where is it coming from? What is it?

Exponentially Dense Matroids

Abstract: 

The growth rate function for a minor-closed class of matroids is the function $h(n)$ whose value at an integer n is the maximum number of elements in a simple matroid in the class of rank at most $n$; this can be seen as a measure of the density of the matroids in the class.