We call $A_{1},A_{2},A_{3}$ mangool iff there is a permutation $\pi$ that $A_{\pi(2)}\not\subset A_{\pi(1)},A_{\pi(3)}\not\subset A_{\pi(1)}\cup A_{\pi(2)}$. A good family is a family of finite subsets of $\mathbb N$ like $X,A_{1},A_{2},\dots,A_{n}$. To each goo family we correspond a graph with vertices $\{A_{1},A_{2},\dots,A_{n}\}$. Connect $A_{i},A_{j}$ iff $X,A_{i},A_{j}$ are mangool sets. Find all graphs that we can find a good family corresponding to it.
Problem
Source: Iran TST 2002
Tags: combinatorics proposed, combinatorics
24.07.2016 10:07
I suppose it's all the complementary gragh of a gragh consisting of several non-intersecting complete paragraphs
06.06.2022 05:38
The answer is that all graphs correspond to some good family. We will only use the following two results about mangool sets: Claim 1: If $X \not\subset A_i \cup A_j$ and $A_i \not\equiv A_j$, then $\{X,A_i,A_j\}$ is mangool. Proof: Note at least one of $A_i \not\subset A_j$ or $A_j \not\subset A_i$ is true, and our Claim follows. $\square$ Claim 2: If $A_i,A_j \subset X$ and $X \subset A_i \cup A_j$, then $\{X,A_i,A_j\}$ is mongool. Proof: Just note that $$ A_i \subset X \cup A_j ~~,~~ A_j \subset X \cup A_i ~~,~~ X \subset A_i \cup A_j $$so our Claim follows. $\square$ We return to our main problem now. Fix any graph $G$ on $n$ veritces. We look at $\overline{G}$ (complement of $G$). We construct a good family satisfying the following: $ A_1,A_2,\ldots,A_n \subset X $ $A_1,A_2,\ldots,A_n$ are pairwise distinct. For any $A_i,A_j$, they are connected in $\overline{G}$ iff there is a element of $X$ which is in neither of $A_i,A_j$. then we are done. We do this now! Originally start with any set $X$ containing a lot of elements and take $$ A_1 \equiv A_2 \equiv \cdots \equiv A_n \equiv X $$To any edge of $A_iA_j$ of $\overline{G}$, we correspond a unique element $\alpha \in X$. Then we remove element $\alpha$ from sets $A_i,A_j$ only (and not any other $A_k$). This way, note the first and third condition are satisfied. Lastly we require all $A_1,\ldots,A_n$ to be distinct. To do this, pick a set $Y$ disjoint from $X$. Add $Y$ to each of the sets $X,A_1,A_2,\ldots,A_n$. Then from each $A_i$, remove some unique element of $Y$. This completes the proof. $\blacksquare$ Remark: In the above proof, we are assuming $X \subset X$. Even if $X \not\subset X$ was meant, then that is easy to fix. Basically after constructing as above, to each edge $A_iA_j$ of $G$, we correspond a unique element $\beta$ which is not in either of $X,Y$. Then we add $\beta$ to both of $A_i,A_j$ only (and not any other $A_k$).