PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
October 5, 20250 citationsOpen Access

Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations

View Full Paper
DHDaniel HathcockCarnegie Mellon UniversityRRR. Ravi

Key Points

  • A bipartite graph has a perfect proportional allocation if it is matching covered, establishing a key condition for perfect matchings.
  • The proof leverages the classical result on matrix scaling, linking it to the properties of bipartite graphs.
  • Simple proportional allocations can also be derived for non-matching-covered bipartite graphs, expanding the framework's applicability.
  • These findings have implications for understanding the relationship between graph structures and matching theories.

Abstract

Given a bipartite graph that has a perfect matching, a prefect proportional allocation is an assignment of positive weights to the nodes of the right partition so that every left node is fractionally assigned to its neighbors in proportion to their weights, and these assignments define a fractional perfect matching. We prove that a bipartite graph has a perfect proportional allocation if and only if it is matching covered, by using a classical result on matrix scaling. We also present an extension of this result to provide simple proportional allocations in non-matching-covered bipartite graphs.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Hathcock et al. (2025) studied this question.

synapsesocial.com/papers/68e2537cd6d66a53c247444bhttps://doi.org/10.48550/arxiv.2510.01107
Ask AI
Helpful
Bookmark
Share
View Full Paper