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

146
questions

2
votes

1
answer

40
views

### Maximal matchable set in hypergraph with finite edges

Let $H=(V,E)$ be a hypergraph. A set $M\subseteq E$ consisting of mutually disjoint members of $E$ is said to be a matching. We say $S\subseteq V$ is matchable if there is a matching $M$ such that $\...

2
votes

2
answers

75
views

### Matching number in infinite hypergraphs

If $H= (V,E)$ is a hypergraph, a matching is a set $M\subseteq E$ such that $e_1\cap e_2 = \emptyset$ whenever $e_1\neq e_2 \in M$. The matching number $\mu(H)$ of a hypergraph $H=(V,E)$ with $V$ ...

1
vote

0
answers

20
views

### Topology of densest graphs whose optimal $3D$-matching can be calculated efficiently

let $A=\lbrace a_1,\,\dots,\,a_k\rbrace $ and $B=\lbrace b_1,\,\dots,\,b_{2k}\rbrace,\ A\cap B=\emptyset$ be be a partition of a graph's vertex set $V$, i.e. $V\,=\,A\cup B$.
Question:
has $G:=\...

1
vote

0
answers

89
views

### Do I need to find a maximum matching to get the matching number of a graph?

Let’s say we are talking about a simple undirected graph with no loops and no multiple edges. But not necessarily bipartite. And we need to find its matching number. Do we have to find a maximum ...

1
vote

2
answers

127
views

### What's the name of the graph operation of connecting two copies of a graph with a perfect matching?

Let $G=(V_1,E_1)$ be a simple graph with vertex set $\{v_1,v_2,\ldots,v_n\}$ and let $G'=(V_2,E_2)$ be another copy of $G$ with vertex set $\{u_1,u_2,\ldots,u_n\}$. Assume $V_1\cap V_2= \emptyset$.
...

0
votes

0
answers

57
views

### A counterexample of a theorem about matching extendable

$M$ is perfect if $M$ covers all vertices of $G$, and $M$ is extendable if $G$ has a perfect matching containing $M$. Moreover, a graph $G$ with at least $2k + 2$ vertices is said to be $k$-extendable ...

7
votes

2
answers

229
views

### Disjoint perfect matchings in complete bipartite graph

Let $K_{n,n}$ be a complete bipartite graph with two parts $\{u_1,u_2,\ldots,u_n\}$ and $\{v_1,v_2,\ldots,v_n\}$, and let $K^-_{n,n}$ be the graph derived from $K_{n,n}$ by delete a perfect matching $\...

3
votes

1
answer

208
views

### Generalization of Marshall Hall's Theorem to non-simple bipartite graphs

Lemma 8.6.5 of the book "Matching Theory" by Lovász and Plummer states the following lemma:
Lemma: Let $G$ be a simple bipartite graph with bipartition $(A,B)$, and assume that each point ...

7
votes

1
answer

309
views

### Berge-Fulkerson conjecture --- the planar case

A well-known conjecture of Berge and Fulkerson says that every bridgeless cubic graph has a collection of six perfect matchings that together cover every edge exactly twice. Is this still open for ...

5
votes

1
answer

217
views

### Bipartite graph with exactly one perfect matching

$\textbf{Problem:}$ Find all bipartite graphs $G[X,Y]$ satisfying the following properties:
$1.$ $|X|=|Y|$, where $|X|\ge 2$ and $|Y|\ge 2$.
$2.$ All vertices have degree three except for two vertices ...

0
votes

0
answers

28
views

### Can rectangular optimal assignment be reduced to quadratic optimal assignment

Let $G(V=A\mathbin{\dot\cup} B, E\subseteq A\times B)$ be a bipartite graph with $n=n_a+n_b,\ n_a\lt n_b $ vertices and weighted edges$.
Let further $G$ have a unique minimum weight matching $\mathcal{...

0
votes

1
answer

39
views

### Name for a type of assignment task

given a bipartite graph $G(U,V,E\subseteq U\times V)$ with strictly positive edge-weights; is there an established name for the the task of calculating the lightest spanning subgraph and what is the ...

8
votes

0
answers

362
views

### A perfect rainbow matching in an edge-colored graph with spanning color classes

This question is related to my last question and is eventually motivated by recent advances in quantum physics. Given an even number $n\ge 6$ and a positive integer $k<n$, Claim from the linked ...

5
votes

0
answers

242
views

### A special perfect matching in a complete edge-colored graph

In 2018 Mario Krenn posed this question, originated from recent advances in quantum physics. Despite very intensive Krenn’s promotion and our efforts, the question is answered only in special cases. ...

0
votes

0
answers

57
views

### Number of edges in bipartite graphs

Let $G$ be a bipartite graph on $n$ vertices of either color.
Suppose $G$ contains no perfect matching the number of edges can be $\Omega(n^2)$ (just do not place an edge between a particular pair of ...

0
votes

0
answers

10
views

### Terminal set of iterated edge-filtering

Given a finite symmetric graph $G(V,E)$ with randomly weighted edges, what will the set of edges be that survives the following refiltering process that is repeated until no edges exist that satisfy ...

1
vote

0
answers

61
views

### Is there any theorem similar to the Tutte–Berge formula?

Tutte–Berge formula is a characterization of the size of a maximum matching in a graph.
The theorem states that the size of a maximum matching of a graph
${\displaystyle G=(V,E)}$ equals $${\...

2
votes

0
answers

32
views

### Which edges to delete from cubic graphs to get good cycle covers?

Let $G\left(V,E\subset V\times V,\omega: V\supset \lbrace u,v\rbrace\mapsto w_{uv}\in\mathbb{R}\right);\ \left|e_{uv}\right|:=\omega_{uv}\quad$ be a cubic symmetric graph that contains a vertex-...

1
vote

1
answer

26
views

### Finding optimal cycle covers with fixed number of vertices

Optimal vertex-disjoint cycle covers of weighted symmetric graphs with $n$ vertices can be calculated efficiently with the method of Tutte.
It is also possible to efficiently calculate optimal ...

3
votes

1
answer

45
views

### Determining a specific perfect matching $M$ by repeatedly asking for $|M \cap M_i|$ for other perfect matchings $M_i$

Let $G=(V,E)$ be a complete bipartite graph with $2n$ vertices and $M \subset E$ some unknown perfect matching of $G$.
The goal is to determine $M$ by repeatedly choosing some perfect matching $M_i \...

3
votes

1
answer

79
views

### Maximum weight matching with classes of edges in a multi-edge bipartite graph

Consider a multi-edge bipartite graph $G = (L, R, E)$, with $|L| = |R| = n$, such that any $x \in L, y \in R$ have precisely two edges in $E$, $(x, y)_r, (x,y)_b$. We can imagine that we are assigning ...

1
vote

1
answer

160
views

### Unique bipartite perfect matchings and cycles?

Given a graph $G$ which is bipartite and balanced and has unique perfect matching let $G^{e}$ be $G$ without edge $e$. Let $G\cup G_{\pi,\pi'}$ be union of $G$ and $G_{\pi,\pi'}$ where $G_{\pi,\pi'}$ ...

1
vote

0
answers

52
views

### Algorithm for minimum weight matching with "tree topology"

Given a finite graph $G(V,E)$ with undirected and weighted edges, whose set of vertices $V$ is partitioned into a collection $\mathfrak{P}=\lbrace V_1,\,\dots,\,V_k\rbrace$ of non-empty and pairwise ...

0
votes

0
answers

22
views

### Complexity of heaviest 2-optimal vertex-disjoint cycle covers

Calculating lightest vertex-disjoint cycle covers of finite complete symmetric graphs with weighted edges can be done efficiently and also renders the edge set of the calculated cycles free of pairs ...

3
votes

1
answer

137
views

### Assignment problem with priorities and scores

I have run into a real problem that is actually a sort of assignment problem. I am describing it here because I am interested in knowing whether this problem already has a name (and whether there is ...

2
votes

0
answers

69
views

### Counting matchings in middle levels of the Boolean lattice

Let $k$ be a nonnegative integer and consider $C_k$, the set of all subsets $A$ of size $k$ in $[2k+1]=\{1,2,\ldots,2k+1\}$ as well as $C_{k+1}$, the set of all subsets $B$ of size $k+1$ in $[2k+1]$. ...

1
vote

0
answers

83
views

### Number of maximum matchings in bipartite graphs of positive surplus

Let $G$ be a simple bipartite graph with left part $L(G)$ and right part $R(G)$. For $S \subseteq L(G)$, denote $N(S)$ the set of neighbours of vertices of $S$. Define the surplus $s(G)$ as $\min_{S \...

3
votes

1
answer

128
views

### Perfect matchings in infinite regular bipartite graphs

This question was motivated by a discussion here and is related to a previous question here.
Let $\kappa$ and $\lambda$ be cardinals such that $0<\lambda\leq \kappa$. Let $G=(A\cup B, E)$ be a ...

4
votes

2
answers

202
views

### Relationship between minimum vertex cover and matching width

Let $H$ be a 3-partite 3-uniform hypergraph with minimum vertex cover number $\tau(H)$ (i.e. $\tau(H)=\min\{|Q|: Q\subseteq V(H), e\cap Q\neq \emptyset \text{ for all } e\in E(H)\}$).
Question: Is $\...

1
vote

0
answers

60
views

### $1$-factorizability for linear hypergraphs with infinite edges on $\omega$

Let $H=(V,E)$ be a hypergraph. We say that $M\subseteq E$ is a matching if the members of $M$ are pairwise disjoint, and $M$ is said to be perfect if $\bigcup M = E$. Moreover, $H$ is $1$-factorizable ...

3
votes

1
answer

48
views

### $1$-factorizability for "complete" finite hypergraphs

Let $H=(V,E)$ be a hypergraph such that $V\neq \varnothing$ and $\varnothing \notin E$. A matching is a subset $M\subseteq E$ such that $m_1\neq m_2 \in M$ implies $m_1\cap m_2 = \varnothing$, and $M$ ...

0
votes

0
answers

50
views

### Birkhoff's theorem for hypergraphs

Birkhoff's theorem says that, in a bipartite graph $G$ in which both sides have size $n$, any fractional matching of size $n$ can be presented as a convex combination of integral matchings of size $n$ ...

0
votes

1
answer

99
views

### Weak $1$-factorizability

A simple, undirected graph is said to be $1$-factorizable if there is a partition of the edge set $E$ such that every member of the partition is a perfect matching of $G$. Let us call $G$ weakly $1$-...

2
votes

1
answer

79
views

### Are countable graphs with infinite minimal degree $1$-factorizable? [duplicate]

We say that a simple, undirected graph $G=(V,E)$ is $1$-factorizable if there is a partition of $E$ such that every member of the partition is a perfect matching of $G$. It is easy to see that any $1$-...

11
votes

2
answers

1k
views

### Proving Hall's marriage theorem using Sperner's lemma

In the paper Hall's theorem for hypergraphs (Aharoni and Haxell, 2000),
the authors prove a theorem on the existence of perfect matchings in bipartite hypergraphs, using Sperner's lemma. At the last ...

2
votes

0
answers

172
views

### Perfect matching in hypergraphs: tripartite, regular and unbalanced

In a balanced bipartite graph - where both sides have the same size - a sufficient condition for the existence of a perfect matching is that the graph is regular - all vertices have the same degree.
...

2
votes

0
answers

81
views

### From fractional matching to integral matching in tripartite hypergraphs

Let $G = (X\cup Y, E)$ by a bipartite graph with $n = |X|\leq |Y|$.
A fractional matching is a function assigning a non-negative weight to every edge in $E$, such that the sum of weights near each ...

1
vote

0
answers

28
views

### Optimal preprocessing in the Kuhn-Munkres algorithm

The matrix formulation of the Kuhn-Munkres algorithm for solving the Linear Assignment Problem requires a preprocessing in which the minimal values of a line be subtracted from every value in that ...

4
votes

2
answers

215
views

### Max weighted matching where edge weight depends on the matching

Given a bipartite graph $G$, we seek a maximal weighted matching $E$. The particularity is below. Once an edge $e$ is chosen, the action of choosing $e$ adds a negative weight $w(e,e')$ to any other ...

9
votes

1
answer

787
views

### What graph's minimum vertex cover equals twice the maximum matching?

Matching: https://en.wikipedia.org/wiki/Matching_(graph_theory)
Vertex Cover: https://en.wikipedia.org/wiki/Vertex_cover
It is easy to see that
$$\texttt{minimum vertex cover} \leq 2 \texttt{ ...

0
votes

1
answer

214
views

### Expanding Hall's theorem [closed]

I'm trying to get a "feel" about Hall's theorem and try to expand it for one to many matching.
So my question is:
Given a bipartite graph, what would be a neccessary and sufficient condition for that ...

1
vote

0
answers

54
views

### Matching generating function of 2-lifts

Let $P_G$ denote the matching generating function of a finite simple bipartite graph $G$.
Let now $H$ be a $2$-lift of $G$. We know (see for example Proposition 5.3.3 in Barvinok's book Combinatorics ...

2
votes

2
answers

113
views

### Number of subgraphs with matching of size $n$ for a complete bipartite graph

Say we have a $K_{n,n}$ bipartite graph (i.e. a complete bipartite graph with $n$ nodes on each side). We induce a subgraph by deleting some subset of edges. There are $2^{n^2}$ possible subgraphs. ...

2
votes

1
answer

39
views

### maximum weighted matching with weights being sets

Given a set $S$ and a bipartite graph $G$, each edge $v\in E(G)$ covers a subset $S_v$ of $S$. My problem is to find a matching maximizing the number of covered elements, i.e., denote $V$ the set of ...

2
votes

1
answer

124
views

### Does there exist an r-regular graph (r≥2) with a unique maximum matching?

Akbari, Ghodrati, Hosseinzadeh (2017), On the structure of graphs having a unique k-factor, Aust. J. Combin. (pdf) show:
... we prove that there is no r-regular graph (r≥2) with a unique perfect ...

5
votes

0
answers

86
views

### Hypergraphs with only disjoint perfect matchings

Let $H(n,r)$ be the set of $r$-uniform hypergraph with $n$ vertices that have only disjoint perfect matchings (i.e. every hyperedge only appears in at most one of the perfect matchings). Let $m(h(n,r))...

5
votes

1
answer

61
views

### Sizes of matchings and transversals in hypergraphs

Let $H=(V,E)$ be a hypergraph. We call $H$ proper if $E\neq\emptyset, \emptyset \notin E$ and for no $e_1\neq e_2\in E$ we have $e_1\subseteq e_2$. A matching is a set $M$ of pairwise disjoint edges (...

2
votes

1
answer

239
views

### Extending perfect matchings into Hamiltonian cycles

Let $G$ be a simple cubic graph which has a Hamiltonian circuit $C$. In general, it is not possible to find a second Hamiltonian circuit which contains all the chords of $C$. For example, the Wagner ...

1
vote

2
answers

153
views

### Clutters with no maximum-size matchings

A clutter is a pair $C=(V,E)$ where $V\neq\emptyset$ is a set, and $E\subseteq {\cal P}(V)$ such that no member of $E$ is included in another member of $E$. A matching in $C$ is a collection of ...

0
votes

0
answers

55
views

### Decomposition of triangle-free bridgeless planar cubic graphs

Question:
is it true that every triangle-free connected bridgeless planar cubic graph can be decomposed into a vertex-disjoint cycle cover and a single maximal matching of the edges that are adjacent ...