Lesson 2

Advanced Problems.

1. (20 points) Provide examples of four \(S_{1}, S_{2}, S_{3}, S_{4}\) pairwise non-isomorphic countable linearly ordered sets, each of which is dense in a space \(X_{i}\) with a cardinality of at least continuum.
2. (20 points) A family of sets \(\mathcal{F}\) is called \(r\)-union-free if \(A_{0} \not\subseteq A_{1} \cup A_{2} \cup \cdots \cup A_{r}\) holds for all distinct \(A_{0}, A_{1}, …, A_{r} \in \mathcal{F}\). Thus, antichains are \(r\)-union-free for \(r = 1\).

   Let \(\mathcal{F}= \{A_{1}, …, A_{m}\}\) be an \(r\)-union-free family. Show that then \[\bigcup_{i \in I}A_{i} \ne \bigcup_{j \in J}A_{j}\] for any two distinct non-empty subsets \(I, J\) of size at most \(r\).

   Hint:

   Assume, for the sake of contradiction, that the two unions are equal. Since the index sets \(I\) and \(J\) are distinct, one must contain an index that the other does not. Consider the set \(A_{k}\) corresponding to such an index \(k\) and examine the implication in light of the definition of an \(r\)-union-free family.
3. (20 points) Consider \((2^{\mathbb{N}}, \subseteq)\), the family of all subsets of the natural numbers, ordered by inclusion. Does it have a subfamily of cardinality continuum such that any two elements of the subfamily are incomparable?
4. (20 points) Prove that if \(\mathcal{F}\) is antichain in \((2^{[n]}, \subseteq)\), then \(|\mathcal{F}| \leq \binom{n}{\lfloor n / 2 \rfloor}\).
5. (20 points) Let \(\mathcal{F}= \{A_{1}, …, A_{m}\}\) be a family of subsets of an \(n\)-element set \(X\). The family \(\mathcal{F}\) is said to be convex if, for any sets \(A_{i}, A_{j} \in \mathcal{F}\), every set \(B\) such that \(A_{i} \subseteq B \subseteq A_{j}\) also belongs to \(\mathcal{F}\). Prove that the absolute value of the sum \(\sum_{i=1}^{m}(-1)^{|A_i|}\) does not exceed \(\binom{n}{\lfloor n/2 \rfloor}\).
   Hint:

   Consider the poset of all subsets of the \(n\)-element set, ordered by inclusion. Use the fact that this poset can be partitioned into \(\binom{n}{\lfloor n/2 \rfloor}\) symmetric chains.
6. (20 points) Let \(\mathcal{F}\) be a \(k\)-uniform family of sets. Suppose that \(\mathcal{F}\) is intersection-free, which means that for any three distinct sets \(A, B, C \in \mathcal{F}\), we have the condition \(A \cap B \not\subseteq C\). Prove that the size of the family is bounded by \(|\mathcal{F}| \le 1 + \binom{k}{\lfloor k/2 \rfloor}\).
   Hint:

   Fix an arbitrary set \(B_{0} \in \mathcal{F}\). Consider the family of sets \(\mathcal{G}= \{A \cap B_{0} \mid A \in \mathcal{F}, A \neq B_{0}\}\). Show that this family \(\mathcal{G}\) is an antichain composed of subsets of \(B_{0}\).
7. (20 points) Let \(\mathcal{F}\) be an antichain over a set \(X\) of \(n\) elements. Then \[\sum_{A \in \mathcal{F}}\binom{n}{|A|}^{-1}\leq 1.\]
8. (20 points) Let \(x_{1}, …, x_{n}\) be real numbers satisfying \(x_{i} \ge 1\) for each \(i\). Let \(S\) be the set of all numbers which can be formed as \(\sum_{i=1}^{n}\alpha_{i} x_{i}\), where each coefficient \(\alpha_{i} \in \{-1, 1\}\). Let \(I = [a, b)\) be any interval on the real line with length \(b - a = 2\). Show that \(|I \cap S| \le \binom{n}{\lfloor n/2 \rfloor}\).
   Hint:

   For each sum \(\xi = \sum_{i=1}^{n}\alpha_{i} x_{i}\), define a corresponding set of indices \(A_{\xi} = \{i \mid \alpha_{i} = +1\}\). Let \(\mathcal{F}\) be the family of all such sets \(A_{\xi}\) for which the sum \(\xi\) lies in the interval \(I\). Show that this family \(\mathcal{F}\) forms an antichain.
9. (20 points) Let \(\mathcal{F}= \{A_{1}, …, A_{m}\}\) and suppose that \[|A_{i} \cap A_{j}| < \frac{1}{r}\min\{|A_{i}|, |A_{j}|\} \quad \text{for all }i \ne j.\] Show that \(\mathcal{F}\) is \(r\)-union-free.
   Hint:

   To show that \(A_{0} \not\subseteq \bigcup_{i=1}^{r} A_{i}\), it is sufficient to prove that \(|A_{0}| > |A_{0} \cap (\bigcup_{i=1}^{r} A_{i})|\).
10. (20 points) You are given three arrays of distinct integers \(A\), \(B\), and \(C\), each of size \(n\), and an integer \(t \in [n]\) that divides \(n\).

    Construct an algorithm that outputs \(O(t^{2})\) triples of arrays \((A_{i}, B_{i}, C_{i})\), where \(A_{i} \subseteq A\), \(B_{i} \subseteq B\), \(C_{i} \subseteq C\), and \(|A_{i}| = |B_{i}| = |C_{i}| = n/t\). The algorithm must run in \(O((n + t^{2}) \log n)\) time.

    The output must satisfy the condition that \((0 \in A+B+C) \iff (\exists i \text{ such that }0 \in A_{i}+B_{i}+C_{i})\).

    Hint:

    First, sort the input arrays \(A\), \(B\), and \(C\). Then, consider partitioning each array into \(t\) contiguous blocks of size \(n/t\). A triple of blocks \((A_{i}, B_{j}, C_{k})\) can potentially contain a solution \(a+b+c=0\) only if the sum can span zero. Then show that it is enough to consider only \(O(t^{2})\) triples of indices instead of \(t^{3}\).
11. (20 points) Is the set \(A=\mathbb{Q}\times\mathbb{Q}\), equipped with the lexicographic order, isomorphic to the set \(B=\mathbb{Q}\) equipped with the usual order?
12. (25 points) A string \(t \in [n]^{k}\) is called \(n\)-universal if every subset \(S \subseteq [n]\) appears in \(t\) as a substring: for some index \(i\), it holds that \[S = \{t_{i}, t_{i+1}, \dotsc, t_{i + |S| - 1}\} \ .\] For example, the string \(t = \texttt{1234512413524}\) is \(5\)-universal.

    If one simply concatenates all subsets of \([n]\), an \(n\)-universal string of length \(n2^{n-1}\) is obtained (since the total number of subsets is \(2^{n}\), and the average size is \(n/2\)). Prove that there exists an \(n\)-universal string of length at most \(\frac{4}{\pi}2^{n}\).

13. (25 points) Let \(\mathcal{F}\) be a family of subsets of an \(n\)-element underlying set \(X\), and \(r \ge 2\). Prove that if \(\mathcal{F}\) is \(r\)-union-free then \(|\mathcal{F}| \le r + \binom{n}{t}\) where \[t := \left\lceil \frac{(n - r)}{\binom{r + 1}{2}}\right\rceil.\] That is, \[\frac{\log_2 |\mathcal{F}|}{n}= O\left(\frac{\log_2 r}{r^2}\right).\]