Skip to main content

All Questions

Filter by
Sorted by
Tagged with
1 vote
0 answers
149 views

Inequalities in the classic proof of perfect matching in Erdős–Rényi graph

I am checking the classic paper by Erdős and Rényi, "On the existence of a factor of degree one of a connected random graph" with the link here. I am curious about the computation of the ...
Nicole's user avatar
  • 97
4 votes
0 answers
113 views

Find necessary & sufficient conditions for two families of sets to have $m$ pairwise disjoint common partial transversals of given sizes

Let $S$ be a finite set, $I$ a finite index set, $\mathcal A=(A_i:i\in I)$ and $\mathcal B=(B_i:i\in I)$ families of subsets of $S$. For $J\subseteq I$, let $A(J)$ denote $\bigcup_{j\in J} A_j$. A ...
Tri's user avatar
  • 1,644
3 votes
1 answer
140 views

Generalizations of a theorem of Edmonds/Tutte on existence of a perfect matching in a graphs

It is well known that for a bipartite graph $G$ with bi-adjacency matrix $A$, then $\det A \neq 0$ (as a polynomial) iff $G$ has a perfect matching (there is a similar result for general graphs with ...
Agile_Eagle's user avatar
2 votes
0 answers
163 views

Generalizing Hall's marriage theorem to non-perfect matchings

Let $G = (X, Y, E)$ be bipartite graph such that $|X|=|Y|=n$. A matching $M \subseteq E$ is a subset of disjoint edges (i.e., there does not exist a pair of edges $(x, y) \in M$ and $(x', y') \in M$ ...
errorist's user avatar
  • 121
0 votes
1 answer
238 views

Graph alignment by considering node and edge weights

I have two complete weighted graphs, with the same number of nodes and edges. Each node has a multi-dimensional vector, which represents its features. Edge weights are float numbers between 0 to 1. I'...
Danial's user avatar
  • 101
1 vote
0 answers
183 views

Generalizing Hall's marriage theorem

(This question was earlier posted on stackexchange: Generalizing Hall's marriage theorem. As it received no answers there, I am reposting it here for more attention.) Fix positive integers $m,n,k$ ...
MathManiac's user avatar
3 votes
0 answers
231 views

Counting matchings and perfect matchings

A matching in a graph is a subset of the edges such that no two edges share a vertex. A perfect matching is a matching where every vertex is part of exactly one edge in the matching. Counting the ...
Per Alexandersson's user avatar
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 ...
Per Alexandersson's user avatar
1 vote
0 answers
128 views

Hopcroft–Karp Algorithm for a dynamic graph

As so you all know, we have Hopcroft–Karp Algorithm for maximum matching between two sides in a bipartite graph. It runs in $O(\sqrt{V} \times E)$ where $V$ is the vertex set and $E$ is the edges set. ...
linuxbeginner's user avatar
0 votes
0 answers
65 views

Validity of an argument for an implication of NP-Completeness

Fedor Petrov has posed a notorious problem regarding the existence of a matching in this question: Resolution of multiple edges As I see it the setting is a constrained bipartite matching and thus, ...
Manfred Weis's user avatar
  • 13.2k
0 votes
0 answers
110 views

Bound on the number of maximum matchings in a graph

It is known that the number of perfect matchings in a graph is bounded above by the integer part of the square root of the permanent of its adjacency matrix. But, suppose I take the square root of the ...
vidyarthi's user avatar
  • 2,089
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 $\...
Xin Zhang's user avatar
  • 1,190
3 votes
1 answer
376 views

Generalization of Marshall Hall's Theorem to non-simple bipartite graphs

Lemma 8.6.5 of the book "Matching Theory" by Lovász and Plummer states the following lemma: Lemma: Let $G$ be a simple bipartite graph with bipartition $(A,B)$, and assume that each point ...
Sanket Biswas's user avatar
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 ...
Xin Zhang's user avatar
  • 1,190
2 votes
0 answers
44 views

Which edges to delete from cubic graphs to get good cycle covers?

Let $G\left(V,E\subset V\times V,\omega: V\supset \lbrace u,v\rbrace\mapsto w_{uv}\in\mathbb{R}\right);\ \left|e_{uv}\right|:=\omega_{uv}\quad$ be a cubic symmetric graph that contains a vertex-...
Manfred Weis's user avatar
  • 13.2k
1 vote
0 answers
61 views

Algorithm for minimum weight matching with "tree topology"

Given a finite graph $G(V,E)$ with undirected and weighted edges, whose set of vertices $V$ is partitioned into a collection $\mathfrak{P}=\lbrace V_1,\,\dots,\,V_k\rbrace$ of non-empty and pairwise ...
Manfred Weis's user avatar
  • 13.2k
4 votes
1 answer
292 views

Assignment problem with priorities and scores

I have run into a real problem that is actually a sort of assignment problem. I am describing it here because I am interested in knowing whether this problem already has a name (and whether there is ...
Vicent's user avatar
  • 153
2 votes
0 answers
77 views

Counting matchings in middle levels of the Boolean lattice

Let $k$ be a nonnegative integer and consider $C_k$, the set of all subsets $A$ of size $k$ in $[2k+1]=\{1,2,\ldots,2k+1\}$ as well as $C_{k+1}$, the set of all subsets $B$ of size $k+1$ in $[2k+1]$. ...
Abdelmalek Abdesselam's user avatar
1 vote
0 answers
123 views

Number of maximum matchings in bipartite graphs of positive surplus

Let $G$ be a simple bipartite graph with left part $L(G)$ and right part $R(G)$. For $S \subseteq L(G)$, denote $N(S)$ the set of neighbours of vertices of $S$. Define the surplus $s(G)$ as $\min_{S \...
Mikhail Tikhomirov's user avatar
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 $\...
Louis D's user avatar
  • 1,701
2 votes
0 answers
314 views

Perfect matching in hypergraphs: tripartite, regular and unbalanced

In a balanced bipartite graph - where both sides have the same size - a sufficient condition for the existence of a perfect matching is that the graph is regular - all vertices have the same degree. ...
Erel Segal-Halevi's user avatar
2 votes
0 answers
141 views

From fractional matching to integral matching in tripartite hypergraphs

Let $G = (X\cup Y, E)$ by a bipartite graph with $n = |X|\leq |Y|$. A fractional matching is a function assigning a non-negative weight to every edge in $E$, such that the sum of weights near each ...
Erel Segal-Halevi'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
1 vote
1 answer
376 views

Expanding Hall's theorem [closed]

I'm trying to get a "feel" about Hall's theorem and try to expand it for one to many matching. So my question is: Given a bipartite graph, what would be a neccessary and sufficient condition for that ...
Blur's user avatar
  • 19
2 votes
2 answers
223 views

Number of subgraphs with matching of size $n$ for a complete bipartite graph

Say we have a $K_{n,n}$ bipartite graph (i.e. a complete bipartite graph with $n$ nodes on each side). We induce a subgraph by deleting some subset of edges. There are $2^{n^2}$ possible subgraphs. ...
TPaul's user avatar
  • 41
2 votes
1 answer
55 views

maximum weighted matching with weights being sets

Given a set $S$ and a bipartite graph $G$, each edge $v\in E(G)$ covers a subset $S_v$ of $S$. My problem is to find a matching maximizing the number of covered elements, i.e., denote $V$ the set of ...
lchen's user avatar
  • 367
1 vote
2 answers
163 views

Clutters with no maximum-size matchings

A clutter is a pair $C=(V,E)$ where $V\neq\emptyset$ is a set, and $E\subseteq {\cal P}(V)$ such that no member of $E$ is included in another member of $E$. A matching in $C$ is a collection of ...
Dominic van der Zypen's user avatar
0 votes
1 answer
150 views

Combining three matchings to form a maximal matching

Consider a regular tripartite graph $G$ with maximum degree $\Delta\ge3$ and parts $A,B,C$. Now, the induced subgraphs $A\cup B, B\cup C$ and $A\cup C$ are all bipartite. Now, is there a way to ...
vidyarthi's user avatar
  • 2,089
0 votes
1 answer
357 views

A vertex transitive graph has a near perfect/ matching missing an independent set of vertices

Consider a power of cycle graph $C_n^k\,\,,\frac{n}{2}>k\ge2$, represented as a Cayley graph with generating set $\{1,2,\ldots, k,n-k,\ldots,n-1\}$ on the Group $\mathbb{Z}_n$. Supposing I remove ...
vidyarthi's user avatar
  • 2,089
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$ ...
vidyarthi's user avatar
  • 2,089
2 votes
1 answer
338 views

Number of distinct perfect matchings/near perfect matchings in an induced subgraph

Consider a Class 1 graph with degree $\Delta\ge3$ and the induced subgraph formed by deleting a set of independent vertices of cardinality $\left\lfloor\frac{n}{\Delta}\right\rfloor$. Then, what is ...
vidyarthi's user avatar
  • 2,089
0 votes
1 answer
141 views

All even order graphs with $\Delta\ge\frac{n}{2}$ is Class 1

Are all even order graphs with maximum degree $\ge\frac{|V(G)|}{2}$ Class 1(edge-colorable(chromatic index) with $\delta(G)$ colors)? Here, $|V(G)|$ detnotes the number of vertices in the graph. I ...
vidyarthi's user avatar
  • 2,089
1 vote
1 answer
152 views

Hall theorem with non-saturating matching

Hall's marriage theorem states that given a bipartite graph $G=(X+Y,E)$, if there is no $X$-saturating matching, there there exists $W\subseteq X$ such that $|W|>|N_G(W)|$. Is the following ...
user137692's user avatar
2 votes
2 answers
149 views

Graphs in which all maximal matchings intersect

Let $G=(V,E)$ be a simple, undirected graph. A matching is a set $M\subseteq E$ consisting of pairwise disjoint edges. We say $M$ is maximal if it is maximal amongst all matchings in $G$ with respect ...
Dominic van der Zypen's user avatar
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$...
Dominic van der Zypen's user avatar
1 vote
0 answers
81 views

Matchings in infinite, not necessarily bipartite, graphs

Aharoni, Nash-Williams, and Shelah have extended the famous marriage theorem for finite bipartite graphs due to Hall to arbitrary graphs. Is there a similar generalization of Tutte's theorem on ...
Dominic van der Zypen's user avatar
0 votes
1 answer
134 views

A weaker version of Dirac's theorem

This is related to Dirac's theorem. For any finite, simple, undirected graph $G=(V,E)$ let $\delta(G)$ denote the minimal degree of all vertices. Are there positive integers $n,c\in\mathbb{N}$ with ...
Dominic van der Zypen's user avatar
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 ...
Mario Krenn's user avatar
4 votes
1 answer
433 views

Bijection between noncrossing matchings on $2b$ points and Standard Young Tableaux of size $2 \times b$

I'm currently reading a review article called Dynamical Algebraic Combinatorics: Promotion, Rowmotion, and Resonance by Jessica Striker. In this article, Striker writes that there is a ''nice'' ...
Joakim Uhlin's user avatar
3 votes
2 answers
340 views

A direct proof that every $r$-colored complete graph on $n=(r+1)m-(r-1)$ vertices has a monochromatic matching of size $m$?

Cockayne and Lorimer ("The Ramsey number for stripes" 1975) prove that in every $r$-colored complete graph on $n=\sum_{i=1}^rm_i+m_1-(r-1)$ vertices, where $m_1\geq \dots\geq m_r\geq 1$, has a ...
Louis D's user avatar
  • 1,701
3 votes
0 answers
119 views

Forcing $A_1x,\dotsc,A_Kx$ to lie in a proper subspace

(This is a re-worked version of a question I asked several days ago.) Let $J$ be the all-one matrix with $m$ rows and $n$ columns, and suppose that $J=A_1+\dotsb+A_K$ is a decomposition of $J$ into a ...
Seva's user avatar
  • 23k
1 vote
1 answer
79 views

Hall type theorem for saturations of subsets of bipartite graphs

Let $X,Y$ be a bipartite graph and $X',Y'$ be two subsets of the vertices. Is there a Hall type theorem for the existence of matchings saturating both subsets simmultaneously? Clearly necessary ...
Gorka's user avatar
  • 1,835
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 ...
Mostafa - Free Palestine's user avatar
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 ...
Turbo's user avatar
  • 13.9k
8 votes
2 answers
760 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.9k
2 votes
0 answers
64 views

Minimum size of genus $g$ bipartite graphs with $2^n$ perfect matchings

Given $n\in\Bbb Z_{\geq0}$ let $2T_{n,g}$ be size of smallest number of vertices of genus $g$ bipartite graph with $T_{n,g}$ vertices of each color such that number of perfect matchings is $2^n$. Eg: ...
Turbo's user avatar
  • 13.9k
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 ...
user177523's user avatar
7 votes
2 answers
186 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
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^...
Max Alekseyev's user avatar
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 ...
Ben Barber's user avatar
  • 4,589