All Questions
Tagged with perfect-matchings co.combinatorics
63 questions
32
votes
0
answers
3k
views
Vertex coloring inherited from perfect matchings (motivated by quantum physics)
Added (19.01.2021): Dustin Mixon wrote a blog post about the question where he reformulated and generalized the question.
Added (25.12.2020): I made a youtube video to explain the question in detail.
...
- 155
28
votes
3
answers
2k
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 ...
- 82.7k
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
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
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
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
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
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
8
votes
1
answer
384
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 ...
- 1,190
8
votes
0
answers
245
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 ...
- 13.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
7
votes
2
answers
500
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 $\...
- 1,190
7
votes
1
answer
974
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 ...
- 763
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 ...
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
7
votes
1
answer
696
views
Perfect matching in a vertex-transitive hypergraph
In connection with this MO problem, I wonder whether the hypergraph in
question was actually vertex-transitive. And so, as a natural variation (and,
perhaps, a refinement):
If the vertex set of a ...
- 23k
7
votes
0
answers
203
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 ...
- 965
7
votes
0
answers
349
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}$.
...
- 13.9k
6
votes
1
answer
252
views
Pair matching between divisors less and more than $\sqrt{N}$
Let $n$ be the positive integer. Let $A$ and $B$ be sets of divisors of $n$ less and more than $\sqrt{n}$ respectively.
Consider bipartite graph $(A, B)$, where two vertices are connected when one ...
- 163
6
votes
1
answer
230
views
A non-distinct system of representative edges
I have the following problem:
Let $ \mathcal{G} = (G_{i})\_{i} $ be a collection of graphs on the same vertex set. I would like to find a "system of representative edges" $ f : \mathcal{G} \...
- 161
6
votes
0
answers
375
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 ...
- 1,343
6
votes
0
answers
154
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:
...
- 25.4k
5
votes
2
answers
579
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
4
votes
1
answer
592
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 ...
- 239
4
votes
1
answer
111
views
Are there decompositions of $K_{16}$ by certain 3-regular graphs?
This is inspired by the problem of the Hoffman-Singleton Decomposition of $K_{50}$. I wanted to look at smaller variants of this kind of problem, and so naturally I started wondering:
Can the (edges ...
- 13.4k
4
votes
0
answers
187
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!\...
- 13.9k
3
votes
2
answers
397
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 ...
- 380
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
3
votes
1
answer
131
views
A graph $G$ with two $K_6$ subgraphs, in which any one-factor of $G$ induces a one-factor in exactly one of the $K_6$ subgraphs?
I'm seeking a simple graph $G$ of the following type:
It contains two disjoint copies of $K_6$ (the complete graph on 6 nodes), $H$ and $H'$ say.
Any one-factor of $G$ must contain either (a) a one ...
- 4,229
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
3
votes
1
answer
145
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 ...
- 13.2k
3
votes
1
answer
141
views
Generalizations of a theorem of Edmonds/Tutte on existence of a perfect matching in a graphs
It is well known that for a bipartite graph $G$ with bi-adjacency matrix $A$, then $\det A \neq 0$ (as a polynomial) iff $G$ has a perfect matching (there is a similar result for general graphs with ...
- 129
3
votes
1
answer
376
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
3
votes
0
answers
232
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 ...
- 15.8k
3
votes
0
answers
75
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 $\...
- 13.9k
3
votes
0
answers
88
views
Perfect Matching for Edge-transitive Hypergraphs
I'm new to this subject, but I've noticed that a lot of work has been done on perfect matching in k-uniform hypergraphs. I'm curious to know if there are any results on perfect matching in the more ...
- 31
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
2
votes
2
answers
123
views
Existence of certain regular graphs
Question:
what can be said about the existence of $2k$ regular graphs, $1\lt k$ that have a $1$-factor and a $2$-factor?
Provided their existence, what is/are the smallest for $k$?
The graphs must be ...
- 13.2k
2
votes
1
answer
430
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
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
2
votes
1
answer
152
views
Graph immersed into the plane with segments as edges and we search for matching with no edges intersecting
There are some points in the plane and some of them are connected with segments between them. We look at this structure as a graph immersed into the plane where the points are the vertices and the ...
- 286
2
votes
0
answers
124
views
Symmetric matching in special graphs
Let $G$ be a bipartite graph, $L$ ($R$) be the set of vertices in the left (right) part.
Consider a graph $T$ with the set of vertices $R \times L$ ( $L \times R$ ) in the left (right) part. For any $...
2
votes
0
answers
163
views
Generalizing Hall's marriage theorem to non-perfect matchings
Let $G = (X, Y, E)$ be bipartite graph such that $|X|=|Y|=n$.
A matching $M \subseteq E$ is a subset of disjoint edges
(i.e., there does not exist a pair of edges $(x, y) \in M$ and $(x', y') \in M$ ...
- 121
2
votes
0
answers
108
views
Counting number of perfect matchings
Counting perfect matchings in bipartite graphs is $\# P$ complete. Let $G(V,E)$ be a graph known to have $d$ number of perfect matchings. Bipartite it the obvious way by adding $E$ vertices with one ...
- 13.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
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
2
votes
0
answers
64
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: ...
- 13.9k
2
votes
0
answers
365
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 ...
- 13.9k
1
vote
1
answer
190
views
Converse of Petersen's 2-Factorization Theorem
Definition: A $k$-factor of a graph is a spanning $k$-regular
subgraph.
Definition: A $k$-factorization of a graph is a partition of the edge
set into $k$-factors.
Petersen's celebrated ...
- 6,962
1
vote
1
answer
178
views
Planar eucliean bipartite matching with squared distances
This is probably a really stupid question, but suppose I have two sets of points in the plane $X$ and $Y$ each with cardinality $|X| = |Y| = n$. For any bipartite matching $M$ between $X$ and $Y$, ...
