Questions tagged [perfect-matchings]
A perfect matching is a matching of all the vertices of a graph. In other words, a perfect matching is a set of edges such that each vertex of the graph is incident to exactly one edge in the set.
142 questions
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
7
votes
5
answers
4k
views
Applications of Perfect Matching
I'm exploring some applications of perfect matching and I would like some input. I have found many applications in chemistry (storing information, estimating bond lengths, estimating resonance energy, ...
- 111
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
2
votes
0
answers
69
views
Why is Schröder numbers equivalent to the number of perfect matchings for triangular grid of n squares and how the graph look like? [duplicate]
In the OEIS entry for the Schröder numbers is A006318. There is a comment which related the sequence to perfect matchings:
The number of perfect matchings in a triangular grid of n squares (n = 1, 4, ...
- 141
1
vote
1
answer
313
views
Unique bipartite perfect matchings and cycles?
Given a graph $G$ which is bipartite and balanced and has unique perfect matching let $G^{e}$ be $G$ without edge $e$. Let $G\cup G_{\pi,\pi'}$ be union of $G$ and $G_{\pi,\pi'}$ where $G_{\pi,\pi'}$ ...
- 13.9k
3
votes
1
answer
197
views
Is it possible to improve the weight of perfect bipartite matchings faster than with Bellman-Ford?
If $G\left(A\cup B,\ E=\lbrace\lbrace a, b\rbrace\,|\, a\in A,\, b\in B\rbrace\right)$ is a weighted bipartite graph and $M_0$ an initial perfect matching, then the optimality of $M_0$ can be verified ...
- 13.2k
2
votes
1
answer
81
views
Are countable graphs with infinite minimal degree $1$-factorizable? [duplicate]
We say that a simple, undirected graph $G=(V,E)$ is $1$-factorizable if there is a partition of $E$ such that every member of the partition is a perfect matching of $G$. It is easy to see that any $1$-...
- 48.9k
22
votes
2
answers
8k
views
Cubic graphs without a perfect matching and a vertex incident to three bridges
The example shown below (courtesy of David Eppstein) is a common example of a cubic graph that admits no perfect matching:
(source: uci.edu)
Are there other examples of cubic graphs that do not ...
- 1,164
3
votes
1
answer
54
views
$1$-factorizability for "complete" finite hypergraphs
Let $H=(V,E)$ be a hypergraph such that $V\neq \varnothing$ and $\varnothing \notin E$. A matching is a subset $M\subseteq E$ such that $m_1\neq m_2 \in M$ implies $m_1\cap m_2 = \varnothing$, and $M$ ...
- 48.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
2
votes
0
answers
60
views
Sum of number of perfect matchings and a constant constuction
Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$.
Is ...
- 13.9k
1
vote
0
answers
94
views
Number of extremal $\{0,1\}$ matrices having permanent $1$ property
Is there a function which describes the number of $\{0,1\}^{n\times n}\cap\mathbb Z^{n\times n}$ matrices having permanent $1$?
I think it might be $\mathsf{poly}(n!)$ bounded.
Is there a function ...
- 13.9k
0
votes
1
answer
112
views
Weak $1$-factorizability
A simple, undirected graph is said to be $1$-factorizable if there is a partition of the edge set $E$ such that every member of the partition is a perfect matching of $G$. Let us call $G$ weakly $1$-...
- 48.9k
2
votes
1
answer
321
views
Extending perfect matchings into Hamiltonian cycles
Let $G$ be a simple cubic graph which has a Hamiltonian circuit $C$. In general, it is not possible to find a second Hamiltonian circuit which contains all the chords of $C$. For example, the Wagner ...
- 1,018
1
vote
0
answers
112
views
Is there a bipartite graph whose determinant corresponds to number of perfect matchings?
Let $M\in\{0,1\}^{n\times n}$ be a square integer matrix. If we consider $M$ as biadjacency of a balanced bipartite graph on $2n$ vertices having $n$ vertices of color $1$ and $n$ vertices of color $2$...
- 13.9k
12
votes
2
answers
750
views
Postnikov's approach to perfect matchings of graphs
Over a decade ago Alexander Postnikov developed his own way of looking at perfect matchings of bipartite plane graphs. As I recall, he starts with a 2-coloring of the square grid and creates a new ...
- 19.7k
10
votes
0
answers
750
views
Has this notion of vertex-coloring of graphs been studied?
In a study of a quantum physics problem, I came about an apparently very natural type of vertex colorings of a graph. The colors of the vertex $v_i$ is inherited from perfect matchings $PM$ of an edge-...
- 155
9
votes
1
answer
382
views
Why is the number of Perfect Matchings in a triangular grid equivalent to the number of Royal Paths?
The sequence A006318 at OEIS stands for the Schröder numbers.
They describes the number of lattice paths from the southwest corner $(0,0)$ of an $n\times n$ grid to the northeast corner $(n,n)$, ...
- 155
3
votes
1
answer
80
views
Determining a specific perfect matching $M$ by repeatedly asking for $|M \cap M_i|$ for other perfect matchings $M_i$
Let $G=(V,E)$ be a complete bipartite graph with $2n$ vertices and $M \subset E$ some unknown perfect matching of $G$.
The goal is to determine $M$ by repeatedly choosing some perfect matching $M_i \...
- 149
11
votes
1
answer
820
views
Graphs with only disjoint perfect matchings, with coloring
The following purely graph-theoretic question is motivated by quantum mechanics.
Definitions: A bi-colored graph $G$ is an undirected graph where every edge is colored. An edge can either be ...
- 155
2
votes
0
answers
106
views
Computing bipartite matching of size $k$?
Given a bipartite graph with $n$ vertices on each side and an integer $k$, how can we compute all bipartite matchings of size $k$?
The problem of computing all perfect matchings is #P-complete. But I ...
- 241
3
votes
0
answers
88
views
Infection on a complete graph
Suppose we have a complete graph on $2n$ vertices with one "infected" vertex.
At each time step, we form a matching of the vertices. Then the vertices paired with infected vertices will also ...
11
votes
2
answers
1k
views
Densest Graphs with Unique Perfect Matching
Given a graph $G$ with $n$ vertices, that has a perfect matching $M$, what is the maximal number of edges that $G$ can have without contradicting the uniqueness of $M$?
Are examples of such extremal ...
- 13.2k
0
votes
0
answers
48
views
Spanning subgraphs defined via $K_4$ matchings
I have by accident found an interesting kind of spanner of complete symmetric graphs $G(V,E)$ with weighted edges.
What I actually had planned was to implement an algorithm for calculating certain non-...
- 13.2k
6
votes
1
answer
299
views
Why is the number of Hamiltonian Cycles of n-octahedron equivalent to the number of Perfect Matching in specific family of Graphs?
In OEIS A003436, it is written that the number of inequivalent labeled Hamilton Cycles of an n-dimesnional Octahedron is the same as the number of Perfect Matchings in a the complement of the Cycle ...
- 155
-2
votes
1
answer
362
views
Infinite graphs with large degree but no perfect matching [duplicate]
Is there an example of an infinite connected, simple, undirected graph $G = (V,E)$ such that every vertex has $|V|$ neighbors, but $G$ does not have a perfect matching (that is, a set $M\subseteq E$ ...
- 48.9k
4
votes
2
answers
987
views
Applications of Hafnians
I am learning about Hafnians but I am struggling to find real-world applications of them. I understand the applications of determinants, permanents, and even pfaffians but I am at a loss for Hafnians. ...
- 111
1
vote
0
answers
63
views
$1$-factorizability for linear hypergraphs with infinite edges on $\omega$
Let $H=(V,E)$ be a hypergraph. We say that $M\subseteq E$ is a matching if the members of $M$ are pairwise disjoint, and $M$ is said to be perfect if $\bigcup M = E$. Moreover, $H$ is $1$-factorizable ...
- 48.9k
3
votes
1
answer
377
views
Minimum planar bipartite graph to cover all perfect matching count
Given set $\mathcal T_n=\{0,1,\dots,2^n-1\}$ what is the minimum number of vertices $2m$ needed in a planar bipartite balanced graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\...
- 13.9k
5
votes
1
answer
316
views
On optimal dual solutions for the minimum weight perfect matching problems in the case of metric weights
Following Lovasz-Plummer (Matching theory, North-Holland 1986, Theorem 9.2.1),
the minimum weight perfect matching problem on a complete graph
$G$ with even number of vertices and weight $w:E(G)\to
\...
- 4,878
2
votes
1
answer
338
views
Number of distinct perfect matchings/near perfect matchings in an induced subgraph
Consider a Class 1 graph with degree $\Delta\ge3$ and the induced subgraph formed by deleting a set of independent vertices of cardinality $\left\lfloor\frac{n}{\Delta}\right\rfloor$. Then, what is ...
- 2,089
1
vote
0
answers
53
views
Density of perfect matching count in $k$-partite graphs?
Let $f(G)$ give number of perfect matchings of a graph $G$.
Denote $\mathcal N_{n}=\{0,1,2,\dots,n!-1,n!\}$.
Denote collection of all $kn$ vertex balanced $k$-partite graph (each color is on $n$ ...
- 13.9k
9
votes
2
answers
454
views
How to characterize "matching-transitive" regular graphs?
I am interested in regular graphs $G$ such that for each pair of 1-factors (=perfect matchings) $F$ and $F'$ there is an automorphism of $G$ that takes $F$ to $F'$. Let's call this property matching ...
- 13.4k
5
votes
3
answers
877
views
On number of perfect matchings
Consider $2n$ vertex balanced bipartite graph.
If total number of edges is $n^2$ then we have $n!$ perfect matchings.
Fix $c\in(0,\frac12)$ and consider collection of $2n$ vertex balanced bipartite ...
- 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
4
votes
2
answers
2k
views
Edmond's blossom algorithm for Max weight perfect matchings
Edmond's blossom algorithm computes a maximum weight matching in a general graph (https://en.wikipedia.org/wiki/Blossom_algorithm).
Many papers also reference to Edmond's blossom algorithm to compute ...
- 167
0
votes
1
answer
358
views
A vertex transitive graph has a near perfect/ matching missing an independent set of vertices
Consider a power of cycle graph $C_n^k\,\,,\frac{n}{2}>k\ge2$, represented as a Cayley graph with generating set $\{1,2,\ldots, k,n-k,\ldots,n-1\}$ on the Group $\mathbb{Z}_n$. Supposing I remove ...
- 2,089
3
votes
1
answer
576
views
Minimum number of perfect matchings in a regular bipartite graph
Is there a lower bound on the number of perfect matchings in a $k$-regular bipartite graph?
One can use Hall's marriage theorem and induction on $k$ to derive the lower bound of $k$. I can't come up ...
- 217
6
votes
1
answer
526
views
Complexity for calculating number of Perfect Matchings in k-regular hypergraph
Let $G(V,E)$ be a unweighted, k-regular hypergraph, with vertices $V=(v_1, ... v_n)$ and edges $E=(e_1, ... e_m)$. The k-regularity leads to $|e_i|=k$ (i.e. every edge contains exactly $k$ vertices).
...
- 155
5
votes
0
answers
115
views
Hypergraphs with only disjoint perfect matchings
Let $H(n,r)$ be the set of $r$-uniform hypergraph with $n$ vertices that have only disjoint perfect matchings (i.e. every hyperedge only appears in at most one of the perfect matchings). Let $m(h(n,r))...
- 155
2
votes
0
answers
56
views
How to prove polynomial inequality encoded from 1-factors in $K_{2n}$
Let $G=(V,E)$ be a complete graph $K_{2n}$ and it has $m$ 1-factors $f_{i,(i=1,\dots,m)}$, where $m=\frac{(2n)!}{n!2^n}$.
Some definition:
$F=\{f_{1},f_{2},...,f_{2n-1}\}$ is one 1-factorization in $...
- 141
1
vote
0
answers
147
views
A simple case of a strong version of the Berge-Fulkerson conjecture
UPDATE 28 June 2019 A counterexample for Conjecture 2 has been provided. The conjecture is now demoted again to guess. The text has been updated to reflect this change, and there is now a new ...
- 1,018
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
0
votes
1
answer
150
views
Combining three matchings to form a maximal matching
Consider a regular tripartite graph $G$ with maximum degree $\Delta\ge3$ and parts $A,B,C$. Now, the induced subgraphs $A\cup B, B\cup C$ and $A\cup C$ are all bipartite.
Now, is there a way to ...
- 2,089
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
5
votes
6
answers
1k
views
Algorithm to find all (up to isomorphism) perfect matchings of quartic plane graphs
I need to find all (up to isomorphism) perfect matchings of some quartic plane graphs. I haven't found any specific algorithm to give me all the perfect matchings. Does anybody know about such an ...
- 563
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
-2
votes
2
answers
2k
views
Does every 3-regular bridgeless graph have a perfect matching? [closed]
Let $G$ be a simple $3$-regular (every vertex has degree $3$) $2$-edge connected graph. Does $G$ contain a perfect matching?
- 17
1
vote
1
answer
95
views
Maximum number of perfect matchings in a graph of genus $g$ balanced $k$-partite graph
What is the maximum number of perfect matchings a genus $g$ balanced $k$-partite graph (number of vertices for each color in all possible $k$-colorings is within a difference of $1$) can have? I am ...
- 13.9k
7
votes
2
answers
571
views
Perfect matchings in certain classes of hypergraphs
While doing research I came unto the following problem:
Given a hypergraph $H$ which is $r$-partite, $r$-uniform (each edge contains exactly $r$ vertices), $k$-regular (each vertex is contained in ...
