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.
63 questions
3
votes
1answer
212 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\...
10
votes
0answers
435 views
+100
Vertex Coloring inherited from Perfect Matchings (motivated by Quantum Physics)
The following purely graph-theoretic question is motivated by quantum mechanics (and a special case of the questions asked here).
Bi-Colored Graph: A bi-colored weighted graph $G=(V(G),E(G))$, on $n$ ...
2
votes
1answer
44 views
Triangle Center from Weighted Perfect Matchings
let $\Delta$ be the triangle whose corners $A$, $B$, $C$ points in general position in Euclidean plane and, let $D$ be a fourth point inside $\Delta$.
Question:
what is known about the ...
0
votes
0answers
14 views
Name for Spanning Trees Containing all Edges of a Minimum Weight Perfect Matching
This question is motivated by the task of "uniformly" bicoloring the vertices of a symmetric TSP-instance graph with $2n$ vertices.
A simple heuristical requirement for such a bicoloring could be ...
5
votes
1answer
151 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)$, ...
2
votes
0answers
32 views
Can Orientability of Manifolds be Generalized to TSP Instances?
It is well known, that there are two basic kinds of manifolds, orientable and non-orientable ones; the most simple examples being obtained by identifying a pair of opposite sides of a rectangular ...
1
vote
0answers
21 views
Complexity of Calculating Minimum Weight Final Perfect Matchings
It is known, that Minimum Weight Perfect Matching can be calculated in $O(n^3)$;
Furthermore, it is possible, that the edge sets of the Minimum Weight Perfect Matching and of the Maximum Weight ...
4
votes
1answer
92 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 ...
8
votes
1answer
401 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 ...
-2
votes
1answer
340 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$ ...
9
votes
2answers
229 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 ...
4
votes
1answer
166 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).
...
-2
votes
1answer
69 views
Matching and minimal degree
Let $n\in\mathbb{N}$ be a positive integer and let $G =(V,E)$ be a connected simple undirected graph with $|V| = 2n$. Is it true that if for the minimal degree $\delta(G)$ we have $\delta(G) \geq n$, ...
-4
votes
1answer
120 views
Connected infinite graph $G$ with $\delta(G)\geq 2$ and no perfect matching [closed]
Is there a connected infinite graph $G=(V,E)$ such that $\text{deg}(v) \geq 2$ for all $v\in V$, and $G$ possesses no perfect matching?
2
votes
1answer
177 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?
-4
votes
1answer
111 views
Does the Hadwiger-Nelson graph have a perfect matching?
The Hadwiger-Nelson graph on $\mathbb{R}^n$ is defined to be $(\mathbb{R}^n,E_n)$ where $$E_n = \big\{\{x,y\}: x,y\in \mathbb{R}^n \text{ and } |x-y|=1\big\},$$ where $|\cdot|$ denotes the Euclidean ...
23
votes
3answers
1k views
Is every positive integer the permanent of some 0-1 matrix?
In the course of discussing another MO question we realized that we did not know the answer to a more basic question, namely:
Is it true that for every positive integer $k$ there exists a balanced ...
7
votes
1answer
323 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 ...
6
votes
5answers
2k 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, ...
4
votes
2answers
290 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 ...
2
votes
0answers
55 views
Minimum size of genus $g$ bipartite graphs with $2^n$ perfect matchings
Given $n\in\Bbb Z_{\geq0}$ let $2T_{n,g}$ be size of smallest number of vertices of genus $g$ bipartite graph with $T_{n,g}$ vertices of each color such that number of perfect matchings is $2^n$.
Eg: ...
3
votes
2answers
453 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. ...
5
votes
1answer
210 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 ...
3
votes
1answer
124 views
Unique matching completion
Assume we have bridgeless cubic graph $G(V, E)$, $n=|V|$.
By Petersen's theorem, every such graph has a perfect matching.
Moreover, given any edge in $G$ there exists a perfect matching containing ...
15
votes
2answers
1k 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 ...
3
votes
2answers
555 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 ...
3
votes
1answer
695 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 ...
1
vote
2answers
135 views
Reference Request: “Resolutions” of $K_n$ for $n$ odd
A resolution (in the combinatorial design sense) of $K_{n}$ is a collection of sets of edges of $K_{n}$ so that within each set of edges, each vertex appears once, and over the entire collection, each ...
7
votes
0answers
282 views
Missing count in number of perfect matchings
Let $f(G)$ give number of perfect matchings of a graph $G$.
Denote $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$.
Denote collection of all $2n$ vertex balanced bipartite graph to be $\mathcal G_{2n}$.
...
1
vote
0answers
108 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$...
1
vote
0answers
91 views
Expected number of perfect matchings in bounded degree bipartite graphs
Consider collection $\mathcal C_{n,n,\Delta}$ of every $2n$ vertex balanced bipartite graph of average degree $\Delta$.
What is the expected number of perfect matching a graph in $\mathcal C_{n,n,\...
4
votes
3answers
348 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 ...
1
vote
0answers
59 views
Largest number of perfect matchings in bounded genus graphs
What is the largest number of perfect matchings a genus $g$ bipartite graph on $n+m$ vertices have?
3
votes
0answers
70 views
Fraction of graphs with bound on number of perfect matchings
Asymptotically what is the fraction of balanced bipartite graph on $2n$ vertices with at most $cn^{\beta}$ edges having at most $n^\alpha$ perfect matchings for any fixed $c,\alpha>0$ and fixed $\...
1
vote
0answers
185 views
On symmetric difference of $k$-partite perfect matchings
Given a bipartite graph we know that symmetric difference of any two perfect matchings is union of even cycles.
Conversely when is it true that every union of even cycles comes from symmetric ...
4
votes
1answer
232 views
Probability bound for perfect matching
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 ...
-3
votes
2answers
612 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?
2
votes
1answer
111 views
“Hypo” and “Hyper” for Perfect Matching
There is a fairly rich classification on graphs with respect to the existence of Hamiltonian cycles either in unmodified graphs or after certain small modifications.
Do there also exist such ...
8
votes
2answers
578 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 ...
1
vote
1answer
58 views
Test Instances for Perfect Matchings in Graphs
Are there any graphs with a known set of perfect matchings and other predefined properties, such as vertex connectivity, which can be used for testing the implementation of matching algorithms?
...
6
votes
1answer
484 views
Algorithm to count the number of perfect matchings in non planar graph
I need to count the number of perfect matchings of a certain family of graphs. This family of graph is non planar and a type of snark. For the initial cases, it seems that this number is growing ...
1
vote
2answers
136 views
The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)
In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$).
This is what I observed from some books (e.g. "Combinatorial ...
2
votes
2answers
205 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 ...
-2
votes
1answer
181 views
About structure of the set of perfect matchings of $K_{n,n}$
Are there any special properties known about the set of perfect matchings of $K_{n,n}$? Like any global structure of this set? Some natural way to partition it? Like is there some algebraic structure ...
3
votes
0answers
256 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 ...
11
votes
2answers
539 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 ...
4
votes
0answers
122 views
Mixing time for dimers on the square-octagon graph
Consider the "fortress graph" of order $n$ (see Figure 9 of http://faculty.uml.edu/jpropp/tiling/www/mdblum/arctic.html). It's been known empirically for twenty years that if one turns the set of ...
4
votes
0answers
195 views
Counting perfect matchings with integrals
Has anyone used the Joni-Rota-Godsil integral formula (see details below) to count perfect matchings of square-grid graphs, Aztec diamond graphs, hexagon-honeycomb graphs, etc.? (Or even just to ...
6
votes
0answers
285 views
Kasteleyn, Gessel-Viennot and eigenvalues
The Kasteleyn matrix (for counting perfect matchings) and the Lindström-Gessel-Viennot matrix (for counting families of nonintersecting lattice paths) are tightly related, as observed many times by ...
5
votes
0answers
141 views
Complexity of finding three perfect matchings with no edge in common in a bridgeless cubic graph
According to a conjecture:
Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common.
Equivalent statement here
Main question:
...
