How to prove p ( x ) ≥ m 2 / 4Let F be a...

rose2904ks

rose2904ks

Answered question

2022-06-19

How to prove p ( x ) m 2 / 4
Let F be a family of m subsets of a finite set X. For x X, let p(x) be the number of pairs (A,B) of sets A , B F such that either x A B or x A B. Prove that p ( x ) m 2 / 2.
In the book I'm studying, writer has written the following hint:
Hint: Let d(x) be the degree of x in F , and observe that p ( x ) = d ( x ) 2 + ( m d ( x ) ) 2 .
I was wondering if someone could help me about my problem. Thanks in advance.

Answer & Explanation

Zayden Andrade

Zayden Andrade

Beginner2022-06-20Added 22 answers

Step 1
Well m 2 = p ( x ) + ( m 2 p ( x ) ) so either p ( x ) m 2 / 2 or m 2 p ( x ) > m 2 / 2. Notice that the hint implies(or the way you solve it by counting) that m 2 p ( x ) = 2 d ( x ) ( m d ( x ) ) why?
Step 2
We want to show that it is not possible that 2 d ( x ) ( m d ( x ) ) > m 2 / 2 can you factor the whole expression in a nice way?

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?