Tagged Questions

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

2
votes
0answers
66 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 ...
8
votes
1answer
327 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 ...
2
votes
0answers
66 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
77 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 ...
4
votes
0answers
141 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
113 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
100 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 ...
2
votes
0answers
51 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
152 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
221 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
122 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
115 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 ...
4
votes
1answer
309 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 ...
4
votes
1answer
236 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
74 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}) ...
2
votes
6answers
491 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
925 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
2answers
665 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 ...