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.
Prove that the chromatic number of a triangle-free graph on \(n\) vertices is \(O(\sqrt{n})\text{.}\)
Prove that, for any graph \(H\) and any \(2\)-regular triangle-free graph \(G\) on \(n\) vertices,
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 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! 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.
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.
Show that the number of edges of \(G\) contained in any set of at least \(n/2 + t\) vertices is at least \(td\text{.}\)
Let \(d\geq1\text{,}\) let \(n\) be divisible by \(2d\) and let \(G\) be a disjoint union of \(n/(2d)\) copies of \(K_{d,d}\text{.}\)
How many proper \(2\)-colourings does \(K_{d,d}\) have? How many proper \(2\)-colourings does \(G\) have?
How many proper \(3\)-colourings does \(K_{d,d}\) have? (Careful!) How many proper \(3\)-colourings does \(G\) have?
Let \(G\) be a \(d\)-regular bipartite graph with bipartition \((A,B)\) where \(|A|=|B|=n\text{.}\)
For \(0\leq k\leq n\text{,}\) prove that the number of independent sets \(S\) of \(G\) such that \(|S\cap A|=k\) is at least
Consider the following lemma of Balogh, Morris and Samotij: Lemma: For every \(\varepsilon>0\) 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
\(|\mathcal{G}|\leq 2^{\varepsilon n^2}\text{,}\)
every graph in \(\mathcal{G}\) has at most \((1/4+\varepsilon)n^2\) edges and
for every triangle-free graph \(G\) with vertex set \([n]\text{,}\) there exists \(G'\in\mathcal{G}\) such that \(G\subseteq G'\text{.}\)
Use this lemma to prove that the number of triangle-free graphs on \(n\) vertices is at most
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{.}\)
Prove that, for any graphs \(G\) and \(H\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 \(\Theta(G)=\alpha(G)\) for every bipartite graph \(G\text{.}\)Hint: Look up Kőnig’s Theorem and use it.
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{.}\)
Prove that, if \(H\) is a spanning subgraph of \(G\text{,}\) then \(\vartheta(G)\leq \vartheta(H)\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{.}\)
Prove that \(\vartheta(G\boxtimes H)\leq \vartheta(G)\vartheta(H)\) for any two graphs \(G\) and \(H\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{.}\)
Prove that \(\{f(v)\otimes h(v):v\in V(G)\}\) is an orthonormal system.
Prove that, for any two vectors \(c,d\in \mathbb{R}^n\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{.}\)
Prove that \(\vartheta(G)\vartheta(\overline{G})\geq n\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{.}\)
Prove that \(\vartheta(G)\leq \chi^*(\overline{G})\) for every graph \(G\text{.}\)
