Seminar

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.

Title: Sequences of Trees and Higher-Order Renormalization Group Equations

Abstract:

In 1998, Connes and Kreimer introduced a combinatorial Hopf algebra HCK on the vector space of forests of rooted trees that precisely explains the phenomenon of renormalization in quantum eld theory.

Title: The Parallel Postulate: a 2000-year controversy

Abstract:

Euclid's book The Elements was groundbreaking in its logical formulation of synthetic geometry, and it is profoundly influential to this day, as it is widely considered to be the most published non-religious book in human history.