Concept

Matching (graph theory)

Related lectures (32)

Unweighted Bipartite Matching

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

Matroids: Matroid Intersection

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

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.

Linear Programming: Weighted Bipartite Matching

Covers linear programming, weighted bipartite matching, and vertex cover problems in optimization.

Algorithms & Growth of Functions

Covers optimization algorithms, stable matching, and Big-O notation for algorithm efficiency.

Ramanujan Graphs: Constructions and Similarities

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

Linear Programming Duality

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

Matching Polynomials: Real-Rootedness and Signings

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

Interlacing Families and Ramanujan Graphs

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

Greedy Change-Making Algorithm: Optimality and Stability

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

Algorithms: Stable Matchings

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

Graph Matching Entropy

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

Linear Programming Duality

Covers linear programming duality and complementary slackness condition.

Polynomial Identity Testing

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

Pseudorandomness: Expander Mixing Lemma

Explores pseudorandomness and the Expander Mixing Lemma in the context of d-regular graphs.

Comparing Hierarchical Clusterings

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

Spin Model Exercises

Covers exercises on the spin model, independent set, matching, and increasing functions.

Mean field computation

Explores the computation of mean field and effective field in message passing algorithms.

Matching Polynomials: Real-Rooted Property

Explores matching polynomials, emphasizing their real-rooted property and related bounds.

Algorithms: Stable Matchings

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