Suppose that \(|\mathcal{F}|\geq\frac{t^k}{k!}\) for some \(t>0\text{.}\) Using the previous part of the question, derive a lower bound on \(|\partial\mathcal{F}|\text{.}\) How does this compare to the bound in the Kruskal-Katona Theorem?
Let \(X\) be a random variable with range \(\mathbb{N}\) such that, for all \(n\geq1\text{,}\)
For \(1\leq i\leq n\text{,}\) let \(s_i\in \{0,1\}^{k_i}\text{.}\) Suppose that \(X\) is a random variable such that \(\mathbb{P}(X=i) = (1/2)^{k_i}\text{.}\) That is, \(s_i\) is a binary string of length \(k_i\text{.}\) Prove that the entropy of \(X\) is equal to the expected value of the length of \(s_X\text{.}\)
Let \(X\) and \(X'\) be independent and identically distributed discrete random variables. Prove that \(\mathbb{P}(X=X')\geq 2^{-H(X)}\text{.}\)
Let \(X,Y_1,Y_2\) and \(Z\) discrete random variables such that \(Y_1\) and \(Y_2\) are identically distributed. Prove that there exist random variables \(X',Y'\) and \(Z'\) such that all of the following hold simultaneously: (1) \((X',Y')\) has the same distribution as \((X,Y_1)\text{,}\) (2) \((Y',Z')\) has the same distribution as \((Y_2,Z)\) and (3) \(Z'\) is conditionally independentent of \(X'\) given \(Y'\text{.}\)
The binary entropy function\(h:[0,1]\to \mathbb{R}\) is defined by
The symmetric difference of two sets \(A\) and \(B\) is \(A\triangle B := (A\setminus B)\cup (B\setminus A)\text{.}\) For a set system \(\mathcal{A}\subseteq 2^{[n]}\text{,}\) define
For each \(i\in [n]\text{,}\) let \(p_i:=|\{A\in \mathcal{A}: i\in A\}|/|\mathcal{A}|\text{.}\) Prove that \(\text{ dist } (\mathcal{A}) = \sum_{i\in [n]}2p_i(1-p_i)\text{.}\)
Prove that \(2x(1-x)\geq -x\ln(x)-(1-x)\ln(x)+1/2-\ln(2)\) for all \(x\in (0,1)\text{.}\) (Your First Year Calculus should help you here).
Prove that every \(\mathcal{A}\subseteq 2^{[n]}\) satisfies \(\text{ dist } (\mathcal{A})\geq \frac{n}{2}-\ln\left(2^n/|\mathcal{A}\right)\text{.}\)
A family \(\mathcal{F}\subseteq 2^{[n]}\) is union-closed if, whenever \(A,B\in\mathcal{F}\text{,}\) we also have \(A\cup B\in\mathcal{F}\text{.}\) Our goal is to use a lemma about entropy (that we will not prove) to show that, for any union-closed family \(\mathcal{F}\neq\{\emptyset\}\text{,}\) there exists \(i\in [n]\) which is contained in a large number of sets of \(\mathcal{F}\text{.}\)
Let \(h(p)\) be the binary entropy function defined as in Exercise 9 in this section. Let \(p\in (0,1)\) and suppose that \(A\) is a random subset of \([n]\) obtained by including each \(i\in [n]\) in \(A\) with probability \(p\) independently of one another. Determine \(H(A)\) in terms of \(h(p)\) and \(n\text{.}\)
Suppose that \(A\) and \(B\) are two sets chosen independently of one another with the distribution described in question 10.a. Determine \(H(A\cap B)\) and \(H(A\cup B)\text{.}\)
Consider the following facts about the binary entropy function: Fact 1:\(h(p)\) is increasing for \(0\leq p\leq 1/2\) and decreasing for \(1/2\leq p\leq 1\text{.}\)Fact 2:\(h(p)=h(q)\) if and only if \(p=q\) or \(p=1-q\text{.}\) Using these two facts and the previous parts of the question, show that, if \(p\in (0,1)\) and \(A\) and \(B\) are two sets chosen independently of one another with the distribution described in question 10.a, then
\begin{equation*}
H(A\cup B)\begin{cases}>H(A) \amp \text{ if } p\lt \frac{3-\sqrt{5}}{2}\\ =H(A) \amp \text{ if } p=\frac{3-\sqrt{5}}{2},\\ \lt H(A) \amp \text{ if } p>\frac{3-\sqrt{5}}{2}. \end{cases}
\end{equation*}
Consider the following lemma of [253]: Lemma: If \(p\lt \frac{3-\sqrt{5}}{2}\) and \(A\) and \(B\) are independently chosen according to some distribution on \(2^{[n]}\) such that \(\mathbb{P}(A=\emptyset)\neq 1\) and \(\mathbb{P}(i\in A)\leq p\) for all \(i\in [n]\text{,}\) then
Explain how the previous part of the question shows that this lemma is tight.
Use the lemma in the previous part of the question to prove that every union-closed family \(\mathcal{F}\neq \{\emptyset\}\) there exists \(i\in [n]\) such that \(i\) is contained in at least \(\left(\frac{3-\sqrt{5}}{2}\right)|\mathcal{F}|\) elements of \(\mathcal{F}\text{.}\)Hint:Lemma 7.1.4 is useful.
Our aim in this exercise is to derive Theorem 7.3.5 from Corollary 7.3.4. Let \(G\) be a graph and let \(A\) be its adjacency matrix.
Let \(\mathcal{H}\) be the collection of all subgraphs of \(H\) of \(G\) such that \(V(H)=V(G)\) and \(H\) is a disjoint union of cycles and edges such that every vertex has degree at least one. For each \(H\in\mathcal{H}\text{,}\) let \(s(H)\) be the number of components of \(H\) with more than two vertices. Show that
A Hamiltonian cycle in a graph \(G\) is a cycle in \(G\) which contains every vertex of \(G\text{.}\) Prove that, if \(G\) is a bipartite graph with bipartition \((A,B)\text{,}\) then the number of Hamiltonian cycles in \(G\) is at most
Hint: Consider the permanent of the matrix \(A+I\) where \(A\) is the adjacency matrix of \(G\) and \(I\) is the identity.
Compute \(t(T,G)\) for any tree \(T\) on \(k\) vertices and any \(d\)-regular graph \(G\) on \(n\) vertices. Rewrite this as \(t(K_2,G)\) raised to some power.
Let \(S_k\) be the \(k\)-vertex “star” graph \(K_{1,k-1}\text{.}\) Our goal is to prove the following theorem of Sidorenko: If \(H\) is a connected \(k\)-vertex graph, then \(\hom(H,G)\leq \hom(S_k,G)\) for every graph \(G\text{.}\)
Show that, if \(H'\) is a subgraph of \(H\text{,}\) then \(\hom(H,G)\leq \hom(H',G)\text{.}\) Conclude that the theorem of Sidorenko is true if and only if it is true in the case that \(H\) is a tree.
Let \(T\) be a tree, let \(f\) be a uniformly random homomorphism from \(T\) to \(G\) and let \(X_v=f(v)\) for all \(v\in V(T)\text{.}\) Let \(v,x\in V(T)\) and suppose that there is a neighbour \(y\) of \(x\) such that the following holds for every leaf \(u\) adjacent to \(v\text{:}\)
Let \(T'\) be the tree obtained by taking all leaves that are adjacent to \(v\) and making them adjacent to \(x\) instead. Show that \(\hom(T,G)\leq \hom(T',G)\text{.}\)
Prove the theorem. Hint: Show that if \(T\) is a tree that is not a star, then there exists a tree \(T'\) with more leaves than \(T\) such that \(\hom(T,G)\leq \hom(T',G)\text{.}\)
Given a graph \(H\text{,}\) the \(2\)-blowup of \(H(2)\) of \(H\) is the graph with vertex set \(V(H)\times \{1,2\}\) where, for \(u,v\in V(H)\) and \(i,j\in \{1,2\}\text{,}\) the vertices \((u,i)\) and \((v,j)\) are adjacent if and only if \(uv\in E(H)\text{.}\) Using a similar argument to that in the proof of Theorem 7.4.1, prove that, if \(T\) is a tree, then
Hint: Suppose there is a graph \(G\) such that \(t(H,G)\lt t(F,G)^\alpha\text{.}\) Use the result of Exercise 13 from Section 4.7.
Our goal is to give a proof of the following theorem of Conlon, Fox and Sudakov [58]: Theorem: If \(H\) is a bipartite graph with bipartition \((A,B)\) and there is a vertex \(x\in A\) such that \(N(x)=B\text{,}\) then, for every graph \(G\text{,}\)
Let \(f_x:\{x\}\cup B\to V(G)\) be a random function sampled as follows:
\(f_x(x)\) is a random vertex of \(G\) chosen with probability proportional to its degree, as in the proof of Proposition 7.4.3.
for each \(u\in B\text{,}\)\(f_x(u)\) is a uniformly random neighbour of \(f_x(x)\text{.}\)
Given \(z\in A\setminus\{x\}\text{,}\) let \(f_z:\{z\}\cup N(z)\to V(G)\) be a random function chosen in the following way. First, sample \(f_z:\{z\}\cup B\to V(G)\) according to the same distribution as \(f_x\text{,}\) but with \(z\) in the place of \(x\text{,}\) independently of \(f_x\text{.}\) While there exist \(y\in N(z)\) such that \(f_z(y)\neq f_x(y)\text{,}\) resample \(f_z\) in the same way. Once \(f_z(y)=f_x(y)\) for all \(y\in N(z)\text{,}\) stop and restrict the domain of the \(f_z\) to \(\{z\}\cup N(z)\text{.}\)
For and \(z\in A\setminus\{x\}\text{,}\) vertex \(v\in V(G)\) and tuple \((u_y:
y\in N(v))\in V(G)^{N(v)}\text{,}\) prove that
\begin{equation*}
\mathbb{P}(f_z(z)=v\mid f_z(y)=u_y\text{ for all } y\in N(z))=\mathbb{P}(f_x(x)=v\mid f_x(y)=u_y\text{ for all } y\in N(z))\text{.}
\end{equation*}
Let \(H'\) be a graph obtained from \(H\) by adding \(|E(H)|-|V(H)|\) isolated vertices. Find a distribution on the set of homomorphisms from \(H'\) to \(G\) with entropy at least \(|E(H)|\cdot \log(\hom(K_2,G))\text{.}\)
Prove the theorem.
A “generalized theta graph” is obtained by taking two “terminal” vertices \(s\) and \(t\) and adding paths between them. It is said to be “even” if all the paths have an even number of edges. Prove that if \(H\) is an even generalized theta graph, then, for any graph \(G\text{,}\)
A digraph is a pair \((V,A)\) where \(V\) is a set of vertices and \(A\) is a set of ordered pairs of vertices called arcs. That is, \(A\subseteq V^2\text{.}\) The way that we depict a digraph is by drawing its vertices as points and drawing an arrow from vertex \(u\) to vertex \(v\) if \((u,v)\in A\text{.}\) A digraphHom from a digraph \(H\) to a digraph \(D\) is a mapping \(f:V(H)\to V(D)\) such that \((f(u),f(v))\in A(D)\) whenever \((u,v)\in A(H)\text{.}\) We define \(\Hom(H,D)\text{,}\)\(\hom(H,D)\) and \(t(H,D)\) analogously to the case of graphs. Let \(Vee\) and \(C_3\) be the digraphs depicted below.
The goal of this problem is to show that every digraph \(D\) satisfies \(\hom(Vee,D)\geq \hom(C_3,D)\) and that this inequality is tight.
For each \(n\geq1\text{,}\) let \(D_{n}\) be the digraph with vertex set \(V_1\cup V_2\cup V_3\) such that \(|V_i|=n\) for each \(1\leq i\leq 3\) and \((u,v)\in A(D_{n})\) if and only if \((u,v)\in V_1\times V_2\text{,}\)\((u,v)\in V_2\times V_3\) or \((u,v)\in V_3\times V_1\text{.}\) Prove that
Let \(D\) be any digraph such that \(\hom(C_3,D)\geq1\text{.}\) Let \(F\) be a uniformly random element of \(\Hom(C_3,D)\text{.}\) For \(i\in\{1,2,3\}\text{,}\) let \(X_i\) be the random variable \(F(v_i)\text{.}\) Using Lemma 7.1.9 and Lemma 7.1.11, prove that
