Questions tagged [matching-theory]
For questions about matchings in graphs.
567
questions
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$?
- 2,075
3
votes
2
answers
86
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 ...
- 2,075
0
votes
1
answer
102
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
45
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
75
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 ...
- 1,475
1
vote
1
answer
41
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
1
vote
0
answers
58
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
47
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
1
vote
0
answers
24
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
$$\{\...
- 2,075
0
votes
1
answer
40
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 ...
- 3,019
0
votes
1
answer
62
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
61
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.
...
3
votes
1
answer
164
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,432
2
votes
1
answer
39
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 ...
- 263
3
votes
0
answers
97
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 ...
- 12.3k