suppose that $\mathcal F\subseteq p(X)$ and $|X|=n$. prove that if $|\mathcal F|>\sum_{i=0}^{k-1}\dbinom{n}{i}$ then there exist $Y\subseteq X$ with $|Y|=k$ such that $p(Y)=\mathcal F\cap Y$ that $\mathcal F\cap Y=\{F\cap Y:F\in \mathcal F\}$(20 points) you can see this problem also here: COMBINATORIAL PROBLEMS AND EXERCISES-SECOND EDITION-by LASZLO LOVASZ-AMS CHELSEA PUBLISHING- chapter 13- problem 10(c)!!!
Problem
Source:
Tags: combinatorics proposed, combinatorics
onyqz
04.12.2024 23:57
for the sake of completeness
We induct on $n$.
The base case $n=1$ is clear. So now $n\rightarrow n+1$.
WLOG let $X=[n+1]$ and $X'=[n]$. Moreover, note that $$|\mathcal{F}| > \sum_{i=0}^{k-1}{n+1 \choose i} = 2\left[\sum_{i=0}^{k-2}{n \choose i}\right] + {n \choose k-1} \, .$$Let all sets $V \in\mathcal{F}$ for which $n+1 \not\in V, V\cup\{n+1\} \in \mathcal{F}$ be in $\mathcal{V}$. Similarly, all other sets are in $\mathcal{F}\backslash\mathcal{V}:=\mathcal{U}$.
Suppose that $|\mathcal{U}|\leq \sum_{i=0}^{k-1} {n \choose i}$, otherwise the result follows by induction (by noting $U\backslash\{n+1\}\subseteq X', U\in \mathcal{U}$ and for any $A,B \in \mathcal{U}$, we have $A\backslash\{n+1\}\neq B\backslash \{n+1\}$).
Thus $|\mathcal{V}|=|\mathcal{F}|-|\mathcal{U}|>\sum_{i=0}^{k-2}{n \choose i}$.
By induction, $\mathcal{V}$ contains a set $Y' \subseteq X', |Y'|=k-1$ with $p(Y')=Y' \cap \mathcal{V}$.
Now consider $Y = Y' \cup \{n+1\}$.
For a set $S\in p(Y')$, we can find $V \in \mathcal{V}\subseteq \mathcal{F}$ s.t. $S=V \cap Y'=V\cap Y$ by above.
So consider $S \in p(Y)\backslash p(Y')$. Clearly $n+1 \in S$ and for $S\backslash \{n+1\}$ we can again find $V \in \mathcal{V}$ s.t. $S\backslash \{n+1\} = V \cap Y'$.
In fact, by how we defined $\mathcal{V}$, we can find $U \in \mathcal{U} \subseteq \mathcal{F}$ s.t. $S =(S\backslash\{n+1\})\cup \{n+1\}= (V\cup \{n+1\})\cap (Y' \cup \{n+1\})= U \cap Y$.
This shows that $Y$ indeed satisfies $Y\subseteq X, |Y|=k$ and $p(Y)=\mathcal{F}\cap Y$, which completes the problem. $\square$
semizarov
04.12.2024 23:58
imagine if he actually responds now after more than 14 years :skull:
goodar2006
08.12.2024 11:21
Respond to what?
AshAuktober
08.12.2024 12:56
HE'S BACK AFTER 3 YEARS OF DORMANCY!!! NO WAY