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{.}\)
Generalize the result in
question 7.b to all
\(n\) (not just odd
\(n\)).
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?
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{.}\)
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 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{.}\)
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 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.
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.
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{.}\)
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 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{.}\)
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 26 from this section.
Prove
Theorem 1.5.6 in the case
\(d=1\text{.}\) Hint: The Intermediate Value Theorem may be useful.
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:
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{.}\)