Lattice theory | Stable matching

Lattice of stable matchings

In mathematics, economics, and computer science, the lattice of stable matchings is a distributive lattice whose elements are stable matchings. For a given instance of the stable matching problem, this lattice provides an algebraic description of the family of all solutions to the problem. It was originally described in the 1970s by John Horton Conway and Donald Knuth. By Birkhoff's representation theorem, this lattice can be represented as the lower sets of an underlying partially ordered set, and the elements of this set can be given a concrete structure as rotations, cycle graphs describing the changes between adjacent stable matchings in the lattice. The family of all rotations and their partial order can be constructed in polynomial time, leading to polynomial time for other problems on stable matching including the minimum or maximum weight stable matching. The Gale–Shapley algorithm can be used to construct two special lattice elements, its top and bottom element. Every finite distributive lattice can be represented as a lattice of stable matchings.The number of elements in the lattice can vary from an average case of to a worst-case of exponential.Computing the number of elements is #P-complete. (Wikipedia).

Video thumbnail

Agnes Cseh: Popular matchings

We are given a bipartite graph where each vertex has a strict preference list ranking its neighbors. A matching M is stable if there is no unmatched pair ab, so that a and b both prefer each other to their partners in M. A matching M is popular if there is no matching M' such that the num

From playlist HIM Lectures 2015

Video thumbnail

Lattice Structures in Ionic Solids

We've learned a lot about covalent compounds, but we haven't talked quite as much about ionic compounds in their solid state. These will adopt a highly ordered and repeating lattice structure, but the geometry of the lattice depends entirely on the types of ions and their ratio in the chem

From playlist General Chemistry

Video thumbnail

Pattern Matching - Being Flexible

As your patterns become more complex you'll need to build patterns that can match expressions with different but similar forms. Activity Link: https://teacher.desmos.com/activitybuilder/custom/60626999811e664d596ece18

From playlist Pattern Matching with Computation Layer

Video thumbnail

Set Theory 1.4 : Well Orders, Order Isomorphisms, and Ordinals

In this video, I introduce well ordered sets and order isomorphisms, as well as segments. I use these new ideas to prove that all well ordered sets are order isomorphic to some ordinal. Email : fematikaqna@gmail.com Discord: https://discord.gg/ePatnjV Subreddit : https://www.reddit.com/r/

From playlist Set Theory

Video thumbnail

Pattern Matching - Correctness

Learn how to use pattern matching to assist you in your determination of correctness. This video contains two examples, one with feedback and one without. https://teacher.desmos.com/activitybuilder/custom/6066725595e2513dc3958333

From playlist Pattern Matching with Computation Layer

Video thumbnail

Lattice relations + Hermite normal form|Abstract Algebra Math Foundations 224 | NJ Wildberger

We introduce lattices and integral linear spans of vexels. These are remarkably flexible, common and useful algebraic objects, and they are the direct integral analogs of vector spaces. To understand the structure of a given lattice, the algorithm to compute a Hermite normal form basis is

From playlist Math Foundations

Video thumbnail

Sets and other data structures | Data Structures in Mathematics Math Foundations 151

In mathematics we often want to organize objects. Sets are not the only way of doing this: there are other data types that are also useful and that can be considered together with set theory. In particular when we group objects together, there are two fundamental questions that naturally a

From playlist Math Foundations

Video thumbnail

Every Subset of a Linearly Independent Set is also Linearly Independent Proof

Please Subscribe here, thank you!!! https://goo.gl/JQ8Nys A proof that every subset of a linearly independent set is also linearly independent.

From playlist Proofs

Video thumbnail

F. Andreatta - The height of CM points on orthogonal Shimura varieties and Colmez conjecture (part5)

We will first introduce Shimura varieties of orthogonal type, their Heegner divisors and some special points, called CM (Complex Multiplication) points. Secondly we will review conjectures of Bruinier-Yang and Buinier-Kudla-Yang which provide explicit formulas for the arithmetic intersecti

From playlist Ecole d'été 2017 - Géométrie d'Arakelov et applications diophantiennes

Video thumbnail

Oliver Vipond (4/8/20): Local equivalence of metrics for multiparameter persistence modules

Title: Local equivalence of metrics for multiparameter persistence modules Abstract: An ideal invariant for multiparameter persistence should be discriminative, computable and stable. In this work we analyse the discriminative power of a stable, computable invariant of multiparameter pers

