Seminar

Title: Spanning trees and electrical networks... and what about matroids?

Abstract:

The relevance of spanning trees to the theory of electrifcal networks goes all the way back to Kirchhoff in 1847.

Title: Popularity, Mixed Matchings, and Self-duality

Abstract:

This week we continue our discussion of popular matchings.

Title: Popular Matchings

Abstract:

We introduce a variant of the stable matching problem on a bipartite graph G = (A [ P;E)

Title: Approximately counting independent sets in graphs with bounded bipartite pathwidth

Abstract:

In 1989, Jerrum and Sinclair showed that a natural Markov chain for counting
matchings in a given graph G is rapidly mixing.

Title: Hedetnemi's conjecture is false

Abstract:

On may 6th 2019, Yaroslav Shitov found a graph G x H such that the chromatic number of G x H is strictly smaller than the minimum of the chromatic number of G and the chromatic number of H. I will present the example.

Title: Toric varieties from distributive lattices

Abstract:

Given a nite lattice L, consider the ring of complex polynomials in indeterminates indexed by L, modulo the ideal generated by (XaXb-Xa^bXa_b for all a; b 2 L).

Title: A Fixed-Point Approach to Stable Matchings

Abstract:

This talk will be independent of the previous reading group talk. Three classical results in stable matching are the correctness of Gale Shapley’s deferred acceptance algorithm, the result of Conway that Stable Matchings form a distributive lattice, and Vande Vate and later Rothblum’s result that the convex hull of stable matchings has a polynomial-sized linear description.

Title: Free Groups

Abstract:

(The "free" in the title is an adjective, not a verb.) I will discuss free groups from a combinatorial perspective, focusing on the connections to fundamental groups and covers of graphs.

Title: Wronskians of polynomials

Abstract:

The Mukhin-Tarasov-Varchenko (MTV) theorem is the following statement in real algebraic geometry. If the wronskian of a set of complex polynomials has only real roots, then the vector space spanned by these polynomials is real.

Title: Quantum Log-Approximate-Rank Conjecture is also False

Abstract:

In a recent breakthrough result, Chattopadhyay, Mande and Sherif [ECCC TR18-17] showed an exponential separation between the log approximate rank and randomized communication complexity of a total function `f', hence refuting the log approximate rank conjecture of Lee and Shraibman [2009].