Having trouble applying Hall's Theorem

  • Thread starter junho
  • Start date
  • Tags
    Theorem
In summary: The last time I took any university level math was 5 years ago. I'm just going back to school now for some upper level math courses to complete a minor in Math.
  • #1
junho
5
0
1. Let k>0 and let A1,A2,...,An be a collection of k-subsets of finite set X such that every element of X appears in exactly k sets in the collection. Prove that |X| = n



2. Teacher provided us with the following hints:
-- Use a variation of Hall's Theorem.



3. I have no clue how to approach this problem. I don't even understand how proving |X|=n implies anything?
 
Last edited:
Physics news on Phys.org
  • #2
?? |X|= n is the conclusion you want to prove! Why should it imply anything?

"k- subsets" here means subsets of X containing exactly k members? The "overlapping" is the problem here so imaging "painting" the members of each Ai a different color! In other words, imagine that these are all distinct items. Since there are n sets, each containing k items, how many items are there altogether.

But we are told that each item in X appears in exactly k sets. In other words each item in X is counted k times in the formula above.
 
  • #3
HallsofIvy said:
?? |X|= n is the conclusion you want to prove! Why should it imply anything?

By that, I meant that I don't know understand what solving for |X| = n proves and therefore I can't figure out the reasoning and logic to bring me to that solution.

But thanks for the tips! I'll see if I can use it to help me figure it all out.
 
  • #4
junho said:
By that, I meant that I don't know understand what solving for |X| = n proves and therefore I can't figure out the reasoning and logic to bring me to that solution.

But thanks for the tips! I'll see if I can use it to help me figure it all out.
? It proves just what it says: that X contains n elements!

I can't think what else you could mean.
 
  • #5
HallsofIvy said:
? It proves just what it says: that X contains n elements!

I can't think what else you could mean.


Hahaha, well I guess that's the meaning that I missed. Sorry for my horrible math skills. The last time I took any university level math was 5 years ago. I'm just going back to school now for some upper level math courses to complete a minor in Math.

I've basically forgotten everything.
 

Related to Having trouble applying Hall's Theorem

1. What is Hall's Theorem and why is it important?

Hall's Theorem is a mathematical concept that states a bipartite graph has a perfect matching if and only if it satisfies a certain condition known as the Hall's condition. It is important because it helps in determining the existence of a perfect matching in a bipartite graph, which has applications in various fields such as computer science, economics, and social sciences.

2. What is the Hall's condition and how does it relate to the theorem?

The Hall's condition states that in a bipartite graph, for any subset of vertices on one side, the number of adjacent vertices on the other side must be equal to or greater than the number of vertices in the subset. This condition is crucial in determining the existence of a perfect matching in the graph according to Hall's Theorem.

3. What are some common problems people face when applying Hall's Theorem?

One common problem is understanding the concept of a bipartite graph and how it relates to the theorem. Another issue is identifying and applying the Hall's condition correctly, especially in complex graphs. Additionally, people may struggle with proving the theorem or identifying a perfect matching in a graph.

4. Are there any limitations to Hall's Theorem?

Yes, there are limitations to Hall's Theorem. It only applies to bipartite graphs and cannot be used for non-bipartite graphs. Also, it does not provide an algorithm for finding a perfect matching, it only determines whether one exists or not.

5. How can I improve my understanding and application of Hall's Theorem?

To improve your understanding and application of Hall's Theorem, you can practice solving problems and proofs related to the theorem. It can also be helpful to study examples and applications of the theorem in different fields. Additionally, seeking help from a tutor or joining a study group can also aid in improving your understanding of the theorem.

Similar threads

A proof that a union of compact spaces is compact
    • Calculus and Beyond Homework Help
Replies
12
Views
1K
Prove every subset of countable set is either finite or else countable
    • Calculus and Beyond Homework Help
Replies
1
Views
526
Prove that the sequence does not have a convergent subsequence
    • Calculus and Beyond Homework Help
Replies
4
Views
893
My proof of the Geometry-Real Analysis theorem
    • Calculus and Beyond Homework Help
Replies
1
Views
665
To prove the "##m^{\text{th}}## Powers Theorem"
    • Calculus and Beyond Homework Help
Replies
3
Views
606
I Bloch Analysis proof of Theorem 2.5.5 (Definition by recursion)
    • Topology and Analysis
Replies
2
Views
344
Prove ##a \cdot 1 = a = 1 \cdot a## for ##a \in \mathbb{N}##
    • Calculus and Beyond Homework Help
Replies
1
Views
538
Lemma: Extracting a convergent subsequence
    • Calculus and Beyond Homework Help
Replies
11
Views
1K
Generalization of a theorem in Real Analysis
    • Calculus and Beyond Homework Help
Replies
3
Views
1K
Prove ##(a+b)\cdot c=a\cdot c+b\cdot c## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
3
Views
535

Hot Threads

Recent Insights

Back
Top