## Section 1.6 Exercises

- Prove that the maximum cardinality of an intersecting family \(\mathcal{F}\subseteq 2^{[n]}\) is \(2^{n-1}\text{.}\)
- Prove that every intersecting family \(\mathcal{F}\subseteq 2^{[n]}\) is contained in an intersecting family in \(2^{[n]}\) of cardinality \(2^{n-1}\text{.}\)
- For \(n\geq5\text{,}\) describe three non-isomorphic constructions of intersecting families \(\mathcal{F}\subseteq 2^{[n]}\) of cardinality \(2^{n-1}\text{.}\)
- Prove that, if \(\mathcal{F}_1,\dots,\mathcal{F}_k\) are intersecting families in \(2^{[n]}\text{,}\) then\begin{equation*} \left|\bigcup_{i=1}^k\mathcal{F}_i\right|\leq 2^n-2^{n-k}\text{.} \end{equation*}
*Hint:*The Harris–Kleitman Inequality and Exercise 1 in this section may be useful. - For \(n\leq 2k\text{,}\) determine the size of the largest family \(\mathcal{F}\subseteq \binom{[n]}{k}\) such that \(A\cup B\neq [n]\) for all \(A,B\in \mathcal{F}\text{.}\)
- Exactly how many intersecting families in \(\binom{[n]}{2}\) are there?
- Given \(x\in \{0,1,2\}^n\) and \(1\leq i\leq n\text{,}\) let \(x_i\) denote the \(i\)th coordinate of \(x\text{.}\) Say that a set \(F\subseteq\{0,1,2\}^n\) is
*intersecting*if for any \(x,y\in F\) there exists \(1\leq i\leq n\) such that \(x_i=y_i \neq 0\text{.}\) Determine the maximum size of a set \(F\subseteq\{0,1,2\}^n\) that is intersecting. - Say that a set \(F\subseteq\{0,1,2\}^n\) is
*weakly intersecting*if for any \(x,y\in F\) there exists \(1\leq i\leq n\) such that \(x_i\neq 0\) and \(y_i \neq 0\text{.}\) Suppose that \(n\) is odd and consider the set\begin{equation*} B:=\{x\in\{0,1,2\}^n: x_i\neq 0\text{ for more than } n/2\text{ indices } i\}\text{.} \end{equation*}Show that \(B\) is weakly intersecting, and that every weakly intersecting set has cardinality at most \(|B|\text{.}\)*Hint:*Given a weakly intersecting \(F\subseteq\{0,1,2\}^n\text{,}\) consider the family \(\mathcal{F}:=\{\{i: x_i\neq0\}: x\in F\}\subseteq 2^{[n]}\text{.}\) It may be helpful to solve Exercise 1 and Exercise 2 in this section first. - Generalize the results of question 7.a and question 7.b to subsets of \(\{0,1,\dots,r-1\}^n\) for all \(r\geq2\text{.}\)

- An intersecting family \(\mathcal{F}\subseteq \binom{[n]}{k}\) is
*maximal*if \(\mathcal{F}\cup\{S\}\) is not intersecting for any \(S\in\binom{[n]}{k}\setminus \mathcal{F}\text{.}\) For integers \(k\) and \(n\text{,}\) let \(f_k(n)\) be the minimum size of a maximal intersecting family in \(\binom{[n]}{k}\text{.}\) For fixed \(k\text{,}\) does \(f_k(n)\) tend to infinity as \(n\) tends to infinity? - For \(n\geq k\geq1\text{,}\) suppose that \(\mathcal{F}\subseteq \binom{[n]}{k}\) such that \(|\mathcal{F}|\geq k+1\) and any \(k+1\) sets in \(\mathcal{F}\) have a common element. Prove that there exists \(x\in[n]\) which is in every set in \(\mathcal{F}\text{.}\)
- Find a collection \(\mathcal{F}\subseteq 2^{[n]}\) of cardinality \(2^{n-1}+1\) such that, for every \(\mathcal{A}\subseteq \mathcal{F}\) such that \(\bigcap_{S\in\mathcal{A}}S = \emptyset\text{,}\) it holds that \(\bigcup_{S\in\mathcal{A}}S =[n]\text{.}\)
- As in Exercise 10 in this section, let \(\mathcal{F}\subseteq 2^{[n]}\) have the property that, for every \(\mathcal{A}\subseteq \mathcal{F}\) such that \(\bigcap_{S\in\mathcal{A}}S = \emptyset\text{,}\) it holds that \(\bigcup_{S\in\mathcal{A}}S =[n]\text{.}\) Our goal in this exercise is to prove that \(|\mathcal{F}|\leq 2^{n-1}+1\text{.}\)
- Let \(G\) be a graph with vertex set \([n]\) defined by letting \(ij\) be an edge of \(G\) if every set in \(\mathcal{F}\) intersects \(\{i,j\}\text{.}\) Prove that every vertex of \(G\) has degree at least one.
- Show that if \(G\) is a graph on vertex set \([n]\) of minimum degree at least one, then the number of sets \(S\subseteq [n]\) such that \(S\cap\{i,j\}\neq \emptyset\) for every \(ij\in E(G)\) is at most \(2^{n-1}+1\text{.}\) Using this, conclude that \(|\mathcal{F}|\leq 2^{n-1}+1\text{.}\)

