Note: Every graph with at least one vertex satisfies \(\alpha(G)\geq1\text{.}\) So, by taking \(c\) very small, the bound holds trivially for small \(n\) and so you may assume \(n\) is larger than any constant that you wish.
Hint 1: You may use the fact that every \(2\)-regular graph is a disjoint union of cycles (without proof). Hint 2: Use Corollary 4.3.6 and Exercise 12 from Section 4.7.
Let \(H_{ind}\) be the graph on two vertices obtained from the complete graph \(K_2\) by adding a “loop” on one of the vertices. That is, one of the vertices is adjacent to itself. Prove that, for every graph \(G\text{,}\)\(\hom(G,H_{ind})\) is equal to the number of independent sets in \(G\text{.}\)
Prove that every \(2\)-regular graph \(G\) on \(n\) vertices has at most \(7^{n/4}\) independent sets. Note: You’re not allowed to apply any theorems in later chapters of these notes!
Let \(H_{ind}\) be the looped graph with vertex set \(\{0,1\}\text{,}\) a loop at \(0\text{,}\) and an ordinary edge between \(0\) and \(1\text{,}\) but no loop at \(1\text{.}\) For a graph \(G\text{,}\) let \(i(G)\) denote the number of independent sets in \(G\text{.}\)
For integers \(a,b,c\geq0\text{,}\) let \(H_{a,b,c}\) be the multigraph on two vertices in which one of the vertices has \(a\) loops, the other has \(c\) loops and there are \(b\) edges between the two vertices.
Prove that, if \(ac\geq b^2\text{,}\) then every \(2\)-regular graph \(G\) on \(n\) vertices satisfies
\begin{equation*}
\hom(G,H_{a,b,c})\leq \left(a^3 + 3 a b^2 + 3 b^2 c + c^3\right)^{n/3}\text{.}
\end{equation*}
Also, show that this is tight whenever \(n\equiv 0\bmod 3\text{.}\)
Obtain a tight upper bound on \(\hom(G,H_{a,b,c})\) analogous to the bound in question 6.a for a \(2\)-regular graph \(G\) in the case that \(ac\lt b^2\text{.}\)
Obtain a tight lower bound (as opposed to an upper bound) on \(\hom(G,H_{a,b,c})\) of a similar type as the bounds in question 6.a and question 6.b for a \(2\)-regular graph \(G\) in the case that \(ac\lt b^2\text{.}\)
Obtain a lower bound on \(\hom(G,H_{a,b,c})\) analogous to the bound in question 6.c for a \(2\)-regular graph \(G\) in the case that \(ac\geq b^2\text{.}\) Is it tight?
For \(1\leq d\leq n-1\) such that \(nd\) is even, let \(G\) be a \(d\)-regular graph with \(n\) vertices.
Prove that every independent set in \(G\) has cardinality at most \(n/2\text{.}\) Describe a large family of tight examples (i.e. for infinitely different values of \(d\) and \(n\)).
Show that if \(G\) has an independent set of cardinality at least \(n/2 - t\text{,}\) then there is a set \(E'\) of at most \(td\) edges such that \(G\setminus E'\) is bipartite.
Container Lemma. For every \(\varepsilon>0\text{,}\) there exists \(n_0(\varepsilon)\) such that if \(n\geq n_0(\varepsilon)\text{,}\) then there exists a collection \(\mathcal{G}\) of graphs with vertex set \([n]\) such that:
Let \(q\geq2\text{,}\) let \(G\) be a \(d\)-regular graph on \(n\) vertices and let \(m\) be a positive integer. For each independent set \(S\) of \(G\text{,}\) let \(F_S\) and \(C_S\) be defined as in the proof of Theorem 6.2.3 with respect to \(G\) and \(m\text{.}\) Also, let \(g\) be the mapping as in the proof of Theorem 6.2.3.
Show that, if \(f\) is a proper \(q\)-colouring of \(G\text{,}\) then
Say that the fingerprint of a proper \(q\)-colouring \(f\) of \(G\) is the vector of sets \((F_1,\dots,F_q)\) such that \(F_c\) is the fingerprint of \(F_{f^{-1}(c)}\) for all \(1\leq c\leq q\text{.}\) Given a vector \((F_1,\dots,F_q)\) of subsets of \(V(G)\) of cardinality at most \(n/m\) and a vertex \(v\in V(G)\text{,}\) let \(\eta_{F_1,\dots,F_q}(v)\) be the number of \(c\) such that \(1\leq c\leq q\) and \(v\in g(F_c)\text{.}\) Prove that the number of proper \(q\)-colourings with fingerprint \((F_1,\dots,F_q)\) is at most
Use the AM-GM Inequality (look it up if you don’t know it) to show that the number of proper \(q\)-colourings with fingerprint \((F_1,\dots,F_q)\) is at most
Complete the proof of Theorem 6.2.5. Hint 1: Let \(\varepsilon>0\) and choose \(m\) large enough with respect to \(q\) and \(\varepsilon\) so that the inequality \((em)^q \lt \left(1+\frac{2\varepsilon}{3}\right)^{m}\) holds. Hint 2: Now, choose \(d\) large enough with respect to \(m\) so that \(m/2d\) is less than \(\varepsilon/3\text{.}\)
Find a graph \(G\) such that the sequence \((\alpha(G^k)^{1/k})_{k=1}^{\infty}\) is not monotone increasing. Hint: Choose a graph for which you already know the exact value of \(\Theta(H)\text{.}\)
Prove that, if \(G\) is a self-complementary graph, then \(\alpha(G\boxtimes G)\geq |V(G)|\text{.}\) Conclude that every self-complementary graph \(G\) satisfies \(\Theta(G)\geq \sqrt{|V(G)|}\text{.}\)
For two vectors \(x\in \mathbb{R}^n\) and \(y\in \mathbb{R}^m\text{,}\) let \(x\otimes y\) be the vector \((x_1y_1,\dots,
x_1y_m, x_2y_1,\dots,x_ny_m)^T\) in \(\mathbb{R}^{nm}\text{.}\) We call \(x\otimes y\) the tensor product of \(x\) and \(y\text{.}\)
Prove that, for any vectors \(x,w\in \mathbb{R}^n\) and \(y,z\in \mathbb{R}^m\text{,}\) we have \(\langle x\otimes y,w\otimes z\rangle = \langle x,w\rangle\langle y,z\rangle\text{.}\)
Let \(G\) be a graph with \(n\) vertices, let \(f\) be an orthonormal representation of \(G\) and let \(h\) be an orthonormal representation of \(\overline{G}\text{.}\)
Hint: Take \(f\) to be an orthogonal representation of \(G\) and \(c\in \mathbb{S}_{n-1}\) so that \(\max_{v\in V(G)}\frac{1}{\langle f(v),c\rangle^2}=\vartheta(G)\text{.}\)
A fractional independent set of a graph \(G\) is a vector \((w_v:
v\in V(G))\) such that \(0\leq w_v\leq1\) for all \(v\in V(G)\) and \(\sum_{v\in S}w_v\leq 1\) for every clique \(S\) in \(G\text{.}\) The fractional independence number of \(G\text{,}\) denoted \(\alpha^*(G)\text{,}\) is the maximum of \(\sum_{v\in V(G)}w_v\) over all fractional independent sets \((w_v: v\in V(G))\text{.}\)
Prove that \(\alpha^*(G)\leq \chi(\overline{G})\) for every graph \(G\text{.}\)
Let \(\mathcal{I}(G)\) be the set of independent sets in a graph \(G\text{.}\) A fractional colouring of a graph \(G\) is a vector \((y_I: I\in\mathcal{I}(G))\) such that \(0\leq y_I\leq 1\) for all \(I\in\mathcal{I}(G)\) and \(\sum_{I: v\in I}y_I\geq 1\) for all \(v\in V(G)\text{.}\) The fractional chromatic number of \(G\text{,}\) denoted \(\chi^*(G)\text{,}\) is the minimum of \(\sum_{I\in\mathcal{I}(G)}y_I\) over all fractional colourings of \(G\text{.}\) Prove that \(\alpha^*(G)\leq \chi^*(\overline{G})\) for every graph \(G\text{.}\)
