Having trouble applying Hall's Theorem

  • Thread starter Thread starter junho
  • Start date Start date
  • Tags Tags
    Theorem
junho
Messages
5
Reaction score
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
?? |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.
 
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.
 
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.
 
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.
 

Thread 'Prove that the integral is equal to ##\pi^2/8##'

Prove $$\int\limits_0^{\sqrt2/4}\frac{1}{\sqrt{x-x^2}}\arcsin\sqrt{\frac{(x-1)\left(x-1+x\sqrt{9-16x}\right)}{1-2x}} \, \mathrm dx = \frac{\pi^2}{8}.$$ Let $$I = \int\limits_0^{\sqrt 2 / 4}\frac{1}{\sqrt{x-x^2}}\arcsin\sqrt{\frac{(x-1)\left(x-1+x\sqrt{9-16x}\right)}{1-2x}} \, \mathrm dx. \tag{1}$$ The representation integral of ##\arcsin## is $$\arcsin u = \int\limits_{0}^{1} \frac{\mathrm dt}{\sqrt{1-t^2}}, \qquad 0 \leqslant u \leqslant 1.$$ Plugging identity above into ##(1)## with ##u...
View full post »

Similar threads

A proof that a union of compact spaces is compact
Replies
12
Views
2K
Prove every subset of countable set is either finite or else countable
Replies
1
Views
2K
Prove that the sequence does not have a convergent subsequence
Replies
4
Views
1K
Generalization of a theorem in Real Analysis
Replies
3
Views
1K
My proof of the Geometry-Real Analysis theorem
Replies
1
Views
1K
Hall's theorem problem (graph theory)
Replies
12
Views
4K
To prove the "##m^{\text{th}}## Powers Theorem"
Replies
3
Views
1K
Lemma: Extracting a convergent subsequence
Replies
11
Views
2K
A quite verbal proof that if V is finite dimensional then S is also....
Replies
34
Views
3K
Normal group of order 60 isomorphic to A_5
Replies
6
Views
1K

Hot Threads

Recent Insights

Back
Top