ConceptMathematics
Bipartite graph
A graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to one in the other.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Bipartite expander2Bipartite expander graph1Bipartite graph average degree formula1Bipartite graph embedding for spectral bounds1Bipartite graph factoring1Bipartite graphs in matrix completion1Bipartite max perfect matching1Bipartite max perfect matching problem1Cycle1Equality condition for quadratic form bound1Genotype representation graph1Hall's theorem1
Lecturers
4Each in their own terms, from the easiest level.
Tom Leighton
A graph is bipartite if its vertices can be split into a left set and a right set such that all edges connect a node in the left set to a node in the right set.Gilbert Strang
A graph whose nodes can be divided into two disjoint sets such that every edge connects a node in one set to a node in the other.Soumyajit Saha
A graph whose vertices can be divided into two disjoint and independent sets such that every edge connects a vertex in one set to a vertex in the other.
Lectures that assume it
11- The Complexity Class coNP
- Spectral Graph Theory: Minimizing and Maximizing the Quadratic Form
- Expander Graphs Application 1: Good Codes
- Expander Graph Application 2: Derandomization
- Relaxing Integer Linear Programs to Linear Programs: Bipartite Maximum Perfect Matching
- Arch4Health: 4th Workshop on Architecture for Health
- Privacy Amplification for Correlated-Noise Mechanisms via b-Min-Sep Subsampling
- NP-Hardness of Approximation
- Expander Graphs Overview
- Max-Flow Min-Cut Theorem
- Duality in Linear Programming
Connections
23The lectures that define it or assume it, and the concepts next to it.
Concepts8
Show 2 moreShow fewer
Lectures15
- Graph Theory and Coloring
- Completing a Rank-One Matrix and Circulants
- Nodal Geometry and Perturbations of the Laplace-Beltrami Operator
- Essential Hardness: Completing the Exponential Time Hypothesis Proof
- The Complexity Class coNP
- Spectral Graph Theory: Minimizing and Maximizing the Quadratic Form
Show 9 moreShow fewer
- Expander Graphs Application 1: Good Codes
- Expander Graph Application 2: Derandomization
- Relaxing Integer Linear Programs to Linear Programs: Bipartite Maximum Perfect Matching
- Arch4Health: 4th Workshop on Architecture for Health
- Privacy Amplification for Correlated-Noise Mechanisms via b-Min-Sep Subsampling
- NP-Hardness of Approximation
- Expander Graphs Overview
- Max-Flow Min-Cut Theorem
- Duality in Linear Programming