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{.}\)
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{.}\)
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.
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
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.
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{.}\)
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?
For \(k\geq1\text{,}\) let \(\mathcal{A}\subseteq \binom{\mathbb{N}}{k}\) be an intersecting family. Does there necessarily exist a finite set \(F\) such that \(\{A\cap F: A\in\mathcal{A}\}\) is intersecting? Hint: Use Theorem 1.2.3.
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.
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{.}\)
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 \(k\geq 1\) and \(p\geq 2\text{.}\) Suppose that \(\mathcal{F}\) is a family of sets, each of cardinality at most \(k\text{,}\) and that \(\mathcal{F}\) contains no sunflower with \(p\) petals. Prove that
\begin{equation*}
|\mathcal{F}|\leq \max\left\{|\mathcal{G}|:\mathcal{G}\subseteq \binom{\mathbb{N}}{k}\text{ and }\mathcal{G}\text{ contains no sunflower with }p\text{ petals}\right\}.
\end{equation*}
Let \(p\geq 2\text{.}\) Determine the largest possible cardinality of a family \(\mathcal{F}\subseteq 2^{[p-1]}\) which contains no sunflower with \(p\) petals.
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
Write down the dual set system \(\mathcal{F}^*\text{.}\) Then compute \(\operatorname{VCdim}(\mathcal{F})\) and \(\operatorname{VCdim}(\mathcal{F}^*)\text{.}\)
Prove that, for every positive integer \(d\text{,}\) there exists a function \(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: You do not need to find the best possible \(f(d)\text{.}\) It may help to first think about \(d=1\) and \(d=2\text{.}\)
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{,}\) viewed as a set system on ground set \(\mathbb{R}^2\text{.}\) Prove that \(\mathcal{F}\) has VC-dimension \(3\text{.}\)
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{.}\)
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
Let \(\mathcal{F},\mathcal{G},\mathcal{F}^c\) and \(\mathcal{G}^c\) be as in question 30.a. Using the result of question 30.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
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 \(\lfloor n/3\rfloor\) vertex-disjoint triangles and \(F\) be the event that \(G\) contains a complete graph with at least \(3\log(n)\) vertices. Prove that
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 29 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
Suppose that \(n>2k\text{.}\) Explain why there cannot exist a weight function as in question 35.a such that \(w(\mathcal{F})\in \{0,1\}\) for all \(\mathcal{F}\in\mathscr{I}\text{.}\)
