Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
Sergei Ivanov's user avatar
5 votes
1 answer
302 views

Reference sought for Conway's observation on stable matchings

Looking for a reference on the observation that the set of stable matchings form a distributive lattice. This is attributed to Conway by Knuth in "Marriages Stables" but I would like an explicit ...
user16317's user avatar
3 votes
1 answer
107 views

Probabilistic many-to-one matching

Let $p<1$ be a constant. Consider two sets $A,B$ with $n$ and $nf(n)$ vertices, respectively, where $f(n)$ is an integer. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears ...
Alexi's user avatar
  • 239
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
2 answers
353 views

Matching with probabilistic edges

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 ...
Alexi's user avatar
  • 239
2 votes
0 answers
78 views

Maximum cardinality general factor of a graph

Given a graph $G=(V,E)$ and a set of integers $B(v)$ associated to each vertex, a general factor of $G$ is a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph $(V, ...
George Octavian Rabanca's user avatar
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
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