Scaling limits for random maximum weight perfect matching

Faculty Member

Partha Dey

Project Image

The well-known "Arctic Circle Theorem" states that uniformly random domino tilings (matchings) of an Aztec diamond of high order are frozen outside the “arctic circle” inscribed within the diamond, with asymptotically high probability. In this project, we plan to study maximal weight perfect matching on a sequence of growing planar bipartite graphs (on square or triangular lattice), like the Aztec diamond, with random edge-weights and find their asymptotic behavior. We will use Hungarian method to find the maximal matching and visualize them using standard coloring scheme (for square lattice) or surface representation (for triangular lattice). Strong coding ability (Matlab or Python) is required. [Image published at by user MiaFr under the Creative Commons Attribution-Share Alike 3.0 Unported License.]

Team Meetings

weekly at first, then biweekly

Project Difficulty


Undergrad Prerequisites

Completion of Calculus 3. Knowledge of Graph Theory and coding in Matlab or Python is required.