 rose2904ks

2022-06-19

How to prove $p\left(x\right)\ge {m}^{2}/4$
Let $\mathcal{F}$ be a family of m subsets of a finite set X. For $x\in X$, let p(x) be the number of pairs (A,B) of sets $A,B\in \mathcal{F}$ such that either $x\in A\cap B$ or $x\notin A\cup B$. Prove that $p\left(x\right)\ge {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 $\mathcal{F}$, and observe that $p\left(x\right)=d\left(x{\right)}^{2}+\left(m-d\left(x\right){\right)}^{2}$.
I was wondering if someone could help me about my problem. Thanks in advance. Step 1
Well ${m}^{2}=p\left(x\right)+\left({m}^{2}-p\left(x\right)\right)$ so either $p\left(x\right)\ge {m}^{2}/2$ or ${m}^{2}-p\left(x\right)>{m}^{2}/2$. Notice that the hint implies(or the way you solve it by counting) that ${m}^{2}-p\left(x\right)=2d\left(x\right)\left(m-d\left(x\right)\right)$ why?
Step 2
We want to show that it is not possible that $2d\left(x\right)\left(m-d\left(x\right)\right)>{m}^{2}/2$ can you factor the whole expression in a nice way?

Do you have a similar question?