Questions tagged [matching-theory]

For questions about matchings in graphs.

424 questions
Filter by
Sorted by
Tagged with
10 views

Is there a relation between Hall's Theorem and the Gale-Shapley Deferred Acceptance Algorithm? If so, what?

Is there a relation between Hall's Theorem and the Gale-Shapley Deferred Acceptance Algorithm or the Rural Hospitals Theorem? If so, what? If not, why not?
28 views

67 views

78 views

Proof of Hall's marriage Theorem based on isolated vertex version

We all know the usual Hall theorem as follows: Theorem (Hall's Theorem, Hall (1935)). Let $G = (X, Y)$ be a bipartite graph. Then $G$ has a matching saturating all vertices of $X$ if and only if for ...
49 views

Graph with a perfect matching has a subgraph with a perfect matching. Is there a path between the vertices which are not contained in the subgraph?

I would like to show the following: Given a graph $G=(V,E)$ with a perfect matching $P_1$ and a subgraph $G[V\setminus \{v_1,v_2,v_3,v_4\}]$ with a perfect matching $P_2$, there exists a path $w$ ...
58 views

Is it possible to have a graph with a perfect matching, add 4 vertices and have a perfect matching for the bigger graph (+ one more condition)?

I encountered this problem about perfect matchings in my project and it is actually pretty important for the progress. It would be great if someone here can give me an idea (or even a solution to it). ...
155 views

How many connected components in this random graph?

I was reading this blog post about minimum-weight matchings on two-color point sets in the unit square and it got me thinking. Suppose you have 3 colors (Red, Blue, Green), and randomly drop $N$ ...
29 views

Minimal Hall Matching Violator Has Size At Most $\lceil \frac{n}{2} \rceil$?

Source of problem: Janson, Łuczak, and Ruciński, section 4.1 (page 82, line -10). The question: Let $G = (V_1 \cup V_2, E)$ be a bipartite graph with $|V_1| = |V_2| = n$ and no perfect matching. By ...
39 views

A graph based on sums in a sequence of numbers

Let $x_1,\ldots,x_n$ be numbers such that $1\geq x_1 \geq \cdots \geq x_n\geq 0$. Construct a undirected graph in which the vertices are $x_1,\ldots,x_n$, and there is an edge between $x_i$ and $x_j$ ...
26 views

An alternate proof of Existence of Stable Matching

The Gale-Shapely Algorithm gives the existence and efficient construction of a stable matching given n men and n women with complete preference list. But I was trying to prove existence without an ...
30 views

Vertex connectivity of a graph and matchings

Let $G$ be a graph with pairwise disjoint vertex classes $A$, $C$ and $B$, such that there is no edge from a vertex in $A$ to a vertex in $B$ and the cardinality of $C$ equals the vertex connectivity ...
19 views

Matching the labels of a clustering with ground truth labels for performance analysis

I'm working on clustering a dataset for which I have ground-truth labels. I want to evaluate the confusion matrix between the predicted and ground truth labels, but the labels assigned by my ...
49 views

Threshold function for the existence of a perfect matching in $G(n,p)$ (from the book of Frieze and Karonski)

I'm reading Introduction to Random Graphs by Frieze and Karonski. Theorem 6.2 determines the threshold for the appearance of a perfect matching in $\mathbf{G}_{n,p}$: Let $\omega=\omega(n)$, $c>0$...
62 views

Combinatorics, Hall's marriage theorem for bipartite graphs, where 2 vertices cannot be connected to more than one common vertex from the other side

I have a problem I'm trying to solve. the problem is: given Bipartite graph $G=(A\cup B,E)$, where $\vert A\vert=\vert B\vert=n>100$. and all edges are from $A$ to $B$ (all edges are symmetric), ...
42 views

Clarification on Diestel's proof of Tutte's Theorem.

Tutte's Theorem states: A graph $G$ has a 1-factor if and only if $\text{odd}(G −S) \leq |S|$ for all $S \subseteq V (G)$. I believe I understand why the forward implication holds. Diestel then ...
91 views

a curiosity about cards, why this is true?

We split the standard 52-card deck between 13 people, each of them gets 4 cards. In any case it is possible to take away one card from each person to fulfil the following condition: the 13 cards taken ...
109 views

A cubic graph with an bridge and the perfect matching

Given a cubic graph with an bridge. Consider this graph has perfect matchings. How can i prove that every perfect matching will cover the bridge in anyways? Has anyone an idea? Here is an possibe ...
80 views

Maximum multi-matching

I'm interested in the following variant of classical matching: A multi-matching is a subgraph of a given graph G that consists of disjoint cliques of size 2 or greater. The goal is to find a multi-...
87 views

How many perfect matches are there in a graph with $n$ connected components?

Question: Let $G=(V,E)$ be a graph with $n$ connected components, in which each component $G_i$ is the $K_{2i}$ graph. How many perfect matches are there in $G$? $Solution.$ We shall have a perfect ...
42 views

Maximum independent set in a graph versus maximum matching in the line graph

As regards this post Maximal independent sets in a graph $G$ versus maximal matchings in the line graph $L(G)$ -- and in particular, the comments under this answer https://math.stackexchange.com/a/...
6 views

Return several matches per person based on quality scores for the potential matches

I am trying to find a way to return a list of 5 matches per person based on preferences. This is sort of similar to the Stable Roommate Problem, but with multiple matches and with scores instead of ...
44 views

$G - u - v$ is not matchable if and only if $G$ has a barrier $B$ such that $u, v \in B$.

Question: Let $G$ be a matchable graph, and let $u$ and $v$ be distinct vertices of $G$. Show that $G - u - v$ is not matchable if and only if $G$ has a barrier $B$ such that $u, v \in B$. My ...
54 views

Closed form expression‎ of double-way matching problem (Special case of derangement)

Is there a "closed form expression‎" for below problem ? Problem : "N" guests gave their raincoats and their umbrellas to the doorman at the entrance of the “Marlinspike” mansion ...
62 views

Any $r$-regular bipartite graph can be partitioned into $r$ disjoint perfect matchings. I want to know whether a version of this extends to perfect $b$-matchings. Suppose we have a bipartite graph $G =... 1answer 31 views Smallest sum of differences between the numbers in two datasets I'm trying to assess the similarity between 2 datasets containing integer numbers. Both datasets are of equal length (size). For this, I am first removing all the numbers which appear in both datasets ... 1answer 59 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 ... 1answer 143 views Prove that if$G$has a perfect matching and no Tutte set contains$x,y$, then there is a perfect matching contains$x,y$Let$G$be a graph with a perfect matching, I want to prove that if no Tutte set contains both$x$and$y$, then there is a perfect matching contains the edge$xy$. Tutte set is defined as a set of ... 0answers 102 views Prove that in a 5-regular and 4-edge connected graph, every edge is in a perfect matching Suppose that$G$is a 5-regular graph and 4-edge connected graph, I want to prove that every edge is in some perfect matching. I can prove that for any edge$xy$, the graph$G-\{ xy\}$(delete the edge ... 1answer 86 views Is p-dimensional matching with$(p-1)n$edges NP-hard? What about$3n$edges? [closed] Let$p\geq 3$an integer. I am wondering whether or not the following problems are NP-hard or not (and if they are, I am looking for a convincing argument, or even better a detailed proof): Let$V_1, ...
I am interested in the probability of having a perfect matching in a bipartite graph $G=(V,E)$ for a fixed number of edges $|E|=k$. The number of the two sets of vertices is $|A|=|B|=n$. ($V=A\cup B$, ...
Suppose we have a bipartite graph $G=(X∪Y,E)$. It has the following properties： $|X| = |Y|$ Maximum degree of vertices is $k$ I want to extend $G$ to a $k$-regular bipartite graph. So I write a loop ...