From playlist AATRN 2020

Video thumbnail

Matthew Hastings - Introduction to Quantum Cellular Automata - IPAM at UCLA

Recorded 01 September 2021. Matthew Hastings of Microsoft Research presents "Introduction to Quantum Cellular Automata" at IPAM's Graduate Summer School: Mathematics of Topological Phases of Matter. Learn more online at: http://www.ipam.ucla.edu/programs/summer-schools/graduate-summer-scho

From playlist Graduate Summer School 2021: Mathematics of Topological Phases of Matter

Video thumbnail

Proof: Regular Bipartite Graph has a Perfect Matching | Graph Theory

An r-regular bipartite graph, with r at least 1, will always have a perfect matching. We prove this result about bipartite matchings in today's graph theory video lesson using Hall's marriage theorem for bipartite matchings. Recall that a perfect matching is a matching that covers every ve

From playlist Graph Theory

Video thumbnail

Gallai-Edmonds Percolation by Kedar Damle

DISCUSSION MEETING : STATISTICAL PHYSICS OF COMPLEX SYSTEMS ORGANIZERS : Sumedha (NISER, India), Abhishek Dhar (ICTS-TIFR, India), Satya Majumdar (University of Paris-Saclay, France), R Rajesh (IMSc, India), Sanjib Sabhapandit (RRI, India) and Tridib Sadhu (TIFR, India) DATE : 19 December

From playlist Statistical Physics of Complex Systems - 2022

Video thumbnail

Geometry of the Global Nilpotent Cone Lecture 1 by Ana Peon-Nieto

PROGRAM : QUANTUM FIELDS, GEOMETRY AND REPRESENTATION THEORY 2021 (ONLINE) ORGANIZERS : Aswin Balasubramanian (Rutgers University, USA), Indranil Biswas (TIFR, india), Jacques Distler (The University of Texas at Austin, USA), Chris Elliott (University of Massachusetts, USA) and Pranav Pan

From playlist Quantum Fields, Geometry and Representation Theory 2021 (ONLINE)

Video thumbnail

Michael Rapoport: The arithmetic transfer conjecture for exotic formal moduli spaces

I will define some formal moduli spaces of p-divisible groups that can be used to formulate an extension of Wei Zhang's Arithmetic Fundamental Lemma conjecture beyond the unramified case. The lecture was held within the framework of the Junior Hausdorff Trimester Program Algebraic Geometr

From playlist HIM Lectures: Junior Trimester Program "Algebraic Geometry"

Video thumbnail

Alessandro Chiodo - Towards a global mirror symmetry (Part 1)

Mirror symmetry is a phenomenon which inspired fundamental progress in a wide range of disciplines in mathematics and physics in the last twenty years; we will review here a number of results going from the enumerative geometry of curves to homological algebra. These advances justify the i

From playlist École d’été 2011 - Modules de courbes et théorie de Gromov-Witten

Video thumbnail

Abelian networks and sandpile models (Lecture 4) by Lionel Levine

PROGRAM :UNIVERSALITY IN RANDOM STRUCTURES: INTERFACES, MATRICES, SANDPILES ORGANIZERS :Arvind Ayyer, Riddhipratim Basu and Manjunath Krishnapur DATE & TIME :14 January 2019 to 08 February 2019 VENUE :Madhava Lecture Hall, ICTS, Bangalore The primary focus of this program will be on the

From playlist Universality in random structures: Interfaces, Matrices, Sandpiles - 2019

Video thumbnail

Topology 1.3 : Basis for a Topology

In this video, I define what a basis for a topology is. Email : fematikaqna@gmail.com Code : https://github.com/Fematika/Animations Notes : None yet

From playlist Topology

Related pages

Finite set | Partially ordered set | Join and meet | Lattice (order) | John Horton Conway | Median graph | Covering relation | National Resident Matching Program | Computational complexity | Factorial | Exponential function | Distributive lattice | Gale–Shapley algorithm | Maximum flow problem | Closure problem | Cycle graph | Mathematics | Symmetric difference | ♯P-complete | Birkhoff's representation theorem | Directed acyclic graph | Abstract algebra | Directed graph | Antichain | Order polytope | Stable matching polytope | Linear programming