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
30 votes
2 answers
3k views

An unfair marriage lemma

I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem: Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into ...
Sergei Ivanov's user avatar
21 votes
2 answers
3k 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 ...
Mario Krenn's user avatar
15 votes
3 answers
4k views

An analysis proof of the Hall marriage theorem

The Hall marriage theorem has several relatively easy combinatorial proofs. Are there short analytical or topological reformulations and proofs of that theorem?
user avatar
15 votes
3 answers
600 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^...
Max Alekseyev's user avatar
14 votes
2 answers
456 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 ...
Mostafa's user avatar
  • 4,454
13 votes
2 answers
796 views

Gale-Shapley stable marriage theorem: can we entrust matchmaking to monkeys?

Disclaimer: This is a question I have not done any real research about. I asked it myself some 5 years ago, and back then I had no idea where to start. Now I have some texts on stable matchings lying ...
darij grinberg's user avatar
13 votes
1 answer
3k views

Is there a version of König's theorem for tripartite 3-graphs?

I would like to know if there exists a version of König's theorem for tripartite $3$-graphs. In other words, let $G = (V,T)$ be a tripartite $3$-graph. That is, $V$ is a set of vertices (with $V$ ...
tbg's user avatar
  • 131
11 votes
5 answers
2k views

Are all almost regular graphs obvious?

