# 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.

125
questions

2
votes

0
answers

90
views

### Counting matchings and perfect matchings

A matching in a graph is a subset of the edges such that
no two edges share a vertex. A perfect matching is a matching where every vertex is part of exactly one edge in the matching.
Counting the ...

0
votes

0
answers

25
views

### Finding a bipartite graph that contains a specific elements of perfect matchings

I am a physicist who is interested in the applications of graph theory.
I've been studying the bipartite graphs and perfect matching finding problems. I see there are several research works on ...

3
votes

2
answers

368
views

### An "incomplete" tiling?

Given an $m\times n$ chess board, we place $p$ $2\times 1$ dominoes on the board so that they don't overlap. How many ways can we place them?
When each square of the board is covered by a domino this ...

1
vote

0
answers

71
views

### Bounds for smallest non-trivial designs

Given $s>t\ge 2$, let $N(s,t)$ be the smallest integer $n>s$ such that there exists an “$(n;s;t;1)$-design” (i.e., a collection of $s$-subsets $e_1,\dots,e_m$ of $[n]:=\{1,\dots,n\}$, such that ...

0
votes

1
answer

26
views

### Edge-length constraints from greedy matching

The subject of this question are perfect matchings of a complete undirected graph $G(V,E), n:=\mathrm{card}(V)=2k$, without self-loops or parallel edges and $n=2k$ vertices.
The objective is to ...

1
vote

0
answers

85
views

### Hopcroft–Karp Algorithm for a dynamic graph

As so you all know, we have Hopcroft–Karp Algorithm for maximum matching between two sides in a bipartite graph. It runs in $O(\sqrt{V} \times E)$ where $V$ is the vertex set and $E$ is the edges set.
...

0
votes

0
answers

29
views

### Finding optimal cycle covers with vertex cardinality constraints

Let $G(V,E)$ be an asymmetric graph of order $n$ without parallel edges or self loops.
Let further $\lbrace\nu_i\in\mathbb{R}\rbrace$ be a set of weights assigned to the vertices and $\lbrace\omega_{...

0
votes

1
answer

112
views

### Curious identity involving the number of perfect matchings of the complete graph

Can you prove (preferably combinatorially) the following identity for the total number of perfect matchings of the complete graph $K_{2n}$, where the edges in the matching are ordered, i.e., $\binom{...

0
votes

0
answers

87
views

### Bound on the number of maximum matchings in a graph

It is known that the number of perfect matchings in a graph is bounded above by the integer part of the square root of the permanent of its adjacency matrix. But, suppose I take the square root of the ...

1
vote

1
answer

56
views

### Symmetry of optimal solutions to symmetric assignment problems

Is there a sound proof of or a counter example to the following conjecture:
if $\boldsymbol{A}^T=\boldsymbol{A}$ is the cost-matrix of a bipartite assignment problem with unique optimal assignment,
...

4
votes

2
answers

219
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 ...

7
votes

0
answers

174
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 ...

1
vote

0
answers

59
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 ...

1
vote

2
answers

131
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$.
...

3
votes

1
answer

325
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 ...

2
votes

0
answers

57
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 ...

7
votes

2
answers

300
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 $\...

3
votes

1
answer

273
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 ...

7
votes

1
answer

324
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 ...

8
votes

0
answers

240
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 ...

1
vote

1
answer

104
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 ...

5
votes

1
answer

447
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 ...

9
votes

0
answers

579
views

### A rainbow perfect matching in an edge-colored graph with spanning color classes

This question is a sequel of 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 ...

5
votes

0
answers

369
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
votes

1
answer

230
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 ...

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, ...

4
votes

0
answers

182
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!\...

2
votes

0
answers

62
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 ...

0
votes

1
answer

121
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 ...

5
votes

2
answers

434
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 ...

1
vote

0
answers

89
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 ...

3
votes

1
answer

52
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 \...

1
vote

1
answer

225
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'}$ ...

0
votes

0
answers

32
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-...

1
vote

0
answers

42
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$ ...

1
vote

0
answers

89
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$...

2
votes

1
answer

108
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.
...

3
votes

1
answer

208
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 ...

3
votes

0
answers

84
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

62
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 ...

3
votes

1
answer

51
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$ ...

0
votes

1
answer

105
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$-...

2
votes

1
answer

80
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$-...

3
votes

1
answer

185
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 ...

4
votes

1
answer

104
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 ...

2
votes

0
answers

55
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 $...

-1
votes

1
answer

105
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 ...

5
votes

3
answers

390
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 ...

5
votes

0
answers

92
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))...

2
votes

1
answer

273
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 ...