Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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
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