English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Stable matching is a classical combinatorial problem that has been thesubject of intense theoretical and empirical study since its introduction in1962 in a seminal paper by Gale and Shapley. In this paper, we provide a newupper bound on $f(n)$, the maximum number of stable matchings that a stablematching instance with $n$ men and $n$ women can have. It has been along-standing open problem to understand the asymptotic behavior of $f(n)$ as$n\to\infty$, first posed by Donald Knuth in the 1970s. Until now the bestlower bound was approximately $2.28^n$, and the best upper bound was $2^{n\logn- O(n)}$. In this paper, we show that for all $n$, $f(n) \leq c^n$ for someuniversal constant $c$. This matches the lower bound up to the base of theexponent. Our proof is based on a reduction to counting the number of downsetsof a family of posets that we call "mixing". The latter might be of independentinterest.

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