Future students

Title: A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists

Abstract:

We will continue the discussion of stable matching when there are unacceptable pairs and one-sided ties. Two weeks ago, we looked at a 3/2-approximation that was purely combinatorial. 

Title: Feynman graphs to chord diagrams

Abstract:

I will explain how classic techniques of algebraic combinatorics can, via chord diagrams, tell us about the leading log, next-to-leading log, etc, expansions in quantum field theory, and what we think chord diagrams can tell us about individual Feynman graphs as well. 

Title: Quasi-popular Matchings, Optimality, and Extended Formulations

Abstract:

The goal of this talk is to obtain efficient algorithms for computing desirable matchings (wrt cost) by paying the price of mildly relaxing popularity.

Title: Dyadic matroids with spanning cliques

^{*Please note time and date change}

Abstract:

The Matroid Minors Project of Geelen, Gerards, and Whittle describes the structure of minor-closed classes of matroids representable over a fixed finite field.

Title: Mutually unbiased bases

Abstract:

A pair of d x d unitary matrices is unbiased if M*N is at, i.e., all its entries have the same absolute value. A relatively simple argument shows that a set of pairwise unbiased unitary matrices has size at most d + 1.

Title: Fun with Pfaffians: Identities for Schur Q-Functions

Abstract:

Schur functions determinantal identities (e.g. Jacobi-Trudi, Giambelli) are cornerstones of symmetric function theory. Less well-known are the Pfaffian identities for Schur Q-functions.

Title: On the hardness of computing the diameter of a polytope

Abstract:

The diameter of a polytope P is given by the maximum length of a shortest path between a pair of vertices on P. Giving bounds on the diameter of a polytope is a fundamental research topic in theoretical computer science and discrete mathematics, motivated by the (still unknown) existence of a polynomial pivot rule for the Simplex Algorithm for solving Linear Programs.

Title: Quadratically Dense Matroids

Abstract:

We discuss recent work proving that for any integer $t\ge 2$, any maximum-sized simple $\mathbb C$-representable matroid $M$ of large rank with no $U_{2,t+3}$-minor satisfies $|M|=t{r(M)\choose 2}+r(M)$. It was not our intention to prove this result, so we will first explain our original motivation. We assume only basic knowledge of matroid theory.

Title: Approximation Algorithms for the Stable Marriage Problem

Abstract:

This week we will discuss stable matching when there are unacceptable pairs and preferences include ties. In this setting one can also consider the Hospitals/Residents problem and the variant where ties are one-sided.

Title: From Modeling Fermions to the Puzzle Rule

_{*room change}

Abstract:

A Knutson-Tao-Woodward puzzle is a tiling of a triangle with certain pieces that have labeled edges. The puzzle rule states that number of puzzles with a given boundary is equal to a Littlewood-Richardson coefficient.