# Questions tagged [matching-theory]

For questions about matchings in graph theory. A matching on a graph is a set of edges such that no two edges share a common vertex.

**2**

votes

**1**answer

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

**0**

votes

**1**answer

58 views

### All even order graphs with $\Delta\ge\frac{n}{2}$ is Class 1

Are all even order graphs with maximum degree $\ge\frac{|V(G)|}{2}$ Class 1(edge-colorable(chromatic index) with $\delta(G)$ colors)? Here, $|V(G)|$ detnotes the number of vertices in the graph.
I ...

**0**

votes

**0**answers

46 views

### Matching (graph theory) [closed]

There are 8 blocks, consisting of two cubes (black and white), and a platform for constructing special things. One of the blocks is glued to the platform as shown in the picture to the left. How many ...

**0**

votes

**1**answer

69 views

### Hall theorem with non-saturating matching

Hall's marriage theorem states that given a bipartite graph $G=(X+Y,E)$, if there is no $X$-saturating matching, there there exists $W\subseteq X$ such that $|W|>|N_G(W)|$.
Is the following ...

**6**

votes

**0**answers

263 views

### Has this notion of vertex-coloring of graphs been studied?

In a study of a quantum physics problem, I came about an apparently very natural type of vertex colorings of a graph. The colors of the vertex $v_i$ is inherited from perfect matchings $PM$ of an edge-...

**2**

votes

**0**answers

59 views

### Graph pattern matching

Given a weighted, oriented, connected graph with $10^7$ vertices and $10^{10}$ edges I need to implement the algorithm for searching various patterns on this graph for less than polynomial time.
...

**5**

votes

**0**answers

152 views

### Can we represent partitions by mutually parallel lines in the plane?

Lately I have become interested in the following idea: Suppose $n$ is a positive integer and $[n]=\{1,2,3,...,n\}$. Suppose we have 3 distinct partitions $b$, $g$, and $r$ of $[n]$. Assume that the ...

**2**

votes

**1**answer

138 views

### Graphs with exactly $n$ perfect matchings

Is there for every $n\in\mathbb{N}$ a connected, simple, undirected graph $G_n=(V_n,E_n)$ such that $G_n$ has exactly $n$ perfect matchings?

**0**

votes

**1**answer

84 views

### Connected infinite graphs in which all matchings are “small”

Is there a countable, simple, connected graph $G=(\omega, E)$ such that $\text{deg}(v)$ is infinite for all $v\in \omega$, and for all matchings $M\subseteq E$ the set $V\setminus (\bigcup M)$ is ...

**3**

votes

**1**answer

78 views

### Maximal matchings in connected graphs

