0
$\begingroup$

Let

  • $|S| = n, \mathcal{A} \subseteq \binom{S}{k}, 1 \leq k < n$.
  • $\nabla \mathcal{A} := \left\{A \in \binom{S}{k+1} : \exists A' \in \mathcal{A} \text{ so } A' \subset A\right\}$ (shade of $\mathcal{A}$)
  • $\Delta \mathcal{A} := \left\{A \in \binom{S}{k-1} : \exists A' \in \mathcal{A} \text{ so } A \subset A'\right\}$ (shadow of $\mathcal{A}$)

Show that $\mathcal{A} = \nabla\Delta\mathcal{A} \Rightarrow \mathcal{A} = \binom{S}{k}$applies for $\mathcal{A} \neq \emptyset$

This seems pretty obvious to me. If I build a set $X$ by successively each item of all items of $\mathcal{A}$ (shadow), and afterwards add each possible item to each item of $X$, I (re-) create at least all items of $\mathcal{A}$, and more of them unless $\mathcal{A}$ already contains all possible items.

I played around for some time, but am struggling with a formally correct way to prove this.

Can you please tell me how a formally correct approach could be created?

$\endgroup$

1 Answer 1

1
$\begingroup$

Assume that $\emptyset \neq \mathcal{A} \neq \binom{S}{k}$. Then there is some $B:= \{x_1,...,x_k\} \subseteq S$ such that $B \not \in \mathcal{A}$ and some $z \in S \setminus B$ such that for $C:=\{x_1,...,x_{k-1},z\}$ we have $C \in \mathcal{A}$. You can prove this statement as follows:

Assume that for all sets $B = \{x_1,...,x_k\} \subseteq S$ and all sets $C:= \{x_1,...,x_{k-1},z\}$ with $z \in S\setminus B$, we have both $B \in \mathcal{A}$ and $C \in \mathcal{A}$. Now assume that we have two sets $D,E \in \mathcal{A}$ such that $D = \{y_1,..,y_{k-i},y_{k-i+1},...,y_k\}$ and $E = \{y_1,...,y_{k-i},v_{k-i+1},...,v_k\}$ where all $v_j \in S \setminus D$ and $1 \leq i < k$. The sets $D$ and $E$ differ by exactly $i$ elements. By an application of the assumption about all $B,C$ above, we get that every $F = \{y_1,...,y_{k-i-1},z,v_{k-i+1},...,v_k\}$ with $z \in S \setminus E$ is also in $\mathcal{A}$, particularly those $F$ with $z \neq y_{k-i}$. In other words, every set in $\binom{S}{k}$ that differs from $D$ by exactly $i+1$ elements is also in $\mathcal{A}$. Thus given our assumption about $B,C$ we find by induction that all sets $Y\in \binom{S}{k}$ that differ from some $X \in \mathcal{A}$ by at least $1$ and at most $k$ elements are also in $\mathcal{A}$, and so $\mathcal{A} = \binom{S}{k}$. Since this contradicts the assumption that $\mathcal{A}\neq \binom{S}{k}$, we have shown that there is some $B$ such that there is some $C$ as above such that $C \in \mathcal{A}$ and $B \not \in \mathcal{A}$.


Now back to our original problem: we just showed that we can choose $B$ and $C$ as we did in the very beginning, and so $\{x_1,...,x_{k-1}\} \in \Delta\mathcal{A}$ and thus $B \in \nabla\Delta\mathcal{A}$ and so $\mathcal{A} \neq \nabla \Delta \mathcal{A}$. Taking the contrapositive gives you the claim.

(I think a similar argument shows the same for $\Delta \nabla \mathcal{A}$.)

$\endgroup$
11
  • $\begingroup$ Thank you for your answer! Do you mean $C := \{x_1,\cdots,x_{k-1},z\}$? If not, what are your $c_i$? $\endgroup$
    – muffel
    Jun 14, 2014 at 16:20
  • $\begingroup$ @muffel Thanks, that was a typo, I do mean $C:= \{x_1,...,x_{k-1},z\}$. $\endgroup$
    – G. Bach
    Jun 14, 2014 at 16:20
  • $\begingroup$ @muffel Be sure to prove the claim that ends in "(why?)", that's a necessary part of this proof. $\endgroup$
    – G. Bach
    Jun 14, 2014 at 17:42
  • $\begingroup$ I thought of the 'why' by building it the other way round: The $C$ could be built by taking an element of $\mathcal{A}$ so that by exchanging one item of it, the resulting set is not in $\mathcal{A}$ (and therefore the $B$ of your example). As $\mathcal{A} \neq \binom{S}{k}$ such an element must exists. Am I right? Is there a shorter or better way to assume such a $C$ exists? $\endgroup$
    – muffel
    Jun 15, 2014 at 8:15
  • $\begingroup$ @muffel: That's not actually a proof, that's just a reaffirmation of the claim. I added a proof to my answer. You wouldn't usually add a proof in the middle of another proof, you would first give the proof for the claim "if $\emptyset \neq \mathcal{A} \neq \binom{S}{k}$, then there is some $B := ...$ such that $B \not \in \mathcal{A}$ and some $z...$ such that for $C...$ we have $C \in \mathcal{A}$. Proof:..." and then you would use that lemma to prove what you actually want to prove. $\endgroup$
    – G. Bach
    Jun 15, 2014 at 13:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .