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.

Filter by
Sorted by
Tagged with
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 $\...
user avatar
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$ ...
user avatar
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:=\...
user avatar
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 ...
user avatar
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$. ...
user avatar
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 ...
user avatar
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 $\...
user avatar
  • 982
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 ...
user avatar
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 ...
user avatar
  • 982
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 ...
user avatar
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{...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 2,657
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. ...
user avatar
  • 2,657
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 ...
user avatar
  • 12.8k
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 ...
user avatar
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 $${\...
user avatar
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-...
user avatar
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 ...
user avatar
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 \...
user avatar
  • 127
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 ...
user avatar
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'}$ ...
user avatar
  • 12.8k
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 143
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]$. ...
user avatar
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 \...
user avatar
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 ...
user avatar
  • 1,461
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 $\...
user avatar
  • 1,461
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 ...
user avatar
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$ ...
user avatar
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$ ...
user avatar
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$-...
user avatar
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$-...
user avatar
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 ...
user avatar
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. ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 491
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{ ...
user avatar
  • 307
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 ...
user avatar
  • 9
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 ...
user avatar
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. ...
user avatar
  • 31
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 ...
user avatar
  • 491
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 ...
user avatar
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))...
user avatar
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 (...
user avatar
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 ...
user avatar
  • 888
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 ...
user avatar
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 ...
user avatar