Let $n\in\mathbb{N}$ be a positive integer. Is there a connected graph $G$ such that $G$ cannot be coloured with less than $n$ colours, and every two maximal matchings have non-empty intersection?
(I ...

**2**

votes

**2**answers

105 views

### Graphs in which all maximal matchings intersect

Let $G=(V,E)$ be a simple, undirected graph. A matching is a set $M\subseteq E$ consisting of pairwise disjoint edges. We say $M$ is maximal if it is maximal amongst all matchings in $G$ with respect ...

**4**

votes

**2**answers

73 views

### Vertex cover number vs matching number

Let $G=(V,E)$ be a finite, simple, undirected graph. A matching is a set $M\subseteq E$ of pairwise disjoint edges. A vertex cover is a set $C\subseteq V$ of vertices such that $C\cap e \neq \emptyset$...

**1**

vote

**0**answers

61 views

### Matchings in infinite, not necessarily bipartite, graphs

Aharoni, Nash-Williams, and Shelah have extended the famous marriage theorem for finite bipartite graphs due to Hall to arbitrary graphs.
Is there a similar generalization of Tutte's theorem on ...

**1**

vote

**1**answer

103 views

### A weaker version of Dirac's theorem

This is related to Dirac's theorem.
For any finite, simple, undirected graph $G=(V,E)$ let $\delta(G)$ denote the minimal degree of all vertices.
Are there positive integers $n,c\in\mathbb{N}$ with ...

**1**

vote

**0**answers

14 views

### Reducing the Dimension of Rectangular Assignment Matrices

Question:
Given a weighted complete bipartite graph $K_{m,n}(U,V,E)$, $m^2\lt n$, are there any counter examples to the assumption, that the edges of the minimum weight maximal bipartite ...

**11**

votes

**1**answer

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

**4**

votes

**1**answer

214 views

### Bijection between noncrossing matchings on $2b$ points and Standard Young Tableaux of size $2 \times b$

I'm currently reading a review article called Dynamical Algebraic Combinatorics: Promotion, Rowmotion, and Resonance by Jessica Striker. In this article, Striker writes that there is a ''nice'' ...

**3**

votes

**2**answers

183 views

### A direct proof that every $r$-colored complete graph on $n=(r+1)m-(r-1)$ vertices has a monochromatic matching of size $m$?

Cockayne and Lorimer ("The Ramsey number for stripes" 1975) prove that in every $r$-colored complete graph on $n=\sum_{i=1}^rm_i+m_1-(r-1)$ vertices, where $m_1\geq \dots\geq m_r\geq 1$, has a ...

**-2**

votes

**1**answer

340 views

### Infinite graphs with large degree but no perfect matching [duplicate]

Is there an example of an infinite connected, simple, undirected graph $G = (V,E)$ such that every vertex has $|V|$ neighbors, but $G$ does not have a perfect matching (that is, a set $M\subseteq E$ ...

**3**

votes

**0**answers

112 views

### Forcing $A_1x,\dotsc,A_Kx$ to lie in a proper subspace

(This is a re-worked version of a question I asked several days ago.)
Let $J$ be the all-one matrix with $m$ rows and $n$ columns, and suppose that $J=A_1+\dotsb+A_K$ is a decomposition of $J$ into a ...

**-2**

votes

**1**answer

70 views

### Matching and minimal degree

Let $n\in\mathbb{N}$ be a positive integer and let $G =(V,E)$ be a connected simple undirected graph with $|V| = 2n$. Is it true that if for the minimal degree $\delta(G)$ we have $\delta(G) \geq n$, ...

**2**

votes

**1**answer

184 views

### Perfect matchings in infinite graphs

Let $G=(V,E)$ be an infinite graph such that $|V| = \kappa$ for some infinite cardinal $\kappa$, and every $v\in V$ has degree $\kappa$. Does $G$ have a perfect matching?

**-4**

votes

**1**answer

112 views

### Does the Hadwiger-Nelson graph have a perfect matching?

The Hadwiger-Nelson graph on $\mathbb{R}^n$ is defined to be $(\mathbb{R}^n,E_n)$ where $$E_n = \big\{\{x,y\}: x,y\in \mathbb{R}^n \text{ and } |x-y|=1\big\},$$ where $|\cdot|$ denotes the Euclidean ...

**1**

vote

**1**answer

50 views

### Hall type theorem for saturations of subsets of bipartite graphs

Let $X,Y$ be a bipartite graph and $X',Y'$ be two subsets of the vertices. Is there a Hall type theorem for the existence of matchings saturating both subsets simmultaneously?
Clearly necessary ...

**3**

votes

**0**answers

68 views

### Min-Cost Max-fractional matching

I have been looking for a proof of the following statement. I think it follows from the proof of the integrality of the matching polytope but I am not so sure.
Given a bipartite graph $G=(A \cup B, ...

**12**

votes

**2**answers

295 views

### Number of matchings of even cycles

By doing some calculations on the generating function of matching polynomials of cycles I made the following interesting observation:
For all positive integers $n>1$ and $k <n $, the number of ...

**7**

votes

**1**answer

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

**1**

vote

**1**answer

71 views

### Tutte's Reduction of Minimum Weight d-Factors to Matching

I am currently interested in minimum weight regular d-spanners (i.e. d-factors) of complete graphs. When searching the internet for related articles, I came across this one, which is concerned with ...

**5**

votes

**2**answers

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

**2**

votes

**0**answers

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

**3**

votes

**2**answers

478 views

### Applications of Hafnians

I am learning about Hafnians but I am struggling to find real-world applications of them. I understand the applications of determinants, permanents, and even pfaffians but I am at a loss for Hafnians. ...

**-1**

votes

**1**answer

214 views

### Marriages in infinite bipartite graphs with many neighbors

Let $A,B\neq \emptyset$ be disjoint and suppose $G = (A\cup B, E)$ is bipartite where for all $e\in E$ we have $e\cap A \neq \emptyset\neq e\cap B$. For $a\in A$ we set $N_G(a) = \{b\in B: (\exists e\...

**3**

votes

**1**answer

175 views

### Induced matching number

Definition:
A $\textit{matching}$ in a graph $G$ is a subgraph consisting of pairwise disjoint edges. If the subgraph is an induced subgraph, the matching is an $\textit{induced matching}$. The ...

**1**

vote

**1**answer

159 views

### Is greedy matching algorithm with normalized edge weights a 2-approximation

Given a weighted, undirected, bipartite, graph $G(V,E)$. All edge weights are assumed to be non-negative. Let $d(u)$ be the degree of vertex u. Let $c(u,v)$ be the cost of edge $(u,v)$. Goal: compute ...

**8**

votes

**1**answer

235 views

### Fastest algorithm for counting perfect matchings in a general graph

Let $G(V,E)$ be a undirected graph. I am interested in the fastest known algorithm for counting the number of perfect matchings in $G(V,E)$ (which is known to be in $\#P$). In particular, what is the ...

**3**

votes

**1**answer

129 views

### Unique matching completion

Assume we have bridgeless cubic graph $G(V, E)$, $n=|V|$.
By Petersen's theorem, every such graph has a perfect matching.
Moreover, given any edge in $G$ there exists a perfect matching containing ...

**18**

votes

**2**answers

1k views

### Graphs with only disjoint perfect matchings

Let $G(V,E)$ be a graph. I am searching for graphs with only disjoint perfect matchings (i.e. every edge only appears in at most one of the perfect matchings).
Examples:
Cyclic graph $C_n$ with even ...

**4**

votes

**2**answers

281 views

### Graphs with unique 1-Factorization

Let $G(V,E)$ be a graph with a 1-factorizations $M$ and $m=|M|$ 1-factors. I am searching for graphs with unique 1-factorizations (i.e. there is only one 1-factorization).
Examples:
Cyclic graph $...

**7**

votes

**2**answers

151 views

### Do successive maximum permutations pick latin squares uniformly?

Suppose we start with a $n\times n$ matrix with entries sampled independently and uniformly at random from $[0,1]$. The weight of a set of entries will simply be the sum of those entries. A ...

**8**

votes

**2**answers

306 views

### Maximum matching in a graph with no “shortcuts”

For a directed acyclic graph (DAG) $G$, denote by $G^\star$ the undirected graph obtained from $G$ by ignoring direction of its arcs. Let $e(G)=e(G^\star)$ be the number of arcs in $G$ (or edges in $G^...

**3**

votes

**1**answer

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

**1**

vote

**1**answer

1k views

### 2-approximation algorithm for Minimum Maximal Matching (MMM) problem

I'm looking to find a 2-approximation algorithm (pseudocode) for the minimum maximal matching problem. I tried to find one but I did not manage. I want to use it to implement a program in java. Can ...

**2**

votes

**0**answers

110 views

### Induced matchings in a bipartite graph with every matching having the same number of edges

Suppose $n,k$ are positive integers such that $k\mid n$.
Consider a bipartite graph $H=(A,B,E)$ such that $|A|=|B|=n$ and the edge set $E$ consists of the union of $m(H)$ induced matchings with every ...

**4**

votes

**1**answer

130 views

### Are Bipartite Matching and General Matching Really Different Problems?

Questions:
Have there been attempts to either prove or disprove, that every general matching problem can be transformed into a bipartite matching problem, from whose solution the solution of ...

**5**

votes

**2**answers

280 views

### Problems and Algorithms Requiring Non-Bipartite Matching

While the importance of the non-bipartite matching problem itself from an algorithmic and complexity point of view is well known, applications of non-bipartite matching are hard to find.
I did an ...

**1**

vote

**0**answers

111 views

### On Schrijver's lower bound for the number of perfect matchings

Schrijver's lower bound gives the number of perfect matchings in a $k$-regular bipartite graph as $\Big(\frac{(k-1)^{k-1}}{k^{k-2}}\Big)^n$. What is the corresponding lower bound for minimum-degree $k$...

**1**

vote

**0**answers

545 views

### Is there an efficient algorithm to find all the maximum matching in any tree?

A matching in a graph (G) is a set of mutually non-adjacent edges of (G). A maximum matching is a matching of maximal cardinality. A tree is an acyclic connected graph.
Is there an efficient ...

**3**

votes

**0**answers

70 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 $\...

**1**

vote

**0**answers

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

**4**

votes

**1**answer

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