Questions tagged [matching-theory]
For questions about matchings in graphs.
533
questions
4
votes
1
answer
44
views
In a simple graph with $2m$ vertices and a unique perfect matching, prove that $|E(G)|$ is bounded by $m^2$.
I have been trying to solve this question, it was already asked but the response seems to have some issues.
The accepted answer implies that if a graph has a cycle of length 4, this implies that it ...
- 43
0
votes
0
answers
8
views
Is the following claim on saturated matching on bipartite graphs with constrained degree true?
Claim: A bipartite graph $G(X, Y)$ with all vertices in $X$ having degree less than or equal to 2 has an X saturating matching if and only if for any components $G'(X', Y')$ in $G$, $|X'| \geq |Y'|$.
...
- 1,549
2
votes
1
answer
30
views
Understanding the proof perfect matching polytope
Theorem. Let $M$ and $N$ be perfect matchings in a graph $G=(V, E)$. Then $\chi^M$ and $\chi^N$ are adjacent vertices of the perfect
matching polytope if and only if $M \triangle N$ is a circuit.
...
- 859
1
vote
1
answer
27
views
Understanding the proof of Konig edge-colouring theorem
Theorem: (König's edge-colouring theorem). For any bipartite graph $G=(V, E)$,
$$
\chi(G)=\Delta(G) .
$$
That is, the edge-colouring number of a bipartite graph is equal to its maximum degree.
Proof. ...
- 859
2
votes
0
answers
52
views
Prove that symmetric difference of two perfect matchings is union of disjoint even cycles
Problem: Let $M$ and $N$ be perfect matchings of a finite graph $G$. Prove that their symmetric difference is a union of disjoint even cycles.
My attempt:
Firstly, if $M = N$, we are done.
Now, let us ...
- 988
0
votes
0
answers
20
views
Algorithm for k sized matching in a complet weighted graph
as the Title suggest im looking for an algorithm for k sized matching in a weighted complet graph.
Any further literature is welcome.
- 1
0
votes
0
answers
45
views
Is there a way to do the Hungarian algorithm in reverse?
The Hungarian algorithm is used to find the optimal choices for a given 'cost matrix' e.g.
going from the output of the Hungarian algorithm
...
- 1
1
vote
0
answers
42
views
What is the connection between the deficiency in bipartite graphs and the connected components? (Matching Theory, Lovasz, 3.3.13)
I am working my way through "Matching Theory" by Lovasz and Plummer.
Lemma 3.3.13 is where I am stuck.
Let $G$ be a graph such that $C(G)=\emptyset$ and let $X$ and $Y$ be barriers such that ...
- 11
0
votes
0
answers
59
views
Find an alternating cycle in a graph with perfect matching.
Given a graph $G(V,E)$, we consider that there is a perfect matching $M$ in $G$. The edges in $M$ is red and the edges not in $M$ is blue. So is there a polynomial time algorithm that can find a red-...
0
votes
0
answers
23
views
Hall's Bipartite Matching With All Pairs of Vertices Having Distinct Degree
Problem: $G$ is a bipartite graph having partite sets $U$ and $W$ where $|U|$ = $|W|$ = $k \geq 2$. I need to prove that if every two vertices of $U$ have distinct degree in $G$, then $G$ contains a ...
3
votes
0
answers
102
views
Largest number of disjoint subsets of certain cardinality in bipartite graph such that every vertex is matched
Given a bipartite graph $G=(V,E)$, where $V$ is partitioned into $A$ and $B$, how can I design an algorithm that runs in polynomial time, such that given a positive integer $n\in\mathbb{N}$, the ...
- 73
0
votes
0
answers
39
views
I can't find a proof of this graph theorem about matchings, would anyone be able to prove it?
Here is the theorem:
Suppose $M_1, M_2, . . . , M_k$ is a sequence of matchings in a graph $G$ such that $M_i$ is
obtained from $M_{i−1}$ by augmenting along some alternating path. If there is no ...
2
votes
2
answers
71
views
Perfect matching in a bipartite graph avoid increasing perfect matchings?
Let $A=\{a_1,\dots,a_n\}$ and $B=\{b_1,\dots, b_n\}$ be two disjoint vertex sets.
Let $A_i=\{a_1,\dots, a_i\}$ be the set of first $i$ vertices of $A$. And $B_i=\{b_1,\dots, b_i\}$, similarly.
For $1\...
- 1,911
0
votes
0
answers
19
views
Relationship between number of perfect matchings in a balanced bipartite graph and determinant of its biadjacency matrix.
Let $G$ be a balanced bipartite graph with the adjacency matrix $A$. It is known that $A$ can be written in the form $A=\left[\begin{array}{ll}
0&B\\
B^T&0
\end{array}\right]$, where $B$ is ...
- 35
1
vote
2
answers
55
views
Finding the set that violates Hall’s condition in a bipartite graph.
If I have a bipartite graph for which it is given that there does not exist any complete matching. This implies that Hall’s condition is not satisfied for this graph. So, there must be atleast one set ...
- 741
0
votes
0
answers
20
views
Does squaring the elements of the cost matrix change the result of the Hungarian Algorithm?
I have a question on the assignment problem, which can be solved with the Hungarian Algorithm.
If we square every element of the cost matrix, would it change the optimal assignment of the Hungarian ...
- 31
0
votes
0
answers
48
views
Graph Alignment algorithms that consider both node and edge weights
I have two complete weighted graphs, with the same number of nodes and edges. Each node has a multi-dimensional vector, which represents its features. Edge weights are float numbers between 0 to 1. I'...
- 103
1
vote
0
answers
42
views
Hungarian Algorithm Adjustment Step
I am not sure whether I can simply not find an answer or I am just missing something obvious, but there is a step in the Hungarian algorithm which I am having trouble understanding; I will be ...
- 11
0
votes
1
answer
94
views
Proving a graph with more than one perfect matching must contain an even cycle.
Statement: If a graph has more than one perfect matchings, then it has an even cycle.
I was trying to prove this result. My try:
Let $M$ and $M'$ be two perfect matchings in graph $G$. Symmetric ...
- 35
0
votes
0
answers
9
views
fractional matching number of projective plane of uniformity $k$?
I am wondering for a projective plane $P$ of uniformity $k$, what is $\nu^*(H)$, the fractional matching number of $H$?
- 1,911
2
votes
2
answers
76
views
No perfect matching in $K_n$ after removing $n-1$ edges?
Assume $n\ge 6$ is even.
Let $S$ be a set of $n-1$ edges in $K_n$.
Suppose there is no perfect matching in $E(K_n)\setminus S$. Then is it true that $S$ must be a star?
I am trying to prove by using ...
- 1,911
0
votes
1
answer
66
views
Variant of minimum weight perfect matching problem with Hungarian algorithm
Given a complete bipartite graph $G=\{A+B,W\}$ with the number of vertices $|A|<|B|$, suppose I am looking for a subset $B'\subset B$ with $|B'|=|A|$ such that the minimum weight perfect matching ...
0
votes
0
answers
44
views
What is the order of a sum of arbitrary positive integers?
I am preparing a presentation about a version of Edmond's Blossom Algorithm as it has been
described by William Pulleyblank. The algorithm finds a maximum weight
b-matching for a graph $G = (V, E)$ ...
- 1
1
vote
1
answer
71
views
Combinatorics: Matching students and teachers from different schools
Let $s_1$, $s_2$$\dots$, $s_n$ be $n$ different schools. Given are $x_i$ teachers and $y_i$ students from school $s_i$, so that $\sum\limits_{i=1}^nx_i=\sum\limits_{i=1}^ny_i$. Do a one to one match ...
- 841
1
vote
1
answer
32
views
Proof Verification - Lemma on Matchings and M-augmenting paths
Lemma: Let $M$ be a matching and $P$ an $M$-augmenting path. Then, $M'= M \Delta P$ is a matching (with cardinality +1).
I have a proof in my notes but I thought to try proving it myself. My attempt ...
- 67
0
votes
0
answers
36
views
Distribution of $k$-matchings in a random graph
Take the Erdos-Renyi random graph $G(n,p)$, i.e. the random graph with $n$ vertices and where each possible edge has an independent probability of $p$ of being present. Recall that a $k$-matching is a ...
0
votes
0
answers
45
views
Bipartite Matching Proof
Let $G=(V,E)$ be a bipartite graph $|L| = |R| = n$
Given the graph G has no perfect matching how can i prove that G has $L_1$ $\subset $ L and $R_1 \subset R
$ such that $|L_1| + |R_1| = n+1$
and $...
- 15
0
votes
0
answers
15
views
Fractional width and fractional matching number
Given a hypergraph $H=(V,E)$, the fractional width $w^*(H)$ is
$\min \sum_{a\in E}f(a)$ over all non-negative function $f\colon E\rightarrow\mathbb{R}$ such that for any $b\in E$, $\sum_{a\in E}f(a)|a\...
- 1,911
1
vote
0
answers
21
views
Is perfect matching anything special in the matching polytope?
Assume a $d$-regular graph $G$ has a perfect matching. I am wondering is the character function of the perfect matchings anything special in the matching polytope $P$ that is the convex hull of
$$\{\...
- 1,911
0
votes
1
answer
39
views
Is the stable marriage problem defined for $0$ people?
When proving properties of algorithms which are supposed to solve the stable marriage problem, I find myself unable to prove them sometimes in the case of there being $0$ things to pair with each ...
- 2,145
0
votes
0
answers
30
views
existence of mappings between two two-dimensional probability distributions
Let $ U_1$, $ U_2$, $V_1,V_2$ be finite sets. Let $F\in \Delta(U_1\times U_2)$ and $G\in \Delta(V_1\times V_2)$ be some given probabilities distributions on $U_1\times U_2$ and $V_1\times V_2$.
Given $...
- 121
0
votes
1
answer
49
views
Minimise the sum of ratios
I have a list $a$ whose elements are positive real values. Assume $a_i > a_2 > ... a_{n-1} > a_n$, and assume $n$ is even. You must form unique pairs from $a$ and for each pair's value is ...
- 11
1
vote
0
answers
44
views
Maximum matching ($\alpha'$) lower bound.
This exercise can be found in "Graph Theory" by Bondy and Murty. I need some help in order to complete the proof. If you have other idea, share us pls.
Only must you use the Berge's Theorem.
...
0
votes
0
answers
68
views
Reduction for NP complete proof
Consider the problem “wellMath”, which is defined as follows:
{
Input: An undirected graph G = (V, E) and a positive integer p.
G contains a well-separated matching of size p.
}
"We define a well-...
0
votes
0
answers
51
views
Prove that every bipartite graph G has a matching of size ≥ |E(G)|/∆, where ∆ is the maximum degree of G.
Prove that every bipartite graph G has a matching of size ≥ |E(G)|/∆, where ∆ is the
maximum degree of G. Using Halls Theorem. I need a good proof, I am studying for an exam and I need to understand ...
0
votes
0
answers
34
views
How to prove the existence of groups for bipartite graph?
I have a simple bipartite graph with bipartition (W, C) such that $|W| < |C|$, each vertex $c \in C$ has 2 edges (so to two different vertices w each time) and each vertex $w \in W$ has 4 edges. I ...
- 1
3
votes
1
answer
151
views
Are the theorems of P. Hall and M. Hall equivalent?
Let $A$ be a set together with and indexed collection $\{A_{i}:i\in I\}$ of (not necessarily distinct) subsets of $A$.
A system of distinct representatives of $\{A_{i}:i\in I\}$ is a collection of ...
- 4,078
2
votes
1
answer
35
views
Listing vs. counting perfect matchings in a graph
In his Polyhedral Computation textbook, Fukuda writes:
It is known that the counting problem [of perfect matchings] is #P-complete even for bipartite graphs. There are polynomial algorithms for the ...
- 261
0
votes
0
answers
37
views
From undirected graph to directed graph and consider minimum value of the maximum in-degree
Given a undirected graph with $n$ vertices and $m$ edges. Now we assign a direction for each edge and get a directed graph. Prove that, for all possible assignments, the minimum value of the maximum ...
- 1
3
votes
0
answers
74
views
Explicit bijection between finite field Grassmannians satisfying a flag condition
This question is inspired by explicit bijection between ${[2n+1]\choose n+1}$ and ${[2n+1]\choose n}$ mapping $A$ to a subset of $A$, or equivalently, Is there an explicit construction of this ...
- 10.4k
0
votes
2
answers
399
views
Prove bipartite graphs have a perfect matching of $X$ into $Y$ if $\deg(x)\ge \deg(y)$ for all $x\in X$ and $y\in Y$
I have an exercise from here involving Hall's Theorem:
Let G be a bipartite graph on the parts $X$ and $Y$, and
suppose that the inequality $\deg(x)\ge \deg(y)\ge 1$ holds for all $x\in X$ and $y\in ...
1
vote
1
answer
50
views
Hall's marriage, a question
The question is below:
At a bakery the baker made 20 kind of cookies, from each kind he made exactly 20 cookies. Once baked, he randomly put them at 20 table pans, at each table pan he put exactly 20 ...
- 963
7
votes
0
answers
274
views
Generalizing Hall's marriage theorem
(This question has been posted on mathoverflow: Generalizing Hall's marriage theorem)
Fix positive integers $m,n,k$ such that $n\geq k$.
Consider a bipartite graph between two sets of vertices $A$ and ...
- 1,213
0
votes
0
answers
26
views
Spatial matching
For two finite sets of 2D coordinates $C_1, C_2 \subset [0, 1]^2$ with $|C_1|,|C_2|<\infty$ and $C_1 \subseteq C_2$. you can only observe parts of these sets $A_1 \subseteq C_1$ and $A_2 \subseteq ...
- 108
1
vote
1
answer
84
views
Lower bounds on the matching number of maximal planar graphs.
I have read the following article in which the authors briefly prove that the lower bound on the matching number of a maximal planar graph is $\frac{n+8}{3}$.
Biedl, T., & Wittnebel, J. (2023). ...
- 2,014
2
votes
0
answers
48
views
Variant of Assignment Problem with multiple group constraints
I have a bipartite graph $G = (G_1 \cup G_2, E)$ where we suppose $|G_1| \le |G_2|$.
Each vertex $V \in G_1$ represents a worker. A worker $V$ has two associated values:
a workgroup index $g(V) \in \...
- 21
0
votes
0
answers
50
views
Solve problem with finding a matching. [duplicate]
Let $k<\frac{n}2$, prove there is a one to one function:
$f: {[n] \choose k} \rightarrow {[n] \choose k+1}$, such that $A$ is a subgroup of $f(A)$ for every subgroup $A$ of $k$.
I tried to make a ...
- 1
1
vote
1
answer
195
views
Criteria for infeasibility of bipartite graph full matching/linear sum assignment
I am trying to (programmatically) find a minimum weight matching in a large bipartite graph (over a thousand nodes on both sides with over a million edges), and I run into an issue where the "...
- 55
11
votes
2
answers
229
views
Injection from binary strings with $i$ bits to $i+1$ bits
I want to find an injection $F$ from binary strings length $n$ with $i$ bits turned on to $i+1$ bits turned on, with the condition that if $F(S)=S'$, then $S'$ can be obtained from $S$ by simply ...
- 698
1
vote
1
answer
108
views
How much can the matching number in a graph decrease at most by removing a vertex subset?
Let $G$ be a graph and let $v$ be a vertex of $G$. Let $\alpha'(G)$ denote the size of maximaum matchings in $G$.
My question is the following:
Question 1. What is the maximum value of $\alpha'(G) - \...
- 2,014