Questions tagged [matching-theory]
For questions about matchings in graphs.
566
questions
1
vote
1
answer
37
views
Maximum number of edges such that $\nu(G) < \frac{n}{2}$
Given an even integer $n$. I want to find the largest number of edges in a $n$-vertex graph such that the matching number is strictly less than $\frac{n}{2}$. I believe that the maximum is obtained by ...
- 511
1
vote
0
answers
76
views
Polynomial Kernel For Minimum Maximal Matching Problem
Let $G$ be a graph, and $k$ be some non-negative integer. The goal is to decide whether there exists a maximal matching in $G$ on at most $k$ edges. This problem is also asked in https://www.mimuw.edu....
- 307
0
votes
0
answers
19
views
Existence of high-weight perfect matching
I have the following problem from Korte and Vygen:
Let $G$ be a $k$-regular and $(k-1)$-edge-connected graph with an even number of vertices, and let $c\colon E(G) \to
\mathbb R_+$ be a weight ...
- 65
0
votes
0
answers
21
views
One to one mapping that maximize the minimum absolute difference
Given two sequences $a_0 \leq a_1 \leq \ldots \leq a_{n-1}$ and $b_0 \leq b_1 \leq \ldots \leq b_{n-1}$. We want to find a one-to-one mapping $\pi:[n-1] \rightarrow [n-1]$ such that
$$
\max \min_{i} |...
0
votes
2
answers
43
views
Determining whether a housing allocation is in the Core
I have recently been thinking about the housing allocation problem where we have a set of players and a set of houses where players have strict preferences over the houses. I am aware of the Top ...
- 21
0
votes
0
answers
26
views
Finding Nash equilibrium in a basic matching market
I've been working on simulating a market with small numbers of mutually-exclusive sellers and buyers, where each individual can only ever enter one transaction. In pursuing this, I've been trying to ...
0
votes
0
answers
46
views
Generate a schedule for doubles with rotating partners
So I want to set up a schedule of double matches: player A and B vs player C and D. I have a few constraints for setting it up:
Each player plays exactly 4 times
The scheme should be as fair as ...
- 580
10
votes
1
answer
179
views
(Hall's Theorem) Existence of two subfamilies of sets containing the same elements
I came across the following claim in a textbook on combinatorics [1].
Claim (Lindström, Tverberg): Let $A_1, . . . , A_m \subseteq [n]$ be non-empty with $m > n$. There are non-empty, disjoint $I, ...
- 103
0
votes
1
answer
29
views
Special form of 3 vertex-connectedness for Graphs with every edge contained in a perfect matching
I am currently struggling with the following problem:
Given a simple, connected Graph $G = (V,E)$ such that every edge is contained in a perfect matching of $G$.
Show that for each edge $e \in E$ (of ...
- 663
1
vote
0
answers
40
views
Can Hall's Marriage Theorem be reduced to the $d$-regular case?
The version of Hall's Marriage Theorem I'd like to consider is the following:
Theorem Let $G$ be a finite bipartite graph with bipartition $\{X,Y\}$ and edge set $E$, so that we can view $E$ as a ...
- 15.7k
1
vote
1
answer
39
views
Specific way to prove that a cubic graph with a cut edge isn't $3$-edge-colorable.
The statement "If a simple graph $G$ is cubic and has a cut edge, then $\chi'(G) =4$" has a couple of proofs on this site, namely here and here. However, I was interested in a specific way ...
- 7,283
0
votes
0
answers
75
views
The Size Relationship Between a Given Matching and the Maximum Matching in a Graph Without Short Augmenting Paths
Let $G = (V, E)$ be a graph, and let $M \subseteq E$ be a matching such that there is no augmenting path of length at most 3 for $M$. Prove that $|M| \geq \frac{2}{3} |M^*|,$
where $M^*$ is the ...
- 59
5
votes
1
answer
79
views
2-factors with many cycles
Petersen's theorem states that every cubic, bridgeless graph contains a perfect matching. Let $G$ be a cubic bridgeless graph, and let $M$ be a perfect matching. Clearly $E(G)-M$ is a 2-factor of $G$ (...
3
votes
1
answer
62
views
Greedy lemma Problem for matching spears to soldiers
The problem has $n$ spears and $n$ soldiers. Spears and soldiers have heights. We want to assign spears to soldiers such that the total height difference of spears and their assigned soldiers is ...
- 307
2
votes
0
answers
89
views
Finding a perfect matching that include $e_{1}$ and exclude $e_{2}$ in a connected bipartite graph
Let $G$ be a $k$-regular bipartite graph with $k\ge3$, and $e_{1},e_{2}$
be edges of $G$. Show that if $G-\{e_{1},e_{2}\}$ is connected,
then there exist a perfect matching in $G$ that includes $e_{1}$...
- 734