Let the maximum and minimum degress of a graph be denoted (as usual) by $\Delta$ and $\delta$ respectively. A graph is almost regular if $\Delta-\delta=1$. Now, here is a simple way to generate ...
Felix Goldberg's 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 ...
Erel Segal-Halevi's user avatar
11 votes
1 answer
798 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 ...
Mario Krenn's user avatar
10 votes
1 answer
2k 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{ ...
phantom's user avatar
  • 317
10 votes
0 answers
607 views

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

This question is a sequel of 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 ...
Alex Ravsky's user avatar
  • 4,102
10 votes
0 answers
715 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-...
Mario Krenn's user avatar
8 votes
2 answers
711 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 ...
Turbo's user avatar
  • 13.7k
8 votes
1 answer
422 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 ...
Mario Krenn's user avatar
8 votes
3 answers
473 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 ...
Manfred Weis's user avatar
  • 12.6k
8 votes
1 answer
2k views

A matching that covers vertices with maximum degree

We have a graph G with maximum degree $\Delta$. The induced subgraph on vertices with degree equal to $\Delta$ is a bipartite graph (while the original graph is not). Prove that G has a matching that ...
Mohemnist's user avatar
  • 400
8 votes
1 answer
2k 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 ...
darij grinberg's user avatar
7 votes
1 answer
367 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 ...
Xin Zhang's user avatar
  • 1,130
7 votes
2 answers
408 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 $\...
Xin Zhang's user avatar
  • 1,130
7 votes
1 answer
912 views

Roots of matching polynomial of graph

At the end of this preprint, I make the following conjecture concerning the roots of the matching polynomial: If a graph $G$ is connected and contains a cycle, then the spectral radius of $G$ ...
David Bevan's user avatar
7 votes
2 answers
180 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 ...
Gjergji Zaimi's user avatar
7 votes
1 answer
906 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 ...
Turbo's user avatar
  • 13.7k
7 votes
2 answers
311 views

Perfect matchings of a regular, uniform, partite hypergraph

This is in relation to the question here. What, if any, are the known conditions for the existence of a perfect matching for a $r$-regular, $r$-uniform, $r$-partite hypergraph. I specifically ...
theGrolarBear's user avatar
7 votes
1 answer
463 views

How does this algorithmic proof of Edmonds-Gallai work?

Sorry, this is going to be technical and dirty. I am not looking for a proof of the Edmonds-Gallai structure theorem (I understand two of them, even if they are rather similar); I am trying to ...
darij grinberg's user avatar
6 votes
2 answers
7k views

How many perfect matchings in a regular bipartite graph?

We have a $d$-regular bipartite graph $G = (X,Y,E)$ with $|X| = |Y| = n$ and $|E| = nd$. What is an upper bound on the number of perfect matchings of $G$?
pnaky's user avatar
  • 61
6 votes
2 answers
477 views

Are all numbers from $1$ to $n!$ the number of perfect matchings of some bipartite graph?

Let $f(G)$ give the number of perfect matchings of a graph $G$. Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$. Consider collection of all $2n$ vertex balanced bipartite graph to be $\...
Turbo's user avatar
  • 13.7k
6 votes
1 answer
486 views

Induced matching number

Definition: A matching in a graph $G$ is a subgraph consisting of pairwise disjoint edges. If the subgraph is an induced subgraph, the matching is an induced matching. The largest size of an induced ...
user177523's user avatar
6 votes
1 answer
2k views

Maximum bipartite graph (1,n) "matching"

Last month I discovered a nice question on stackoverflow and thought the 1,n matching problem could be solved via introducing a 1,k tree matching. Look here for my question, but as Moron pointed out ...
Karussell's user avatar
  • 161
6 votes
1 answer
223 views

A non-distinct system of representative edges

I have the following problem: Let $ \mathcal{G} = (G_{i})\_{i} $ be a collection of graphs on the same vertex set. I would like to find a "system of representative edges" $ f : \mathcal{G} \...
julkiewicz's user avatar
6 votes
0 answers
242 views

Catalan numbers from matchings?

There are several examples of interpreting the Catalan numbers as non-nesting or non-crossing matchings of some graph. My question is: Is there a family of graphs $G_1,G_2,\dotsc$ with the number of ...
Per Alexandersson's user avatar
5 votes
2 answers
603 views

Matching polynomials and Ramanujan graphs

Is it purely coincidental that the same number $2\sqrt{d-1}$ appears in these two following apparently disparate concepts? A $d-$regular graph is said to be called Ramanujan if its adjacency ...
user6818's user avatar
  • 1,883
5 votes
2 answers
872 views

Matching number and chromatic number

If $G$ is a (finite) graph, denote with $\mu(G)$ the size of any maximum matching in $G$ (this number is also called the "matching number" of $G$). For odd integers $n$ we have $n=\chi(K_n) = 2\cdot\...
Dominic van der Zypen's user avatar
5 votes
2 answers
4k views

Solving assignment problem using Hungarian method vs min cost max flow problem

The traditional solution for the assignment problem is the Hungarian method - it's complexity is O(V^4) or O(V^3) if using Edmonds method. However, it can also be reduced to a min cost max flow ...
EugeneMi's user avatar
  • 201
5 votes
1 answer
251 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 ...
Mohammad Al-Turkistany's user avatar
5 votes
1 answer
294 views

Reference sought for Conway's observation on stable matchings

Looking for a reference on the observation that the set of stable matchings form a distributive lattice. This is attributed to Conway by Knuth in "Marriages Stables" but I would like an explicit ...
user16317's user avatar
5 votes
2 answers
796 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$...
Dominic van der Zypen's user avatar
5 votes
1 answer
698 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 ...
Sanket Biswas's user avatar
5 votes
1 answer
77 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 (...
Dominic van der Zypen's user avatar
5 votes
1 answer
117 views

Generalization of Menger's theorem to infinite graphs

Aharoni and Berger generalized Menger's Theorem to infinite graphs: For any digraph, and any subsets $A$ and $B$, there is a family $F$ of disjoint paths from $A$ to $B$ and a set separating $B$ from $...
Tri's user avatar
  • 1,366
5 votes
1 answer
260 views

On optimal dual solutions for the minimum weight perfect matching problems in the case of metric weights

Following Lovasz-Plummer (Matching theory, North-Holland 1986, Theorem 9.2.1), the minimum weight perfect matching problem on a complete graph $G$ with even number of vertices and weight $w:E(G)\to \...
Mikhail Ostrovskii's user avatar
5 votes
0 answers
108 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))...
Mario Krenn's user avatar
5 votes
0 answers
275 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 ...
David Richter's user avatar
5 votes
0 answers
241 views

When does a "stable" assignment of buyers into goods exist?

Consider a setting of $n$ buyers and $m$ goods. We have a value matrix $V\in[0,1]^{n\times m}$ specifying how much each buyer values each good (everything is open information here and there is no ...
R B's user avatar
  • 608
5 votes
0 answers
240 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 ...
James Propp's user avatar
  • 19.4k
4 votes
2 answers
427 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 $...
Mario Krenn's user avatar
4 votes
2 answers
942 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. ...
Aidan Kehoe's user avatar
4 votes
1 answer
1k views

Polygamous stable marriage/ assignment problem

I'm not sure under which 'algorithm' it falls under, but here is the problem: I need to match each person to 5 people from the opposite gender (each guy gets 5 girls, each girl gets 5 guys). Not all ...
EugeneMi's user avatar
  • 201
4 votes
1 answer
188 views

Is König's Property for graphs inheritable from finite subgraphs?

Let $G = (V,E)$ be a simple, undirected graph. A set $C \subseteq V$ is said to be a (vertex) cover if $C \cap e \neq \emptyset$ for all $e\in E$. A matching is a set $M\subseteq E$ of pairwise ...
Dominic van der Zypen's user avatar
4 votes
2 answers
242 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 $\...
Louis D's user avatar
  • 1,666