Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Thursday, November 22, 2018, 12:15 pm

Duration: 45 minutes

Location: OAT S15/S16/S17

Speaker: Justin Dallant

A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings

This talk is based on a 2017 paper by Anna R. Karlin, Shayan Oveis Gharan and Robbie Weber.

Suppose you are given two sets of respectively n men and n women, where each man ranks all the women based on his preference and reciprocally each woman ranks all the men. A matching is a bijection between these two sets, and it is stable if there is no unmatched man/woman pair where both the man and the woman would rather be matched together than with their current match.
Before this paper, the best known bounds on f(n), the maximum number of stable matchings that a stable matching instance with n men and n women can have, were roughly 2.28ⁿ ≤ f(n) ≤ 2^{n·log(n)-O(n)}. I will present the new upper bound of cⁿ for some constant c along with its proof, which relies on the correspondence between stable matchings of an instance and downsets of a particular poset called the rotation poset of that instance.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login