- Suppose that \(\mathcal{F}\subseteq 2^{[n]}\) such that \(|S\cap T|\neq 1\) for all \(S,T\in\mathcal{F}\text{.}\) Prove that it is possible to colour \([n]\) with \(2\) colours such that there does not exist a set in \(\mathcal{F}\) whose elements are all the same colour.
- A
*matching*in a family \(\mathcal{F}\subseteq 2^{[n]}\) is a collection \(\mathcal{M}\subseteq \mathcal{F}\) such that \(A\cap B=\emptyset\) for all \(A,B\in \mathcal{M}\text{.}\) Show that there exists a family \(\mathcal{F}\subseteq 2^{[n]}\) of cardinality \(\frac{3}{4}2^{n}\) which does not contain a matching of cardinality \(3\) such that, for every \(X\in 2^{[n]}\setminus \mathcal{F}\text{,}\) the family \(\mathcal{F}\cup\{X\}\) contains a matching of cardinality \(3\text{.}\) - Generalize the construction from question 13.a to matchings of any cardinality \(k\) such that \(1\leq k\leq n\text{.}\) For different values of \(k\text{,}\) the cardinality of \(\mathcal{F}\) should be different.

- Let \(\mathcal{A}\subseteq 2^{\mathbb{N}}\) be an intersecting family. Does there necessarily exist a finite set \(F\) such that \(\{A\cap F: A\in\mathcal{A}\}\) is intersecting?
- A
*permutation*of \([n]\) is a sequence \(\pi=(\pi_1,\dots,\pi_n)\) such that, for each \(j\in [n]\text{,}\) there is a unique \(1\leq i\leq n\) such that \(\pi_i=j\text{.}\) For example, \((1,3,2)\) is a permutation of \([3]\text{.}\) Say that permutations \(\pi\) and \(\sigma\) of \([n]\)*intersect*if there exists \(i\) such that \(\pi_i=\sigma_i\text{.}\) Determine the maximum size of an intersecting family of permutations of \([n]\text{.}\) - A set system \(\mathcal{F}\subseteq 2^{[n]}\) has
*Property B*if the elements of \([n]\) can be coloured with two colours in such a way that no set \(A\in\mathcal{F}\) is monochromatic.- For \(k\geq1\text{,}\) prove that \(\binom{[2k-1]}{k}\) does not have Property B.
- Prove that, if there does not exist \(A,B\in\mathcal{F}\) with \(|A\cap B|=1\text{,}\) then \(\mathcal{F}\) has Property B.

