Skip to main content

Questions tagged [matching-theory]

For questions about matchings in graphs.

Filter by
Sorted by
Tagged with
0 votes
3 answers
67 views

An Interesting Optimization Problem With Permutation Function [closed]

Define a permutation mapping $\sigma(\cdot):\mathcal{V}\longmapsto\mathcal{V}$ with $\mathcal{V}=\{1,2,\dots,N\}$, which can transform a permutation consisting of $1,2,\dots,N$ into another ...
Jiayu Zou's user avatar
0 votes
0 answers
34 views

How DTW decides which element to take next?

I'm currently working on an DTW algorithm implementation and do have a question about how DTW works if the next steps are the same or if the correct next step is the actually not less-cost one. I do ...
Dixit Dominus's user avatar
0 votes
1 answer
48 views

A proof for the statement: The 3-Dimensional matching problem is NP-Complete

The 3-Dimensional Matching Problem is relatively well known in the fields of discrete mathematics and computer science. The problem consists of determining whether a tripartite $3$-hypergraph with ...
lafinur's user avatar
  • 3,432
0 votes
0 answers
8 views

Bipartite Matching With Distant Constraints

I am investigating the complexity of the following problem. Let a complete bipartite graph $G = (V \cup V', E: V \times V')$ with |V| < |V'|, where the nodes have weights $w: V \cup V' \to \mathbb{...
Dom's user avatar
  • 19
2 votes
1 answer
41 views

If a graph is 1-factoreable, then it has no cut vertex.

I'm trying to prove the statement: if a graph $G$ is 1-factorable, then $G$ has no cut vertex. Assuming $G$ has a cut vertex, let be $v\in V(G)$ a cut vertex of $G$. Then the connected components of $...
Fabrizio G's user avatar
  • 2,107
2 votes
0 answers
16 views

Matching number of a graph is equal to the independence number of its line graph.

Let $\alpha'(G)$ the matching number of a graph $G$, $L(G)$ its line graph and $\alpha(L(G))$ the stability number of its line graph. I need to prove that $\alpha'(G)=\alpha(L(G))$. Let $M$ be a ...
Fabrizio G's user avatar
  • 2,107
1 vote
0 answers
18 views

How sensitive are maximum-size matchings to edge deletion in random graphs?

My question concerns the sensitivity of maximum-size matchings (and more generally maximum-size $k$-cycle collections) to deletion of an edge in the graph. Given a graph $G$, let a $k$-cycle be a ...
user1326274's user avatar
0 votes
1 answer
32 views

Understanding proof of Hall's graph theorem

I am struggling with understanding proof of Halls theorem. Theorem: Let $G=(V_1\cup V_2,E)$ be a bipartite graph and for each $U\subseteq V_1$ let $$N_{G}(U)=\{v\in V_2\ :\ \exists u\in U\text{ such ...
Jane Doe's user avatar
  • 115
1 vote
1 answer
39 views

Problem in proving that every tree has at most one perfect matching.

I would like to prove that every tree has at most one perfect matching. I approached it in the same way as described here: Perfect matching in a tree. However, I don't understand the concluding ...
user avatar
1 vote
1 answer
43 views

A matching problem with $N$ men, $N$ women and $N$ houses [closed]

Consider a matching problem with $N$ men, $N$ women and $N$ houses where each man has to be paired with exactly $1$ woman and then each couple has to be allotted to $1$ house. Now let's consider all $...
vervenumen's user avatar
1 vote
0 answers
32 views

Parity of number of crossings of chord diagram

I would like to define the following sign for a given perfect matching $P$ of set of $2n$ elements: $$\sigma_P=(-1)^k$$ where $k$ is the number of crossings in the chord diagram associated to $P$. Is ...
hopeillstickaround's user avatar
0 votes
1 answer
39 views

Perfect matching on bipartite graph with $n(n-1)$ number of edges

Suppose $G$ is a $(X,Y)$ graph with $|X| = |Y| = n \geq 1$. Prove that if $|A(G)| > n(n-1)$ then $G$ has a perfect matching. I'm looking for a hint on showing that $|N(S)| \geq |S|, \forall S \...
Victor Feitosa's user avatar
0 votes
0 answers
37 views

Equivalent statement to Hall's theorem [duplicate]

I am trying to prove that a bipartite graph $G$ on $(X, Y)$, contains a matching perfect to $X$ if and only if $$ |X\setminus N(T)| \leq |Y\setminus T| \; \; \forall \; T \subseteq Y $$ Forward ...
mNugget's user avatar
  • 511
3 votes
1 answer
88 views

Why would solving #MATCHING(bipartite) problem efficiently solve #MATCHING efficiently?

Im gathering information about the matching counting problem for a graph $G$ (#MATCHING($G$)). I found that for the specific case of $G$ being a bipartite graph then the problem has a simple (not ...
Mikel Solaguren's user avatar
1 vote
1 answer
37 views

Maximum number of edges such that $\nu(G) < \frac{n}{2}$

Given an even integer $n$. I want to find the largest number of edges in a $n$-vertex graph such that the matching number is strictly less than $\frac{n}{2}$. I believe that the maximum is obtained by ...
mNugget's user avatar
  • 511
1 vote
0 answers
76 views

Polynomial Kernel For Minimum Maximal Matching Problem

Let $G$ be a graph, and $k$ be some non-negative integer. The goal is to decide whether there exists a maximal matching in $G$ on at most $k$ edges. This problem is also asked in https://www.mimuw.edu....
Yavuz Bozkurt's user avatar
0 votes
0 answers
19 views

Existence of high-weight perfect matching

I have the following problem from Korte and Vygen: Let $G$ be a $k$-regular and $(k-1)$-edge-connected graph with an even number of vertices, and let $c\colon E(G) \to \mathbb R_+$ be a weight ...
Nico Konrad's user avatar
0 votes
0 answers
21 views

One to one mapping that maximize the minimum absolute difference

Given two sequences $a_0 \leq a_1 \leq \ldots \leq a_{n-1}$ and $b_0 \leq b_1 \leq \ldots \leq b_{n-1}$. We want to find a one-to-one mapping $\pi:[n-1] \rightarrow [n-1]$ such that $$ \max \min_{i} |...
polar_bear_cheese's user avatar
0 votes
2 answers
42 views

Determining whether a housing allocation is in the Core

I have recently been thinking about the housing allocation problem where we have a set of players and a set of houses where players have strict preferences over the houses. I am aware of the Top ...
Finn's user avatar
  • 21
0 votes
0 answers
25 views

Finding Nash equilibrium in a basic matching market

I've been working on simulating a market with small numbers of mutually-exclusive sellers and buyers, where each individual can only ever enter one transaction. In pursuing this, I've been trying to ...
Brandon Lee's user avatar
0 votes
0 answers
45 views

Generate a schedule for doubles with rotating partners

So I want to set up a schedule of double matches: player A and B vs player C and D. I have a few constraints for setting it up: Each player plays exactly 4 times The scheme should be as fair as ...
T C Molenaar's user avatar
10 votes
1 answer
179 views

(Hall's Theorem) Existence of two subfamilies of sets containing the same elements

I came across the following claim in a textbook on combinatorics [1]. Claim (Lindström, Tverberg): Let $A_1, . . . , A_m \subseteq [n]$ be non-empty with $m > n$. There are non-empty, disjoint $I, ...
xyz's user avatar
  • 103
0 votes
1 answer
29 views

Special form of 3 vertex-connectedness for Graphs with every edge contained in a perfect matching

I am currently struggling with the following problem: Given a simple, connected Graph $G = (V,E)$ such that every edge is contained in a perfect matching of $G$. Show that for each edge $e \in E$ (of ...
Raoul Luqué's user avatar
1 vote
0 answers
40 views

Can Hall's Marriage Theorem be reduced to the $d$-regular case?

The version of Hall's Marriage Theorem I'd like to consider is the following: Theorem Let $G$ be a finite bipartite graph with bipartition $\{X,Y\}$ and edge set $E$, so that we can view $E$ as a ...
diracdeltafunk's user avatar
1 vote
1 answer
39 views

Specific way to prove that a cubic graph with a cut edge isn't $3$-edge-colorable.

The statement "If a simple graph $G$ is cubic and has a cut edge, then $\chi'(G) =4$" has a couple of proofs on this site, namely here and here. However, I was interested in a specific way ...
Robert Lee's user avatar
  • 7,273
0 votes
0 answers
75 views

The Size Relationship Between a Given Matching and the Maximum Matching in a Graph Without Short Augmenting Paths

Let $G = (V, E)$ be a graph, and let $M \subseteq E$ be a matching such that there is no augmenting path of length at most 3 for $M$. Prove that $|M| \geq \frac{2}{3} |M^*|,$ where $M^*$ is the ...
dani's user avatar
  • 59
5 votes
1 answer
79 views

2-factors with many cycles

Petersen's theorem states that every cubic, bridgeless graph contains a perfect matching. Let $G$ be a cubic bridgeless graph, and let $M$ be a perfect matching. Clearly $E(G)-M$ is a 2-factor of $G$ (...
Vinicius dos Santos's user avatar
3 votes
1 answer
62 views

Greedy lemma Problem for matching spears to soldiers

The problem has $n$ spears and $n$ soldiers. Spears and soldiers have heights. We want to assign spears to soldiers such that the total height difference of spears and their assigned soldiers is ...
Yavuz Bozkurt's user avatar
2 votes
0 answers
89 views

Finding a perfect matching that include $e_{1}$ and exclude $e_{2}$ in a connected bipartite graph

Let $G$ be a $k$-regular bipartite graph with $k\ge3$, and $e_{1},e_{2}$ be edges of $G$. Show that if $G-\{e_{1},e_{2}\}$ is connected, then there exist a perfect matching in $G$ that includes $e_{1}$...
Kevin's user avatar
  • 734
2 votes
1 answer
51 views

If the bridges of a $3$-regular graph $G$ lie on a single path then $G$ has a $1$-Factor (perfect matching)

If the bridges of a $3$-regular graph $G$ lie on a single path then $G$ has a $1$-Factor (perfect matching) I've proved that a $3$-regular graph with at most two bridges has a perfect matching ($1$-...
H4z3's user avatar
  • 791
1 vote
1 answer
45 views

Find bipartite graph with properties [closed]

Problem: Find a bipartite graph such that a) Each part of the graph has 15 vertices b) Each vertex has a degree of at least 7 c) There is no matching of size 15. How can I construct such graph?
popcorn's user avatar
  • 311
0 votes
0 answers
64 views

Counting the number of "permitted" pairings between two sets

Suppose I have two sets $A$ and $B$. We will be considering pairs of elements $(a,b)$, where $a\in A$ and $b \in B$. I have a function $f(a,b) \rightarrow \{0,1\}$, i.e. for each pair I can say ...
Ben Farmer's user avatar
1 vote
2 answers
90 views

Graph theory (Perfect matchings)

In an undirected graph with 2024 vertices (not necessarily bipartite) between any three vertices have at least two edges. Prove that the graph contains a perfect matching (from 1012 edges). To be ...
Jacobs Monarch's user avatar
0 votes
0 answers
28 views

Find correspondences between a set of ellipsoids and a set of ellipses

I am having the following problem. Imagine that I have set of quadrics, i.e. Ellipsoids in the 3d space and a set of conics, i.e. ellipses on an image plane. For each of the sets I have all the ...
ttsesm's user avatar
  • 101
1 vote
1 answer
110 views

Prove that G-x-y has a perfect matching iff x and y are on opposite sides where G is Hamiltonian

Question: Suppose G is Hamiltonian bipartite graph with $ x , y \in V(G) $. Prove that $G-x-y$ has a perfect matching if and only if $x$ and $y$ are on the opposite sides of the graph. Proof: $\...
i_hate_pure_math's user avatar
2 votes
0 answers
51 views

Prove that $P_{\text {match }}(G) \cap\left\{x: 1^T x=k\right\}$ is the convex hull of all matchings in $G$ of size exactly $k$.

Problem: Prove that $P_{\text{match}}(G) \cap\left\{x: 1^T x=k\right\}$ is the convex hull of all matchings in $G$ of size exactly $k$. My attempt: Firstly, we prove that $$\text{conv}\left\{\chi_M: M ...
Tung Nguyen's user avatar
  • 1,238
1 vote
1 answer
108 views

Vertices of Matchings in bipartite Graph are Matroid

Let $G=(V,E)$ be a bipartite graph with $V=A \cup B$ (disjoint) and $\mathcal{F}=\{V(N) \cap B\ |\ N\ is \ a\ matching\ in\ G\}$ . Now I have to prove that $(B,\mathcal{F})$ is a matroid. The first ...
Norn0556's user avatar
2 votes
1 answer
42 views

Stable matching theorem for non-equal sides

Given a bipartite graph with two sides $A$ and $B$, for a vertex $v$, there is a linear order on $N(v)$ (a preference list). The stable matching theorem says that if $|A|=|B|$, then there exists a ...
Connor's user avatar
  • 2,075
2 votes
1 answer
100 views

Maximise $\sum_{x,y\in S} GCD(x,y)$ where $S = \{1,2,\ldots, 100\}$ and each number appears once in the sum

Question: One day Anindya and his friend Faria cooperated to play a fun game. They played to maximize the sum of points they gained throughout the game. Let $S = \{1,2,\ldots, 100\}$. There are $50$ ...
user avatar
2 votes
1 answer
89 views

G a k-connected bipartite graph with bipartition $(A, B)$ such that $|A|$, $|B| \geq 2k$. Show that $G$ contains a matching of size $2k$.

Let $k \geq 1$ be an integer, and let G be a k-connected bipartite graph with bipartition $(A, B)$ such that $|A|$, $|B| \geq 2k$. Show that $G$ contains a matching of size $2k$. I have managed to ...
The Math Hermit's user avatar
2 votes
1 answer
102 views

Multiset Matching

Suppose we have two multisets of positive integers, $A$ and $B$, where the sum of the elements (counted with multiplicity) of the two multisets is the same. Starting from $A$, we would like to arrive ...
SpringLandMid's user avatar
0 votes
1 answer
60 views

Notion of neighborhood in Hall's Theorem

In Hall's Theorem, should we refer to $N(S)$ as $\bigcup_{x \in S}N(x)$ or as $\bigcup_{x \in S}N(x) - S$? I guess that the second definition is the one used in the theorem.
J P's user avatar
  • 893
5 votes
1 answer
92 views

In a simple graph with $2m$ vertices and a unique perfect matching, prove that $|E(G)|$ is bounded by $m^2$.

I have been trying to solve this question, it was already asked but the response seems to have some issues. The accepted answer implies that if a graph has a cycle of length 4, this implies that it ...
mr. man's user avatar
  • 115
0 votes
1 answer
26 views

Is the following claim on saturated matching on bipartite graphs with constrained degree true?

Claim: A bipartite graph $G(X, Y)$ with all vertices in $X$ having degree less than or equal to 2 has an X saturating matching if and only if for any connected component $G'(X', Y')$ in $G$, $|X'| \...
N.S.JOHN's user avatar
  • 1,549
2 votes
1 answer
50 views

Understanding the proof perfect matching polytope

Theorem. Let $M$ and $N$ be perfect matchings in a graph $G=(V, E)$. Then $\chi^M$ and $\chi^N$ are adjacent vertices of the perfect matching polytope if and only if $M \triangle N$ is a circuit. ...
ohana's user avatar
  • 873
1 vote
1 answer
62 views

Understanding the proof of Konig edge-colouring theorem

Theorem: (König's edge-colouring theorem). For any bipartite graph $G=(V, E)$, $$ \chi(G)=\Delta(G) . $$ That is, the edge-colouring number of a bipartite graph is equal to its maximum degree. Proof. ...
ohana's user avatar
  • 873
2 votes
0 answers
115 views

Prove that symmetric difference of two perfect matchings is union of disjoint even cycles

Problem: Let $M$ and $N$ be perfect matchings of a finite graph $G$. Prove that their symmetric difference is a union of disjoint even cycles. My attempt: Firstly, if $M = N$, we are done. Now, let us ...
Tung Nguyen's user avatar
  • 1,238
0 votes
0 answers
20 views

Algorithm for k sized matching in a complet weighted graph

as the Title suggest im looking for an algorithm for k sized matching in a weighted complet graph. Any further literature is welcome.
Hoppi's user avatar
  • 1
0 votes
0 answers
55 views

Is there a way to do the Hungarian algorithm in reverse?

The Hungarian algorithm is used to find the optimal choices for a given 'cost matrix' e.g. going from the output of the Hungarian algorithm ...
Machai's user avatar
  • 1
1 vote
0 answers
63 views

What is the connection between the deficiency in bipartite graphs and the connected components? (Matching Theory, Lovasz, 3.3.13)

I am working my way through "Matching Theory" by Lovasz and Plummer. Lemma 3.3.13 is where I am stuck. Let $G$ be a graph such that $C(G)=\emptyset$ and let $X$ and $Y$ be barriers such that ...
pkay's user avatar
  • 11

1
2 3 4 5
12