Let \(k\geq2\) and let \(\mathcal{F}\subseteq \binom{[n]}{k}\) be nonempty. Let \(\partial\mathcal{F}\) denote the lower shadow of \(\mathcal{F}\text{.}\) Choose a random ordered \(k\)-tuple
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,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 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{.}\)
Let the edges of a graph \(G\) be coloured red, blue and green. Let \(G_R\text{,}\)\(G_B\) and \(G_G\) be the spanning subgraphs consisting of the red, blue and green edges, respectively. Let \(T\) be the edge-coloured triangle on vertices \(1,2,3\) in which \(12\) is red, \(23\) is blue and \(31\) is green. Prove that
Use the fact that \((X_1,X_2)\) is always a red edge, \((X_2,X_3)\) is always a blue edge, and \((X_3,X_1)\) is always a green edge to prove the desired inequality.
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 11.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 11.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
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.4.5 from Corollary 7.4.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
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.5.1, prove that, if \(T\) is a tree, then
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{,}\)
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{.}\)
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
Let \(G\) be an \(n\)-vertex graph whose edges are coloured red and blue. Let \(P^A_3\) be the edge-coloured path \(v_0v_1v_2v_3\) in which \(v_0v_1\) and \(v_2v_3\) are red, while \(v_1v_2\) is blue. The goal of this exercise is to prove that
Let \(H\) be the following edge-coloured forest. Start with the path \(v_0v_1v_2v_3\) coloured red-blue-red as above. Add two new red leaves and one new blue leaf adjacent to \(v_1\text{.}\) Add two new red leaves and one new blue leaf adjacent to \(v_2\text{.}\) Finally, add two isolated vertices.
For a vertex \(u\in V(G)\text{,}\) let \(d_R(u)\) and \(d_B(u)\) be the number of red and blue edges incident to \(u\text{,}\) respectively. Prove that
Let \(f\) be a uniformly random element of \(\operatorname{Hom}(P^A_3,G)\text{,}\) and write \(X_i=f(v_i)\) for \(0\leq i\leq 3\text{.}\) Use entropy and conditional independence to construct a random homomorphism from \(H\) to \(G\) whose entropy is at least
Hint: Map each vertex of \(H\) to the vertex of \(P^A_3\) in the same column: the three vertices in the \(v_0\)-column map to \(v_0\text{,}\) the three vertices in the \(v_1\)-column map to \(v_1\text{,}\) and so on. This map from \(H\) to \(P^A_3\) covers every vertex and every edge of \(P^A_3\) exactly three times. Build the random homomorphism from \(H\) to \(G\) by gluing together conditionally independent copies of the relevant conditional distributions from the random homomorphism \(f\text{.}\)
