All Questions
Tagged with matching-theory combinatorics
125
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
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
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} |...
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
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
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$ (...
2
votes
1
answer
51
views
If the bridges of a $3$-regular graph $G$ lie on a single path then $G$ has a $1$-Factor (perfect matching)
If the bridges of a $3$-regular graph $G$ lie on a single path then
$G$ has a $1$-Factor (perfect matching)
I've proved that a $3$-regular graph with at most two bridges has a perfect matching ($1$-...
- 800
0
votes
0
answers
64
views
Counting the number of "permitted" pairings between two sets
Suppose I have two sets $A$ and $B$. We will be considering pairs of elements $(a,b)$, where $a\in A$ and $b \in B$. I have a function $f(a,b) \rightarrow \{0,1\}$, i.e. for each pair I can say ...
- 121
2
votes
1
answer
42
views
Stable matching theorem for non-equal sides
Given a bipartite graph with two sides $A$ and $B$, for a vertex $v$, there is a linear order on $N(v)$ (a preference list). The stable matching theorem says that if $|A|=|B|$, then there exists a ...
- 2,075
5
votes
1
answer
92
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 ...
- 115
0
votes
0
answers
113
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
51
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 ...
2
votes
2
answers
73
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\...
- 2,075