Questions tagged [matching-theory]
For questions about matchings in graphs.
566
questions
0
votes
0
answers
35
views
Let A be a 2n-element set. Find the number of pairings of A.
I am having trouble understanding how one of the solutions to this problem works:
Let a pairing of A partition the set into 2-element subsets. Example: a pairing of {a, b, c, d, e, f, g, h} is {{a, b},...
- 1
-1
votes
3
answers
84
views
An Optimization Problem With Permutation Function [closed]
When I tried to solve an one-to-one assignment problem, I constructed it as the following optimization problem, which is a min-max optimization problem with the optimization objective being functions.
...
- 11
0
votes
0
answers
34
views
How DTW decides which element to take next?
I'm currently working on an DTW algorithm implementation and do have a question about how DTW works if the next steps are the same or if the correct next step is the actually not less-cost one.
I do ...
0
votes
1
answer
49
views
A proof for the statement: The 3-Dimensional matching problem is NP-Complete
The 3-Dimensional Matching Problem is relatively well known in the fields of discrete mathematics and computer science. The problem consists of determining whether a tripartite
$3$-hypergraph with ...
- 3,468
0
votes
0
answers
8
views
Bipartite Matching With Distant Constraints
I am investigating the complexity of the following problem.
Let a complete bipartite graph $G = (V \cup V', E: V \times V')$ with |V| < |V'|, where the nodes have weights $w: V \cup V' \to \mathbb{...
- 9
2
votes
1
answer
43
views
If a graph is 1-factoreable, then it has no cut vertex.
I'm trying to prove the statement: if a graph $G$ is 1-factorable, then $G$ has no cut vertex.
Assuming $G$ has a cut vertex, let be $v\in V(G)$ a cut vertex of $G$. Then the connected components of $...
- 2,117
2
votes
0
answers
16
views
Matching number of a graph is equal to the independence number of its line graph.
Let $\alpha'(G)$ the matching number of a graph $G$, $L(G)$ its line graph and $\alpha(L(G))$ the stability number of its line graph. I need to prove that $\alpha'(G)=\alpha(L(G))$. Let $M$ be a ...
- 2,117
1
vote
0
answers
18
views
How sensitive are maximum-size matchings to edge deletion in random graphs?
My question concerns the sensitivity of maximum-size matchings (and more generally maximum-size $k$-cycle collections) to deletion of an edge in the graph.
Given a graph $G$, let a $k$-cycle be a ...
- 11
0
votes
1
answer
32
views
Understanding proof of Hall's graph theorem
I am struggling with understanding proof of Halls theorem.
Theorem: Let $G=(V_1\cup V_2,E)$ be a bipartite graph and for each $U\subseteq V_1$ let $$N_{G}(U)=\{v\in V_2\ :\ \exists u\in U\text{ such ...
- 115
1
vote
1
answer
39
views
Problem in proving that every tree has at most one perfect matching.
I would like to prove that every tree has at most one perfect matching. I approached it in the same way as described here: Perfect matching in a tree. However, I don't understand the concluding ...
user1316790
1
vote
1
answer
43
views
A matching problem with $N$ men, $N$ women and $N$ houses [closed]
Consider a matching problem with $N$ men, $N$ women and $N$ houses where each man has to be paired with exactly $1$ woman and then each couple has to be allotted to $1$ house. Now let's consider all $...
- 113
1
vote
0
answers
32
views
Parity of number of crossings of chord diagram
I would like to define the following sign for a given perfect matching $P$ of set of $2n$ elements:
$$\sigma_P=(-1)^k$$
where $k$ is the number of crossings in the chord diagram associated to $P$.
Is ...
0
votes
1
answer
39
views
Perfect matching on bipartite graph with $n(n-1)$ number of edges
Suppose $G$ is a $(X,Y)$ graph with $|X| = |Y| = n \geq 1$. Prove that if $|A(G)| > n(n-1)$ then $G$ has a perfect matching.
I'm looking for a hint on showing that $|N(S)| \geq |S|, \forall S \...
- 367
0
votes
0
answers
37
views
Equivalent statement to Hall's theorem [duplicate]
I am trying to prove that a bipartite graph $G$ on $(X, Y)$, contains a matching perfect to $X$ if and only if
$$
|X\setminus N(T)| \leq |Y\setminus T| \; \; \forall \; T \subseteq Y
$$
Forward ...
- 511
3
votes
1
answer
88
views
Why would solving #MATCHING(bipartite) problem efficiently solve #MATCHING efficiently?
Im gathering information about the matching counting problem for a graph $G$ (#MATCHING($G$)). I found that for the specific case of $G$ being a bipartite graph then the problem has a simple (not ...
- 541
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