**4**

votes

**1**answer

132 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

**2**answers

131 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

**1**answer

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

**7**

votes

**2**answers

298 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

**1**answer

35 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

**1**answer

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

**0**

votes

**1**answer

76 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

**2**answers

129 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

**1**answer

140 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

**0**answers

106 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

381 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

**0**answers

99 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

119 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

219 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

129 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

108 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

61 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

190 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

380 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

132 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

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

**1**answer

375 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

**1**answer

284 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

84 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

624 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

**1**answer

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