Concept

Perfect matching

Related lectures (19)

Explores linear programming duality, covering constraints, variables, solutions, and the relationship between primal and dual LP.

Recent Advances in the Dimer Model and Its Applications

Covers recent advancements in the dimer model, emphasizing its applications in probability and conformal field theory.

Polynomial Identity Testing

Covers polynomial identity testing using oracles and random point evaluation, with applications in graph theory and algorithmic aspects.

Matroids: Matroid Intersection

Covers the concept of matroids, focusing on matroid intersection and the properties of subsets of a ground set.

Graph Matching Entropy

Explores the relationship between matchings, entropy, and Bethe free entropy in random graphs.

Comparing Hierarchical Clusterings

Covers the derivation and use of a measure of similarity between hierarchical clusterings, focusing on the Bk measure.

Ramanujan Graphs: Constructions and Similarities

Explores Ramanujan graphs' constructions, matching polynomials, perfect matchings, and universal covers, along with quantitation and qualitative aspects.

Matching Polynomials: Real-Rootedness and Signings

Explores matching polynomials, real-rootedness, signings, matchings sizes, and Hermann-Lieb condition.

Unweighted Bipartite Matching

Introduces unweighted bipartite matching and its solution using linear programming and the simplex method.

Greedy Change-Making Algorithm: Optimality and Stability

Explores the optimality of the greedy change-making algorithm and the stability of maximum matching.

Graph Algorithms: Ford-Fulkerson and Strongly Connected Components

Discusses the Ford-Fulkerson method and strongly connected components in graph algorithms.

Max-flow and Disjoint Sets

Explores the Ford-Fulkerson method, max-flow, applications of max-flow, and the disjoint-set data structure.

Max-flow Min-cut Theorem

Explores the Max-flow Min-cut theorem, integral capacities, Ford-Fulkerson method, bipartite matching, and edge-disjoint paths.

Algorithms: Stable Matchings

Covers the concept of stable matchings and the Gale-Shapley algorithm.

Algorithms: Union Find and Minimum Spanning Trees

Discusses Union-Find data structures and Minimum Spanning Trees, covering algorithms and their applications in network design and optimization.

Algorithms: Stable Matchings

Covers the concept of stable matchings and the Gale-Shapley algorithm.

Interlacing Families and Ramanujan Graphs

Explores interlacing families of polynomials and 1-sided Ramanujan graphs, focusing on their properties and construction methods.

Complexity of Algorithms

Explores linear search, insertion sort, coin change, maximum matching, and the halting problem in algorithms.

Boolean Hidden Matching Problem

Explores the Boolean Hidden Matching Problem, focusing on distinguishing messages with negligible probability.