All Questions
Tagged with matching-theory elementary-set-theory
5
questions
0
votes
2
answers
37
views
Maximum number of ways to select $2$ element disjoint subsets from an $n$ set
Suppose that we have the set $\{ 1, 2, \cdots, n\}$. I seek the number of ways to select $2$ element subsets, $s_1, s_2, \cdots, s_k$, such that the intersection of any $2$ of these subsets is the ...
- 140
1
vote
1
answer
31
views
How to group 2-member subsets so that in a group no two subsets have a common elements?
For a set $A$ with $n$ members, so that $A = \{1,2,3,...,n\}$. How can I group all subsets with two members, so that the intersection between any two subsets in the same group is an empty set and no ...
1
vote
1
answer
276
views
Proof of a weaker version of Hall's Marriage Theorem
Thm: Let $G=(V_1,V_2,E)$ be a bipartite graph s.t. (*) $|V_1|=|V_2|$, so:
There exists a perfect matching in G $\Leftrightarrow \forall S\subseteq V_1$,
$|N(S)|\ge|S|$
In this notation, $N(S)$ ...
- 332
9
votes
1
answer
6k
views
What does 2 to the power x mean in set theory
In a mathematics assignments i encounter the following statement:
We have a finite collection of combinatorial objects $S \subseteq 2^x$ (For example matchings or spanning trees)
What does this ...
- 369
3
votes
1
answer
1k
views
Hall's marriage theorem explanation
I stumbled upon this page in Wikipedia about Hall's marriage theorem:
The standard example of an application of the marriage theorem is to imagine two groups; one of n men, and one of n women. For ...
- 1,093