Seminar

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.

Title: Maximum Cardinality Popular Matchings

Abstract:

We have seen the algorithm by Abraham, Irving, Kavitha, and Mehlhorn which deals with finding popular matchings (can be easily modified to give maximum cardinality popular matchings) in bipartite graphs with one-sided preference lists.

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.

Title: Finding perfect matchings in random regular graphs in linear expected time

Abstract:

In a seminal paper on finding large matchings in sparse random graphs, Karp and Sipser proposed two algorithms for this task. The second algorithm has been intensely studied, but due to technical difficulties, the first algorithm has received less attention. Empirical results suggest that the first algorithm is superior.

Title: Arborified zeta values and shuffles of rooted trees

_{*Please note room change}

Abstract:

Arborified zeta values are a generalisation to rooted trees of the usual multizeta values.

Title: Matching Games: From Bargaining to the Nucleolus

Abstract:

Cooperative matching games were first introduced in seminal work by Shapley and Shubik in their classic 1971 paper. In this talk, I will first review some of the key concepts and results in this area. I will then use these tools to (re-)derive several facts and algorithms for network generalizations of the famous Nash bargaining concept.