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{.}\)
Prove property d of Lemma 7.1.13. Note that the case when \(X\) and \(Y\) are independent was already covered in Example 7.1.10. What remains to be shown is that \(H(X\mid Y)\lt H(X)\) whenever \(X\) and \(Y\) are not independent.
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 6 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 7.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 7.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:part a of Lemma 7.1.13 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.
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 11 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 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 property b and property d of Lemma 7.1.13, prove that