Questions tagged [matching-theory]
For questions about matchings in graphs.
567
questions
21
votes
1
answer
1k
views
Cantor-Bernstein-Schröder Theorem: small proof using Graph Theory, is this correct?
The theorem:
Suppose there exist injective functions $A \to B$ and $B \to A$ between two infinite sets $A$ and $B$. Then there exists a bijection $A \to B$.
Proof:
Let $f: A \to B$ and $g: B \to A$...
- 1,177
20
votes
8
answers
48k
views
How to find the number of perfect matchings in complete graphs?
In wikipedia FKT algorithm is given for planar graphs. Not anything for complete graphs. I need to find the number of perfect matchings in complete graph of six vertices.
- 311
16
votes
5
answers
8k
views
A magic trick - find out the fifth card if four is given
Here is a magic trick I saw. My question is how the magician and his partner did it.
Given the simple French deck of cards, with $52$ cards. A person from the audience chooses randomly five cards ...
- 376
16
votes
4
answers
34k
views
Prove that a $k$-regular bipartite graph has a perfect matching
Prove that a $k$-regular bipartite graph has a perfect matching by using Hall's theorem.
Let $S$ be any subset of the left side of the graph. The only thing I know is the number of things leaving the ...
- 2,031
15
votes
1
answer
325
views
Mistake in OEIS A103904?
The sequence OEIS A103904 is described as
Number of perfect matchings of an $n \times (n+1)$ Aztec rectangle with the third vertex in the topmost row removed.
Definition of $M \times N $ Aztec ...
- 327
11
votes
4
answers
1k
views
Can you win the monochromatic urn game?
In the (monochromatic) urn depletion game, you are given $n$ vases, each containing some number of balls $a_1,\ldots, a_n \geq 0$. You win the game if you can remove all of the balls from the vases; ...
- 17.7k
11
votes
2
answers
251
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
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
9
votes
1
answer
6k
views
What does 2 to the power x mean in set theory
In a mathematics assignments i encounter the following statement:
We have a finite collection of combinatorial objects $S \subseteq 2^x$ (For example matchings or spanning trees)
What does this ...
- 369
9
votes
2
answers
4k
views
Derive Hall's theorem from Tutte's theorem
I'm trying to derive:
Hall Theorem A bipartite graph G with partition (A,B) has a matching of A $\Leftrightarrow \forall S\subseteq A, |N(S)|\geq |S|$
From this:
Tutte Theorem A graph G has a 1-...
- 101
9
votes
1
answer
1k
views
How many malicious bingo cards are there?
Consider a flexible form of bingo, where each square contains a condition and you mark off whether or not the condition applies to you. The number of bingos you obtain ostensibly measures the extent ...
- 1,535
8
votes
2
answers
7k
views
Prove that the sum of minimum edge cover and maximum matching is the vertex count
Given a connected graph, how can we prove that the number of edge of its minimum edge cover plus its maximum matching is equal to the number of vertices?
- 115
8
votes
1
answer
600
views
Bipartite graphs from permutations
Given are $n\geq 1$ permutations of $abcd$. We construct a bipartite graph $G_{a,b}$ as follows: The $n$ vertices on one side are labeled with the sets containing $a$ and the letters after it in each ...
- 7,194
8
votes
0
answers
317
views
Efficient algorithms to determine whether vertices form a deadlock
$\textbf{I. Problem Statements}$
Let $m, n \in \mathbb{N}^*$ and $G = (V, E)$ be a simple graph. First we define some notations:
(1)$[m] := \{1, 2, \dots, m\}$.
(2)$e_i$ is the elementary vector with $...
- 1,008
7
votes
1
answer
132
views
A hat allocation problem
This is an abstraction of a problem that has come up in my research.
Imagine we have $N$ wizards and $N$ hats. The hats have $C$ different colours. There are $n_1>0$ hats with the first colour, $...
- 1,295