rose2904ks

2022-06-19

How to prove $p(x)\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(x)\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(x)=d(x{)}^{2}+(m-d(x){)}^{2}$.

I was wondering if someone could help me about my problem. Thanks in advance.

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(x)\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(x)=d(x{)}^{2}+(m-d(x){)}^{2}$.

I was wondering if someone could help me about my problem. Thanks in advance.

Zayden Andrade

Beginner2022-06-20Added 22 answers

Step 1

Well ${m}^{2}=p(x)+({m}^{2}-p(x))$ so either $p(x)\ge {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)=2d(x)(m-d(x))$ why?

Step 2

We want to show that it is not possible that $2d(x)(m-d(x))>{m}^{2}/2$ can you factor the whole expression in a nice way?

Well ${m}^{2}=p(x)+({m}^{2}-p(x))$ so either $p(x)\ge {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)=2d(x)(m-d(x))$ why?

Step 2

We want to show that it is not possible that $2d(x)(m-d(x))>{m}^{2}/2$ can you factor the whole expression in a nice way?