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.

learn more… | top users | synonyms

1
vote
0answers
22 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 ...
1
vote
3answers
110 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 ...
0
votes
0answers
41 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
59 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 ...
0
votes
0answers
73 views

Perfect matchings that never combine to form cycle union cover

Can there be exponential number (in terms of vertices) of perfect matchings on a bipartite graph so that no combination of them yields a union of cycles that cover all vertices? Is there a way to ...
0
votes
0answers
55 views

On symmetric difference of $k$-partite perfect matchings

Suppose we have 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 ...
4
votes
1answer
140 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
144 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
83 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
351 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
40 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? ...
3
votes
1answer
203 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
105 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
135 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
146 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 ...
2
votes
0answers
131 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 ...
9
votes
1answer
390 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 ...
3
votes
0answers
101 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 ...
3
votes
0answers
123 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 ...
5
votes
0answers
230 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
130 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: ...
0
votes
1answer
110 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 ...
3
votes
0answers
63 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 ...
5
votes
1answer
193 views

Matching on sphere to create cycle with chords

Imagine a number of chords of a sphere $S$ which nearly, but not quite, pass through the center of $S$, in such a way that no pair of chords intersect:       I would like ...
0
votes
1answer
410 views

Counting matchings in a bipartite matching-covered graph

A graph is called matching-covered if every edge is containd in a perfect matching. (Such graphs are also sometimes called "elementary", e.g. in Chapter 4 of "Matching Theory" by Lovasz & ...
1
vote
1answer
133 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$, ...
2
votes
1answer
116 views

Graph implemened 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 implemented into the plane where the points are the vertices and the ...
5
votes
1answer
382 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 ...
5
votes
1answer
287 views

Perfect matchings in certain classes of hypergraphs

While doing research I came unto the following problem: Given a hypergraph $H$ $r-partite$, $r-uniform$ (a r-graph, each edge contains r vertices), >$k- regular$ (all vertices have regular ...
2
votes
0answers
87 views

A non-distinct system of representative edges.

I have the following problem: Let $ \mathcal{G} = (G_{i})\_{i} $ be a collection of graphs. I would like to find a "system of representative edges" $ f : \mathcal{G} \rightarrow \bigcup_{i} E(G_{i}) ...
3
votes
6answers
659 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 ...
4
votes
2answers
1k views

A k-1 edge connected k regular graph is matching covered

As the title says, let $k \geq 2$ be a positive integer and let $G$ be a $(k-1)$-edge-connected $k$-regular graph with an even number of vertices. Then, for every edge $e$ of the graph there is a ...
6
votes
1answer
1k views

Condition on a bipartite graph to have an $m$-factor

This might be the most stupid question I am ever posting here: I am asking for a proof or a counterexample to a problem I proposed on MathLinks long ago. Let $G$ be a bipartite graph, i. e., a graph ...