All Questions
Tagged with matching-theory graph-theory
128 questions
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 ...
- 32.4k
21
votes
2
answers
4k
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 ...
- 155
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?
user6976
15
votes
3
answers
613
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^...
- 34.3k
14
votes
2
answers
481
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 ...
- 4,484
13
votes
2
answers
811
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 ...
- 33.8k
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$ ...
- 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 ...
- 6,962
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 ...
- 3,549
11
votes
1
answer
819
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 ...
- 155
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{ ...
- 317
10
votes
0
answers
626
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 ...
- 5,409
10
votes
0
answers
748
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-...
- 155
8
votes
2
answers
759
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 ...
- 13.9k
8
votes
1
answer
384
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 ...
- 1,190
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 ...
- 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 ...
- 33.8k
7
votes
2
answers
480
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 $\...
- 13.9k
7
votes
2
answers
500
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 $\...
- 1,190
7
votes
1
answer
952
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$ ...
- 674
7
votes
3
answers
393
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 ...
7
votes
1
answer
969
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 ...
- 13.9k
7
votes
1
answer
467
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 ...
- 33.8k
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$?
- 61
6
votes
1
answer
538
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 ...
- 381
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 ...
- 161
6
votes
1
answer
230
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} \...
- 161
6
votes
0
answers
296
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 ...
- 15.8k
5
votes
2
answers
611
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 ...
- 1,893
5
votes
2
answers
913
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\...
- 48.8k
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 ...
- 201
5
votes
1
answer
280
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 ...
- 2,993
5
votes
2
answers
910
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$...
- 48.8k
5
votes
1
answer
1k
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 ...
- 181
5
votes
1
answer
125
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 $...
- 1,644
5
votes
0
answers
115
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))...
- 155
5
votes
0
answers
244
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 ...
- 618
4
votes
2
answers
445
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 $...
- 155
4
votes
2
answers
985
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. ...
- 111
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 ...
- 201
4
votes
1
answer
193
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 ...
- 48.8k
4
votes
2
answers
257
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,701
4
votes
1
answer
592
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 ...
- 239
4
votes
0
answers
118
views
Reorganizational matching
Motivation. My friend works in an organization that is re-organizing itself in the following somewhat laborious way: There are $n$ people currently sitting on $n$ jobs in total (everyone has one job). ...
- 48.8k
4
votes
2
answers
381
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 ...
- 367
4
votes
0
answers
95
views
Is the size of maximum matching in vertex transitive 3-uniform hyper-graph on $n$ vertices always $\Omega(n)$?
What is the best known lower bound on the size of the maximum matching in a vertex transitive $3$-uniform hyper-graph?
- 197
4
votes
0
answers
207
views
Bounds on numbers of matchings of given sizes in bipartite graphs
I am interested in the following question:
For which sets ${m_1,\ldots m_k}$ of positive integers do there exist bipartite graphs having exactly $m_i$ matchings of size $i$ for each $1\leq i \leq k$, ...
- 1,327
3
votes
1
answer
778
views
Equitable edge coloring of graphs
Consider a simple regular graph $G$ with $n$ vertices and $E$ edges. Then, can we say that the edges can be colored equitably in $\Delta+1$ colors? By equitability is meant that a proper $\Delta+1$ ...
- 2,089
3
votes
1
answer
3k
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 ...
- 4,589
3
votes
1
answer
131
views
A graph $G$ with two $K_6$ subgraphs, in which any one-factor of $G$ induces a one-factor in exactly one of the $K_6$ subgraphs?
I'm seeking a simple graph $G$ of the following type:
It contains two disjoint copies of $K_6$ (the complete graph on 6 nodes), $H$ and $H'$ say.
Any one-factor of $G$ must contain either (a) a one ...
- 4,229