Skip to main content

Section 1.6 Exercises

  1. Prove that the maximum cardinality of an intersecting family \(\mathcal{F}\subseteq 2^{[n]}\) is \(2^{n-1}\text{.}\)
  2. 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{.}\)
  3. For \(n\geq5\text{,}\) describe three non-isomorphic constructions of intersecting families \(\mathcal{F}\subseteq 2^{[n]}\) of cardinality \(2^{n-1}\text{.}\)
  4. 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.
  5. 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{.}\)
  6. Exactly how many intersecting families in \(\binom{[n]}{2}\) are there?
    1. 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.
    2. 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.
    3. 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{.}\)
    4. Generalize the result in question 7.b to all \(n\) (not just odd \(n\)).
  7. 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?
  8. Let \(1 \leq a \leq b \leq n\) be integers such that \(a+b\leq n\) and let \(\mathcal{F}\subseteq 2^{[n]}\) be an intersecting family such that every element of \(\mathcal{F}\) has cardinality between \(a\) and \(b\text{.}\) Prove that
    \begin{equation*} |\mathcal{F}|\leq \sum_{i=a}^b\binom{n-1}{i-1}. \end{equation*}
    Hint: The Erdős–Ko–Rado Theorem should be useful for this, but be careful because that \(b\) may be larger than \(n/2\text{.}\)
  9. 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{.}\)
  10. 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{.}\)
  11. As in Exercise 11 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{.}\)
    1. 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.
    2. 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{.}\)
  12. 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.
    1. 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{.}\)
    2. Generalize the construction from question 14.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.
  13. 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?
  14. 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{.}\)
  15. 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.
    1. For \(k\geq1\text{,}\) prove that \(\binom{[2k-1]}{k}\) does not have Property B.
    2. Prove that, if there does not exist \(A,B\in\mathcal{F}\) with \(|A\cap B|=1\text{,}\) then \(\mathcal{F}\) has Property B.
  16. 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{.}\)
  17. 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.
  18. 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.
  19. 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.
  20. 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.
  21. For each \(n\geq3\text{,}\) find a family \(\mathcal{F}\subseteq 2^{[n]}\) with VC-dimension at most 1 such that \(|\mathcal{F}|=n+1\) and \(\mathcal{F}\) is not equal to \(\binom{[n]}{0}\cup\binom{[n]}{1}\) or \(\binom{[n]}{n-1}\cup\binom{[n]}{n}\text{.}\)
  22. Let \(\mathcal{F}\) be the collection of all closed half-planes in \(\mathbb{R}^2\text{.}\) Prove that \(\mathcal{F}\) has VC-dimension three.
  23. 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{.}\)
  24. 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*}
    1. 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*}
    2. Let \(\mathcal{F},\mathcal{G},\mathcal{F}^c\) and \(\mathcal{G}^c\) be as in question 27.a. Using the result of question 27.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{.}\)
    3. 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{.}\)
  25. 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*}
  26. 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*}
  27. 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 26 from this section.
  28. Prove Theorem 1.5.6 in the case \(d=1\text{.}\) Hint: The Intermediate Value Theorem may be useful.
    1. 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{.}\)
    2. Suppose that \(n>2k\text{.}\) Explain why there cannot exist a weight function as in question 32.a such that \(w(\mathcal{F})\in \{0,1\}\) for all \(\mathcal{F}\in\mathscr{I}\text{.}\)
  29. Watch the film N is a Number.