- For \(n\geq 1\text{,}\) determine the maximum size of a collection \(\mathcal{F}\subseteq 2^{[n]}\) such that there does not exist \(a\in [n]\) such that there are two different sets in \(\mathcal{F}\) that contain \(a\) and two different sets in \(\mathcal{F}\) that do not contain \(a\text{.}\)
- Let \(V_1,\dots,V_k\) be pairwise disjoint sets, each of cardinality \(p-1\text{,}\) and let \(V=V_1\cup\cdots \cup V_k\text{.}\) Define\begin{equation*} \mathcal{F}:=\{F\subseteq V: |F\cap V_i|=1\text{ for } 1\leq i\leq k\}\text{.} \end{equation*}Prove that \(\mathcal{F}\) has cardinality \((p-1)^k\) and does not contain any sunflower with \(p\) petals.
- Adapt the argument in the proof of Theorem 1.2.3 to prove a version of the Sunflower Lemma in the case that \(\mathcal{F}\) is a multiset of sets in \(\binom{\mathbb{N}}{k}\) (that is, \(\mathcal{F}\) may contain multiple copies of the same element of \(\binom{\mathbb{N}}{k}\)); note that the bound on \(|\mathcal{F}|\) should be different.
- Let \(\mathcal{F}\) be the collection of all convex subsets of \(\mathbb{R}^2\text{.}\) Show that \(\mathcal{F}\) does not have bounded VC-dimension.
- Let \(X\) be a set and let \(\mathcal{F}\subseteq 2^{X}\text{.}\) The
*dual system*\(\mathcal{F}^*\) is a subset of \(2^{\mathcal{F}}\) defined as follows. For each \(x\in X\text{,}\) the dual system contains the set\begin{equation*} \{F\in\mathcal{F}: x\in F\}\text{.} \end{equation*}(We ignore duplicate sets). Prove that, for every positive integer \(d\text{,}\) there exists \(f(d)\) such that if \(\mathcal{F}\) has VC-dimension at most \(d\text{,}\) then the VC-dimension of \(\mathcal{F}^*\) is at most \(f(d)\text{.}\)*Hint:*It may help to play around with the cases \(d=1\) and \(d=2\) before trying to generalize. - Let \(\mathcal{F}\) be the collection of all closed half-planes in \(\mathbb{R}^2\text{.}\) Prove that \(\mathcal{F}\) has VC-dimension three.
- Let \(\mathcal{F}\) be the collection of all \((n-1)\)-dimensional hyperplanes in \(\mathbb{R}^n\text{.}\) Show that \(\mathcal{F}\) has VC-dimension \(n\text{.}\)
- Show that, if \(\mathcal{A},\mathcal{B}\subseteq 2^{[n]}\) such that \(\mathcal{A}\) is a downset and \(\mathcal{B}\) is an upset, then\begin{equation*} \frac{|\mathcal{A}\cap\mathcal{B}|}{2^n}\leq \frac{|\mathcal{A}|}{2^n}\cdot \frac{|\mathcal{B}|}{2^n}\text{.} \end{equation*}
- Let \(\mathcal{F}\) be an upset and \(\mathcal{G}\) be a downset in \(2^{[n]}\text{.}\) Define \(\mathcal{F}^c:=2^{[n]}\setminus \mathcal{F}\) and \(\mathcal{G}^c:=2^{[n]}\setminus \mathcal{G}\text{.}\) Prove that\begin{equation*} |\mathcal{F}\cap\mathcal{G}^c|\cdot |\mathcal{G}\cap\mathcal{F}^c|\geq |\mathcal{F}\cap \mathcal{G}|\cdot\left|\mathcal{F}^c\cap \mathcal{G}^c\right|\text{.} \end{equation*}
- Let \(\mathcal{F},\mathcal{G},\mathcal{F}^c\) and \(\mathcal{G}^c\) be as in question 25.a. Using the result of question 25.a, or otherwise, prove that \(|\mathcal{F}\cap \mathcal{G}|^{1/2}+ |\mathcal{F}^c\cap\mathcal{G}^c|^{1/2}\leq 2^{n/2}\text{.}\)
*Hint 1:*Square both sides.*Hint 2:*\(|\mathcal{F}^c\cap\mathcal{G}^c| = 2^n-|\mathcal{F}\cap \mathcal{G}^c| - |\mathcal{G}\cap \mathcal{F}^c| - |\mathcal{F}\cap\mathcal{G}|\text{.}\) - Prove that, if \(\mathcal{A}\) and \(\mathcal{B}\) are families in \(2^{[n]}\) such that no set in \(\mathcal{A}\) contains a set in \(\mathcal{B}\) and no set in \(\mathcal{B}\) contains a set in \(\mathcal{A}\text{,}\) then \(|\mathcal{A}|^{1/2}+|\mathcal{B}|^{1/2}\leq 2^{n/2}\text{.}\)

- For \(r\geq2\text{,}\) let \(\mathcal{P}_r^n\) be the partially ordered set on \(\{0,1,\dots,r-1\}^n\) where \((x_1,\dots,x_n)\preceq (y_1,\dots,y_n)\) if and only if \(x_i\leq y_i\) for all \(1\leq i\leq n\text{.}\) A
*downset*in \(\mathcal{P}_r^n\) is a set \(A\subseteq \mathcal{P}_r^n\) such that if \(x\in A\) and \(y\preceq x\text{,}\) then \(y\in A\text{.}\) Prove that, if \(A\) and \(B\) are downsets in \(\mathcal{P}_r^n\text{,}\) then\begin{equation*} \frac{|A\cap B|}{r^n}\geq \frac{|A|}{r^n}\cdot \frac{|B|}{r^n}\text{.} \end{equation*} - Let \(G\) be a random graph on \(n\) vertices obtained by including each edge in \(G\) with probability \(1/2\text{,}\) independently of all other edges. Let \(E\) be the event that \(G\) contains \(n/3\) vertex-disjoint triangles and \(F\) be the event that \(G\) contains a complete graph with at least \(3\log(n)\) vertices. Prove that\begin{equation*} \mathbb{P}(E\cap F)\geq \mathbb{P}(E)\mathbb{P}(F)\text{.} \end{equation*}
- For \(n\geq2\text{,}\) prove that the size of the largest family \(\mathcal{F}\subseteq 2^{[n]}\) such that \(\mathcal{F}\) is intersecting and \(A\cup B\neq[n]\) for all \(A,B\in \mathcal{F}\) is \(2^{n-2}\text{.}\)
*Hint:*Apply Exercise 24 from this section. - Let \(k\geq1\) and \(n\geq2k\) and let \(\mathscr{I}\) be the collection of all intersecting families in \(\binom{[n]}{k}\text{.}\) Prove that there is a “weight function” \(w:\mathscr{I}\to [0,1]\) with the following properties:
- \(\sum_{\mathcal{F}\ni A}w(\mathcal{F})\geq 1\) for all \(A\in \binom{[n]}{k}\) and
- \(\sum_{\mathcal{F}\in \mathscr{I}}w(\mathcal{F})\leq n/k\text{.}\)

- Suppose that \(n>2k\text{.}\) Explain why there cannot exist a weight function as in question 30.a such that \(w(\mathcal{F})\in \{0,1\}\) for all \(\mathcal{F}\in\mathscr{I}\text{.}\)

- Watch the film
.`N is a Number`