Questions tagged [matching-theory]

For questions about matchings in graphs.

Filter by
Sorted by
Tagged with
0
votes
0answers
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?
1
vote
1answer
28 views

If G is n regular, then G has n disjoint perfect matchings.

Let G be a bipartite simple graph show that: If G is n regular, then G has n paarwise disjoint perfect matchings. It's firstly easy to show that G has a perfect matching by using Hall’s Theorem, $|N(...
0
votes
1answer
18 views

Simple graph with vertex degree $\geq k$ has a matching of cardinality $\min\{k,\lfloor \frac{|V|}{2}\rfloor\}$

Essentially, I'm referring to this question The part I don't understand is why a graph with $\#V<2k$ must have a matching of cardinality $\lfloor \frac{|V|}{2}\rfloor$. Can someone explain?
3
votes
1answer
32 views

Complexity of finding a matching with color constraints in an edge-colored graph with only 2 colors.

Problem The problem I am considering is the following: Given: A (multi-)graph $G = (V, E)$ in which each edge is colored either red or blue, and two integers $r$ and $b$. Determine: Whether a perfect ...
1
vote
1answer
44 views

A corollary from Sperner's Theorem

How can I conclude this fact: If $\mathcal{F}$ is an antichain consisting of sets of size at most $k \leq n/2$, then $|\mathcal{F}|\leq {n\choose k}$ from the Sperner's Theorem: Let $\mathcal{F}$ be ...
0
votes
0answers
13 views

Minimum weight maximum cardinality non-bipartite matching for Python

I am looking for a Python library to find a max cardinality matching on a non-bipartite graph that minimises the sum of edge weights. I have tried NetworkX: https://networkx.org/documentation/stable/...
3
votes
1answer
61 views

Can every d-regular graph be decomposed into at most d+1 matchings?

If so, how would you prove it? This arose in a circuit context: a paper I was reading considers applying a two-bit gate to every pair of vertices that share an edge in some arbitrary d-regular graph, ...
4
votes
1answer
60 views

A 3-regular graph with at most 2 bridges has 1 factor.

I want to show that every 3-regular graph with at most two bridges, has 1-factor. And I want to use Tutte theorem that says: A graph G has 1-factor iff for every proper subset $S$ of $V(G)$ we have $...
2
votes
2answers
67 views

An optimal non-bipartite matching (Python implementation)

I have a set $S = \{s_1, \cdots, s_n \}$ ($n$ is even), and the $n\times n$ matrix $M = \{ d_{ij}\}$, where $d_{ij}$ is a distance between $s_i$ and $s_j$. I wish to find a non-bipartite matching on $...
2
votes
1answer
42 views

Undirected connected claw-free graph with even number of vertices implies existing perfect matching

I need to prove that graph $G$ which: is undirected is connected has an even number of vertices is claw-free (does not contain $K_{1,3}$ as an induced subgraph) implies $G$ has a perfect matching. I'...
2
votes
1answer
34 views

finding disjoint subsets of a family of k-sets

This problem is from Combinatorial Mathematics by Douglas West, problem 6.1.32: Let $A_1,A_2,\cdots A_m$ be $k$-sets such that each element of the union lies in at most $l$ sets. Prove that there ...
1
vote
0answers
42 views

Number of distinct perfect matching in a d-regular graph.

I have a claim that every d-regular bipartite graph has at least d! distinct perfect matchings. Is this claim is true? if yes then can somebody tell me the proof? Actually there is a problem that ask ...
2
votes
1answer
48 views

Deficient version of Halls Theorem to Show a Bipartite Graph has a matching

I am not quite sure how to tackle this question. I understand that using the deficient version it suffices to reduce the graph $G$ to a graph $G'$ by adding suitable vertices to each vertex class ...
1
vote
1answer
29 views

vertex covering number

I want to find $\alpha(G)$ that is vertex independence number(maximum number of vertices, no two of which are adjacent) and $\beta(G)$ that is edge covering number(minimum number of vertices that ...
3
votes
0answers
90 views

Hall's marriage theorem: sufficiency proof by contraposition

EDIT: There is a flaw in the previous proof, so I used a different approach. I believe now that it is correct. I have an alternative proof of Hall's marriage theorem, and would like to know whether it ...
0
votes
1answer
35 views

Number of perfect matchings in a complete bipartite graph without any edge repetition

I need the number of perfect matchings in a complete bipartite graph, such that no edge is repeated in other perfect matchings. For example consider a bipartite graph with $n=6$, the complete graph ...
1
vote
1answer
40 views

Maximum matching and minimum vertex cover problem, that seemingly violates Koning's lemma

We have the following bi-adjacency matrix of a bipartite graph: \begin{bmatrix}0&0&1&0&1&0\\1&1&0&1&0&1\\0&0&1&0&1&0\\1&1&1&1&...
2
votes
1answer
80 views

Extremal combinatorics

I am trying to prove the following claim, or at least find something related to it. Assume we have a complete bipartite graph with partitions of size $n, m$. We then have a family of matchings of this ...
0
votes
1answer
48 views

The existence of a common set of representatives deduced from graph theory

Hey I'm stuck at the following problem: Let $k,n$ be positive integers and let $X$ be a set of size $kn$. Use a result about graphs from the lecture to prove that for any two partitions (disjoint ...
0
votes
1answer
28 views

Assignment problem with multiple assignments and constraints

I have a bi-partite graph $G=(P \cup C,E)$ where $P$ contains 'parents', these parents are in pairs, but count as one vertex, and are to be matched with a number of children in the set $C$. I want to ...
2
votes
1answer
53 views

Maximum matching contains one edge that contains a leaf of a tree.

I wanted to show the following using Berges Lemma (https://en.wikipedia.org/wiki/Berge%27s_lemma): Let $T=(V,E)$ be a tree with $n:=|V| \geq 3$. Then any maximum matching $M_{max}$ contains at least ...
3
votes
1answer
119 views

There exists matching of size at least $E(G)/\Delta(G)$ for bipartite graph.

To show: There exists a matching of size at least $|E(G)|/\Delta(G)$ for any bipartite graph $G$. ($\Delta(G)$ is the maximum degree) Approach. : If say $|E(G)|/\Delta(G)= k+\epsilon, 0\le\epsilon<...
1
vote
2answers
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 ...
3
votes
1answer
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$ ...
2
votes
1answer
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). ...
4
votes
1answer
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$ ...
0
votes
1answer
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 ...
1
vote
2answers
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$ ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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$...
-1
votes
1answer
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), ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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-...
1
vote
1answer
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 ...
0
votes
2answers
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/...
0
votes
0answers
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 ...
3
votes
2answers
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 ...
0
votes
1answer
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 ...
2
votes
1answer
62 views

Partition the edges of a bipartite graph into perfect $b$-matchings

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 =...
0
votes
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 ...
2
votes
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 ...
0
votes
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 ...
1
vote
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 ...
0
votes
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, ...
0
votes
0answers
38 views

Non-asymptotic probability of having a perfect matching in a bipartite graph with a fixed number of edges

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$, ...
2
votes
1answer
162 views

Prove the pseudo k-regular bipartite graphs has a perfect matching

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

1
2 3 4 5
9