All Questions
Tagged with perfect-matchings matching-theory
11 questions
21
votes
2
answers
4k
views
Graphs with only disjoint perfect matchings
Let $G(V,E)$ be a graph. I am searching for graphs with only disjoint perfect matchings (i.e. every edge only appears in at most one of the perfect matchings).
Examples:
Cyclic graph $C_n$ with even ...
- 155
2
votes
1
answer
401
views
Perfect matchings in infinite graphs
Let $G=(V,E)$ be an infinite graph such that $|V| = \kappa$ for some infinite cardinal $\kappa$, and every $v\in V$ has degree $\kappa$. Does $G$ have a perfect matching?
- 48.9k
7
votes
2
answers
480
views
Are all numbers from $1$ to $n!$ the number of perfect matchings of some bipartite graph?
Let $f(G)$ give the number of perfect matchings of a graph $G$.
Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$.
Consider collection of all $2n$ vertex balanced bipartite graph to be $\...
- 13.9k
3
votes
1
answer
3k
views
Number of perfect matchings in bipartite graph with given minimum degree
Let $G$ be a spanning subgraph of $K_{n,n}$ with minimum degree $\delta(G) \geq n/2$. It's easy to show using Hall's theorem that $G$ has a perfect matching, and the example of two disjoint copies of ...
- 4,589
2
votes
2
answers
354
views
Matching with probabilistic edges
Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the ...
- 239
1
vote
0
answers
299
views
On Schrijver's lower bound for the number of perfect matchings
Schrijver's lower bound gives the number of perfect matchings in a $k$-regular bipartite graph as $\Big(\frac{(k-1)^{k-1}}{k^{k-2}}\Big)^n$. What is the corresponding lower bound for minimum-degree $k$...
- 13.9k
-1
votes
2
answers
306
views
Cardinality of a set of mutually disjoint perfect matchings of $K_\omega$
If $G=(V,E)$ is a simple, undirected graph, we say that $M\subseteq E$ is a perfect matching if the members of $M$ are pairwise disjoint and $\bigcup M = V$. Let $K_\omega$ be the complete graph on $\...
- 48.9k
8
votes
1
answer
537
views
Fastest algorithm for counting perfect matchings in a general graph
Let $G(V,E)$ be a undirected graph. I am interested in the fastest known algorithm for counting the number of perfect matchings in $G(V,E)$ (which is known to be in $\#P$). In particular, what is the ...
- 155
8
votes
2
answers
761
views
Maximum number of perfect matchings in a planar graph?
What is the maximum number of perfect matchings a planar $k$-partite $|V|$ number of vertices simple graph can have where $k=2,3,4$ ($k>4$ is impossible for a planar graph)?
Since number of ...
- 13.9k
7
votes
1
answer
969
views
Graph to Bipartite conversion preserving number of perfect matchings
Given a graph $G$ on $n$ vertices is there a technique to convert to a balanced bipartite graph $B$ with $O(n^c)$ vertices at some fixed $0<c$ in $O(n^{c'})$ time at some fixed $0<c'$ such that ...
- 13.9k
3
votes
1
answer
304
views
Perfect matchings in infinite regular bipartite graphs
This question was motivated by a discussion here and is related to a previous question here.
Let $\kappa$ and $\lambda$ be cardinals such that $0<\lambda\leq \kappa$. Let $G=(A\cup B, E)$ be a ...
- 1,701