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.
119
questions
0
votes
0
answers
19
views
Existence of perfect "sub-matchings" in symmetric bipartite regular graphs
Given a symmetric $k$-regular assignment matrix $\boldsymbol{A}\in\lbrace 0,1\rbrace^{r\cdot s\,\times r\cdot s}$ that is "partitioned" into submatrices of size $r\times r$.
The existence of ...
- 11k
4
votes
2
answers
119
views
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment
I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
- 229
7
votes
0
answers
143
views
Upper bound on the number of perfect matchings in $K_{3,3}$-free graphs
Let $G=(V,E)$ be a graph with an even number of vertices $|V|=2n$. Assume that $G$ is $K_{3,3}$-free i.e. it does not contain a graph isomorphic to biclique $K_{3,3}$. A perfect matching of $G$ is a ...
- 885
1
vote
0
answers
50
views
On perfect matchings on planar graphs - is there a linear time deterministic algorithm?
The slides here provide a way to get a pfaffian orientation from Minimum Spanning Tree.
MST can be found in linear time if graph is planar and weights are $1$ and the slides give a linear time ...
- 12.8k
0
votes
0
answers
15
views
Can the most distant edge-disjoint pair of perfect matchings be calculated efficiently
Question:
has the linear program
\begin{align}
\text{LP:} \\
& \sum_{ij} w_{ij}\cdot(b_{ij}-a_{ij})\ \stackrel{!}{=}\ \max \\
\text{s.t. } & \sum_{ij}a_{ij}\ \le\ \sum_{ij}b_{ij} \\
& 0\ ...
- 11k
1
vote
2
answers
127
views
What's the name of the graph operation of connecting two copies of a graph with a perfect matching?
Let $G=(V_1,E_1)$ be a simple graph with vertex set $\{v_1,v_2,\ldots,v_n\}$ and let $G'=(V_2,E_2)$ be another copy of $G$ with vertex set $\{u_1,u_2,\ldots,u_n\}$. Assume $V_1\cap V_2= \emptyset$.
...
- 413
3
votes
0
answers
166
views
The perfect matching problem of planar graph
We know that connectivity is closely related to the Hamiltonian of planar graphs.
The most famous result is the Tutte theorem.
Theorem (Tutte, 1956). A 4-connected planar graph has a Hamiltonian ...
- 577
2
votes
0
answers
55
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 ...
- 12.8k
7
votes
2
answers
229
views
Disjoint perfect matchings in complete bipartite graph
Let $K_{n,n}$ be a complete bipartite graph with two parts $\{u_1,u_2,\ldots,u_n\}$ and $\{v_1,v_2,\ldots,v_n\}$, and let $K^-_{n,n}$ be the graph derived from $K_{n,n}$ by delete a perfect matching $\...
- 982
3
votes
1
answer
208
views
Generalization of Marshall Hall's Theorem to non-simple bipartite graphs
Lemma 8.6.5 of the book "Matching Theory" by Lovász and Plummer states the following lemma:
Lemma: Let $G$ be a simple bipartite graph with bipartition $(A,B)$, and assume that each point ...
- 181
7
votes
1
answer
309
views
Berge-Fulkerson conjecture --- the planar case
A well-known conjecture of Berge and Fulkerson says that every bridgeless cubic graph has a collection of six perfect matchings that together cover every edge exactly twice. Is this still open for ...
- 982
8
votes
0
answers
228
views
Sum of perfect matching construction
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 ...
- 12.8k
1
vote
1
answer
96
views
Succinct polynomial sized representation of balanced bipartite graphs whose perfect matching count is a primorial
Is there a $P$ time definable sequence of succinct polynomial sized representation of balanced bipartite graphs whose number of perfect matchings is a primorial?
For factorial a complete bipartite ...
- 12.8k
5
votes
1
answer
217
views
Bipartite graph with exactly one perfect matching
$\textbf{Problem:}$ Find all bipartite graphs $G[X,Y]$ satisfying the following properties:
$1.$ $|X|=|Y|$, where $|X|\ge 2$ and $|Y|\ge 2$.
$2.$ All vertices have degree three except for two vertices ...
- 181
8
votes
0
answers
362
views
A perfect rainbow matching in an edge-colored graph with spanning color classes
This question is related to my last question and is eventually motivated by recent advances in quantum physics. Given an even number $n\ge 6$ and a positive integer $k<n$, Claim from the linked ...
- 2,657
5
votes
0
answers
242
views
A special perfect matching in a complete edge-colored graph
In 2018 Mario Krenn posed this question, originated from recent advances in quantum physics. Despite very intensive Krenn’s promotion and our efforts, the question is answered only in special cases. ...
- 2,657
0
votes
0
answers
82
views
$0/1$ permanent symmetries
Assume matrix $A\in\{0,1\}^{n\times n}$ satisfies condition either $per(A)=0$ or $per(A)=1$.
Under what conditions is the value of $per(A+A')>per(A)$ where $'$ is transpose?
Under what conditions ...
- 12.8k
2
votes
1
answer
179
views
At most one perfect matching of a bipartite graph
I. Given biadjacency matrix $A$ of a bipartite graph on $2n$ vertices having $n$ vertices of either color on the constraints the graph either has
$0$ perfect matchings
$1$ perfect matchings
is it ...
- 23
0
votes
0
answers
57
views
Number of edges in bipartite graphs
Let $G$ be a bipartite graph on $n$ vertices of either color.
Suppose $G$ contains no perfect matching the number of edges can be $\Omega(n^2)$ (just do not place an edge between a particular pair of ...
- 12.8k
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
4
votes
0
answers
179
views
Dyadic distribution of $0/1$ permanents
Fix reals $a,b\in(1,2)$ satisfying $1<b<a<ab<2$.
What fraction of $0/1$ matrices of dimensions $n\times n$ have permanents
in $[b2^m,a2^m]$ at some $m\in\{0,1,2,\dots,\lfloor\log_2n!\...
- 12.8k
2
votes
0
answers
41
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
0
votes
1
answer
86
views
Minimum-weight disjoint union of perfect matchings
Is there a counter example or proof for the claim that the lightest edge-disjoint union of a pair of perfect matchings contains the edges of the lightest perfect matching in a finite complete graph ...
- 11k
5
votes
2
answers
338
views
Smallest $3$-regular graph with a unique perfect matching
What is the smallest 3-regular graph to have a unique perfect matching?
With a large enough number of nodes, it is possible for a 3-regular graph to have no perfect matching (example can be seen in ...
- 169
1
vote
0
answers
73
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 ...
- 12.8k
3
votes
1
answer
45
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 \...
- 127
1
vote
1
answer
160
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'}$ ...
- 12.8k
0
votes
0
answers
29
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-...
- 11k
1
vote
0
answers
34
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$ ...
- 12.8k
1
vote
0
answers
76
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$...
- 12.8k
2
votes
1
answer
104
views
Mod $2$ information on perfect matchings in general graphs
Determinant modulo $2$ of biadjacency matrix of bipartite graphs provide mod $2$ information on number of perfect matchings on bipartite graphs providing polynomial complexity in bipartite situations.
...
- 12.8k
3
votes
1
answer
128
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,461
3
votes
0
answers
76
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 ...
1
vote
0
answers
60
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 ...
- 39.4k
3
votes
1
answer
48
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$ ...
- 39.4k
0
votes
1
answer
99
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$-...
- 39.4k
2
votes
1
answer
79
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$-...
- 39.4k
3
votes
1
answer
158
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 ...
- 11k
3
votes
1
answer
64
views
Finding minimum weight perfect matchings in sparse bipartite graphs
Question:
What can be recommended for finding optimal perfect matchings in large bipartite graphs with small vertex degree if the edge-weights are positive real values?
I am looking for ...
- 11k
2
votes
0
answers
53
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
votes
1
answer
79
views
What is known about iterated matching as a TSP heuristic
A fairly wellknown heuristic for TSP that is based on matching is described in the 2003 paper Match twice and stitch: a new TSP tour construction heuristic by Andrew B. Kahng and Sherief Reda.
Its ...
- 11k
5
votes
3
answers
368
views
Can local flip moves connect dimer matchings on 'quadrangulated' planar bipartite graphs? (perfect matching reconfiguration problem)
I'm interested in the structure of dimer matchings on planar graphs with a bipartite structure. In particular, I'm interested in whether any two perfect matchings can be connected, i.e. transformed ...
- 565
5
votes
0
answers
86
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))...
- 565
2
votes
1
answer
239
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 ...
- 888
0
votes
1
answer
99
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 ...
- 1,611
-1
votes
2
answers
269
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 $\...
- 39.4k
0
votes
1
answer
233
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 ...
- 1,611
1
vote
0
answers
125
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 ...
- 888
1
vote
0
answers
50
views
Perfect matchings and edge cuts in cubic graphs - part 1
Let $G$ be a bridgeless cubic (simple) graph, and let $M$ be a perfect matching in $G$. $G-M$ will necessarily be a set of circuits. For example, if we delete a perfect matching from $K_{3,3}$ we ...
- 888
1
vote
1
answer
79
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 ...
- 12.8k