**2**

votes

**0**answers

77 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

**1**answer

342 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

**0**answers

72 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

**0**answers

93 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

**0**answers

169 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

**0**answers

117 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

**1**answer

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

**3**

votes

**0**answers

56 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

**1**answer

159 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

**1**answer

249 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

**1**answer

123 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

**1**answer

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

**5**

votes

**1**answer

326 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

**1**answer

246 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

**0**answers

77 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

**6**answers

510 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

**2**answers

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

**2**answers

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