Show that, if \(G\) is a triangle-free graph, then \(\alpha(G)\geq \Delta(G)\text{.}\)
Prove that, for every graph \(G\text{,}\)
\begin{equation*}
\alpha(G)\geq \sum_{v\in V(G)}\frac{1}{d(v)+1}\text{.}
\end{equation*}
For \(r\geq2\text{,}\) suppose that \(G\) is a graph which does not contain \(K_r\text{.}\) Prove that there exists a graph \(G'\) with \(V(G')=V(G)\) such that \(\chi(G')\leq r-1\) and
\begin{equation*}
d_{G'}(v)\geq d_G(v)
\end{equation*}
for all \(v\in V(G)\text{.}\) Deduce Turán’s Theorem. Hint: Consider a vertex of maximum degree. Induct on \(r\text{.}\)
A \(k\)-cycle in a digraph is a sequence of \(k\) vertices \((v_0,v_1,\dots,v_{k-1})\) such that the edge \(v_iv_{i+1}\) is oriented from \(v_i\) to \(v_{i+1}\) for all \(0\leq i\leq k-1\) (viewing indices modulo \(k\)). Prove that the number of \(3\)-cycles in every digraph on \(n\) vertices is at most \(\frac{1}{4}\binom{n+1}{3}\text{.}\) Hint: Without loss of generality, the digraph is a tournament.
A tournament is said to be transitive if the vertices can be ordered \(v_1,v_2,\dots,v_n\) such that, if \(i\lt j\text{,}\) then the edge \(v_iv_j\) is oriented from \(v_i\) to \(v_j\text{.}\) Prove that every tournament on \(n\) vertices contains a transitive tournament with at least \(\lfloor \log_2(n)\rfloor +1\) vertices.
Given \(n\) irrational numbers \(x_1,\dots,x_n\text{,}\) let \(f(x_1,\dots,x_n)\) be the number of unordered pairs \(\{x_i,x_j\}\) such that \(x_i+x_j\) is rational. Determine the maximum value of \(f(x_1,\dots,x_n)\) among all choices of \(x_1,\dots,x_n\in \mathbb{R}\setminus \mathbb{Q}\text{.}\)
In the proof of Mantel’s Theorem, we showed that \(\sum_{v\in V(G)}\degree(v)^2\leq |E(G)||V(G)|\) for any triangle-free graph \(G\text{.}\) Prove that, for any graph \(G\) (with or without triangles),
\begin{equation*}
\sum_{v\in V(G)}\degree(v)^2\leq 2|E(G)|(|V(G)|-1)\text{.}
\end{equation*}
For which graphs \(G\) is this inequality tight?
A permutation of \([n]\) is a bijection \(\pi:[n]\to[n]\text{.}\) We often express a permutation \(\pi\) as a sequence \((\pi(1),\dots,\pi(n))\text{.}\) For example, \((1,3,2)\) is a permutation of \([3]\text{.}\) The displacement of a permutation \(\pi\) of \([n]\) is defined to be \(\sum_{i=1}^n|\pi(i)-i|\text{.}\) Prove that every permutation \(\pi\) of \([n]\) has displacement at most \(n^2/2\text{.}\)
Given a permutation \(\sigma\) of \([k]\) and a permutation \(\pi\) of \([n]\) where \(k\leq n\text{,}\) a copy of \(\sigma\) in \(\pi\) is a subsequence \((a(1),\dots,a(k))\) of \((\pi(1),\dots,\pi(n))\) such that \(a(i)\lt a(j)\) if and only if \(\sigma(i)\lt \sigma(j)\) for \(1\leq i,j\leq k\text{.}\) Let \(\#(\sigma,\pi)\) denote the number of copies of \(\sigma\) in \(\pi\) and define \(\#(\sigma,n)\) to be the maximum of \(\#(\sigma,\pi)\) over all permutations \(\pi\) of \([n]\text{.}\) The packing density of \(\sigma\) is
\begin{equation*}
p(\sigma):=\lim_{n\to\infty} \frac{\#(\sigma,n)}{\binom{n}{k}}\text{.}
\end{equation*}
Prove that \(p(\sigma)\) is well-defined (i.e. that the limit exists).
By coming up with an explicit construction of permutations \(\pi_1,\pi_2,\dots\) whose lengths tend to infinity, prove a lower bound on \(p(1,3,2)\text{.}\) Try to make this lower bound as large as you can.
(Not easy!) Prove that your construction from the previous part is optimal.
Let \(M_k\) be the graph consisting of a matching with \(k\) edges. Prove that
\begin{equation*}
\ex(n,M_k) = \binom{k-1}{2}+(k-1)(n-k+1)
\end{equation*}
for all \(n\geq 3k\text{.}\)
Prove that the maximum number of edges in a complete \((r-1)\)-partite graph with \(n\geq r-1\) vertices is attained with all parts are of cardinality \(\lfloor n/(r-1)\rfloor\) or \(\lceil n/(r-1)\rceil\text{.}\) }
Given graphs \(F\) and \(H\text{,}\) let \(\ex(F,H)\) be the maximum number of edges in a subgraph of \(F\) which does not contain a copy of \(H\text{.}\) Let \(Q_d\) be the \(d\)-dimensional hypercube; i.e. the graph with vertex set \(\{0,1\}^d\) in which two vertices are adjacent if they differ in a unique coordinate. Prove that
\begin{equation*}
\ex(Q_d,C_4)\geq |E(Q_d)|/2\text{.}
\end{equation*}
Given a graph \(G\) and an edge \(uv\) of \(G\text{,}\) to contract the edge \(uv\) means to replace \(u\) and \(v\) by a single vertex which is adjacent to every vertex that is adjacent to at least one of \(u\) or \(v\text{.}\) We say that \(H\) is a minor of \(G\) if it is possible to obtain \(H\) from \(G\) by sequentially contracting edges and deleting vertices or edges.
Suppose that \(c\) is an integer and \(G\) is a graph with \(|E(G)|\geq c|V(G)|\) such that every minor \(H\) of \(G\) satisfies \(|E(H)|\lt c|V(H)|\text{.}\) Prove that any two vertices of \(G\) have at least \(c\) common neighbours.
Show that every graph \(G\) satisfying \(|E(G)|\geq 2^{k-2}|V(G)|\) contains \(K_k\) as a minor. Hint: Induction on \(k\) and \(|V(G)|\text{.}\)
Suppose that you have a TV remote control and a box of 8 batteries. The remote requires 2 charged batteries in order to function—i.e. if one or more of the batteries is dead, then it will not work. You know that 4 of the batteries in the box are charged and 4 are dead, but you do not know which are which. How many pairs of batteries do you need to test in order to guarantee that one of the tests is successful?
Compute \(\ex(n,C_5)\) for \(n\in\{1,2,3,4,5,6\}\text{.}\)
Show that, for any graph \(H\text{,}\) the sequence \(\ex(n,H)/\binom{n}{2}\) for \(n\geq2\) is non-increasing.
For each \(n\text{,}\) let \(g(n)\) be the maximum number of edges in a graph \(G\) on \(n\) vertices such that the edges of \(G\) can be coloured in two colours in such a way that there are no monochromatic triangles.
Prove that \(\frac{g(n)}{\binom{n}{2}}\) converges as \(n\to\infty\text{.}\)
Determine \(\lim_{n\to\infty}\frac{g(n)}{\binom{n}{2}}\text{.}\)
Show that there exists a graph \(H\) and constants \(C>0\) and \(n_0\in\mathbb{N}\) such that \(\chi(H)=3\) and, for every \(n\geq n_0\text{,}\)
\begin{equation*}
\ex(n,H)\geq \frac{n^2}{4} + Cn^{3/2}\text{.}
\end{equation*}
Hint 1: Example 3.4.4 may be helpful.
Hint 2: For every integer
\(m\geq1\text{,}\) there is a prime between
\(m\) and
\(2m\) (this is known as Bertrand’s Postulate).
For positive integers \(n,s,t\text{,}\) let \(z(n,s,t)\) be the maximum number of edges in a subgraph of \(K_{n,n}\) without a copy of \(K_{s,t}\text{.}\) Prove that \(2\ex(n,K_{s,t})\leq z(n,s,t)\leq \ex(2n,K_{s,t})\text{.}\)
Let \(p\) be a prime and let \(G_p\) be a graph with vertex set
\begin{equation*}
V(G_p):=\{(x,y,z)\in \mathbb{Z}_p^3: x\neq y, x\neq z, y\neq z\}
\end{equation*}
where \((x_1,y_1,z_1)\) is adjacent to \((x_2,y_2,z_2)\) if and only if
\begin{equation*}
(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2\equiv 1\bmod p\text{.}
\end{equation*}
Determine \(|V(G_p)|\) as a function of \(p\) for all \(p\text{.}\)
Prove that every vertex in \(G_p\) has degree \(p^2-p\text{.}\)
Show that \(G_p\) does not contain a copy of \(K_{3,3}\text{.}\)
Conclude that
\(\ex(K_{3,3},n)=\Theta(n^{5/3})\text{.}\) (Hint: Use Bertrand’s Postulate; see the second hint to
Exercise 19 in this section).
Determine \(\ex(n,C_n)\) for all \(n\geq3\text{.}\) Hint: Look up Ore’s Theorem on Hamilton cycles in graphs.
Prove that, for each \(k\geq2\) and \(n\geq1\text{,}\)
\begin{equation*}
\ex(n,\{C_3,C_4,C_5,\dots,C_{2k}\})\leq n\left(n^{1/k}+1\right)\text{.}
\end{equation*}
Determine \(\ex\left(n,\left\{C_{2k}:k\geq2\right\}\right)\) for every \(n\text{.}\)
Let \(G\) be a bipartite graph with bipartition \((A_1,A_2)\) and let \(d_i=|E(G)|/|A_i|\) for \(i\in\{1,2\}\text{.}\) Prove that there is a subgraph \(G'\) of \(G\) such that \(|E(G')|\geq |E(G)|/2\) and, for \(i\in\{1,2\}\text{,}\) every vertex \(v\in A_i\cap V(G')\) has degree at least \(d_i/4\) in \(G'\text{.}\)
A tree is a connected graph with no cycles. Show that, for every tree \(T\text{,}\) there exist a constant \(c=c(T)\geq0\) such that \(\ex(n,T)\leq cn\) for all \(n\geq1\text{.}\) Hint: Every tree on at least 2 vertices has a vertex of degree one (called a leaf).
The friendship graph \(F_m\) is the graph obtained by taking \(m\) disjoint copies of \(K_2\) and adding an extra vertex adjacent to all other vertices. For example, \(F_1\) is a triangle and \(F_2\) is two triangles in which one vertex from each triangle is glued together on a common vertex. Prove that, for every \(m\geq1\text{,}\) there exists \(c(m)\) such that if \(G\) is an \(n\)-vertex graph with at least \(c(m)n\) triangles, then it contains a copy of \(F_m\text{.}\)
Determine \(\ex(n,P_k)\) for every \(n\) and \(k\text{.}\)
Let \(G\) be a \(C_4\)-free bipartite graph with parts of sizes \(n\geq1\) and \(m\geq1\text{.}\) Show that \(G\) has at most \(nm^{1/2}+m\) edges.
A set \(A\subseteq \mathbb{N}\) is called a Sidon set if \(a,b,c,d\in A\) such that \(a+b=c+d\text{,}\) then \(\{a,b\}=\{c,d\}\text{.}\)
Prove that if \(A\) is a Sidon set such that \(A\subseteq [n]\text{,}\) then
\begin{equation*}
|A|+\binom{|A|}{2}\leq 2n-1\text{.}
\end{equation*}
Conclude that \(|A|\lt 2\sqrt{n}\text{.}\)
Prove that, if \(A\subseteq [n]\) is a Sidon set and \(|A|\lt n^{1/3}\text{,}\) then there exists \(x\in [n]\setminus A\) such that \(A\cup\{x\}\) is a Sidon set.
Let \(A\subseteq [n]\) be a Sidon set. Let \(G\) be a graph on vertex set \(\{u_1,\dots,u_n\}\cup\{v_1,\dots,v_{2n}\}\) where \(u_iv_j\in E(G)\) if there exists \(a\in A\) such that \(i+a=j\text{.}\) Show that \(G\) does not contain any \(4\)-cycles.
Let \(G\) be a graph with vertex set \(\{v_1,\dots,v_n\}\) and let \(x_1,\dots,x_n\) be \(n\) real variables. Let \(x=(x_1,\dots,x_n)\in \mathbb{R}^n\text{.}\) Define
\begin{equation*}
f(x) = \sum_{v_iv_j\in E(G)}x_ix_j\text{.}
\end{equation*}
Let \(S=\{x\in [0,1]^n: x_1+\cdots+x_n=1\}\) and define \(\rho:=\max_{x\in S}f(x)\text{.}\)
Prove that the maximum of \(f(x)\) for \(x\in S\) is attained when the non-zero coordinates of \(x\) correspond to the vertices of a clique in \(G\text{.}\) In other words, prove that there exists a clique \(C\subseteq\{v_1,\dots,v_n\}\) and a vector \(x\in S\) such that \(x_i=0\) for all \(v_i\notin S\) and \(f(x)=\rho\text{.}\)
Prove that \(\rho=\frac{1}{2}\left(1-\frac{1}{r}\right)\) where \(r\) is the number of vertices in the largest clique in \(G\text{.}\)
Prove that there exists a vector \(x\in S\) such that \(x_i>0\) for all \(i\) and \(f(x)=\rho\) if and only if \(G\) is a complete multipartite graph.
Let \(S\) be a set of \(n\) points in a circular region with radius \(1\text{.}\) Prove that the number of pairs \(x,y\in S\) such that the Euclidean distance from \(x\) to \(y\) is at least \(\sqrt{2}\) is at most \(n^2/3\text{.}\)
Let \(f(n)\) be the minimum size of a family \(\mathcal{F}\) of subsets of \([n]\) such that, for every set \(S\subseteq [n]\) with \(|S|\leq 3\text{,}\) there exists \(A,B\in \mathcal{F}\) such that \(A\cup B=S\) (note: we allow the case \(A=B\)). Prove that \(f(n)=1+n+\binom{n}{2}-\left\lfloor\frac{n^2}{4}\right\rfloor\text{.}\)
-
An \(r\)-uniform hypergraph is r-partite if its vertices can be partitioned into \(r\) sets \(A_1,\dots,A_r\) such that \(|e\cap A_i|=1\) for every \(e\in E\) and \(1\leq i\leq r\text{.}\) Prove that every \(r\)-uniform hypergraph \(H\) has an \(r\)-partite subhypergraph with at least \(\frac{r!}{r^r}|E(H)|\) hyperedges.
Note, a \(r\)-uniform hypergraph is a pair \(H=(V,E)\) where \(v\) is a set of vertices and \(E\subseteq \binom{V}{r}\) is a collection of hyperedges. That is, it is a generalization of graphs where we take our edges to have \(r\) elements instead of just \(2\text{.}\)
For \(r\geq2\) and \(n\geq1\text{,}\) the complete hypergraph \(r\)-uniform hypergraph on \(n\) vertices, denoted Knr, is the hypergraph with vertex set \([n]\) and edge set \(\binom{[n]}{r}\text{.}\) Here, we analyze a well-known construction in the area of hypergraph Turán problems. Let \(n\) be divisible by \(3\) and let \(V_0,V_1,V_2\) be disjoint sets of cardinality \(n/3\text{.}\) Define \(V:= V_0\cup V_1\cup V_2\) and let \(H\) be a \(3\)-uniform hypergraph with vertex set \(V\) such that \(e\in E(H)\) if and only if either (i) \(|e\cap V_i|=1\) for all \(i\in\{0,1,2\}\) or (ii) there exists \(i\in \{0,1,2\}\) such that \(|e\cap V_i|=2\) and \(|e\cap V_{i+1}|=1\text{,}\) where the indices are viewed modulo \(3\text{.}\)
Prove that \(|E(H)|\sim \frac{5}{9}\binom{n}{3}\text{.}\)
Prove that \(H\) does not contain a copy of \(K_4^{(3)}\text{.}\)
Our goal is to show that if \(H\) is a \(3\)-uniform hypergraph on \(n\) vertices with no copy of \(K_4^{(3)}\text{,}\) then \(|E(H)|\leq \frac{2n-3}{9}\binom{n}{2}\text{.}\)
For distinct \(x,y\in V(H)\text{,}\) let \(N(x,y) = \{z\in V(H): \{x,y,z\}\in E(H)\}\) and \(d(x,y)=|N(x,y)|\text{.}\) Prove that if \(\{u,v,w\}\in E(H)\text{,}\) then \(N(u)\cap N(v)\cap N(w)=\emptyset\text{.}\) Use this to show that, if \(\{u,v,w\}\in E(H)\text{,}\) then \(d(u)+d(y)+d(z)\leq 2n-3\text{.}\)
By summing over all \(e\in E(H)\text{,}\) prove that
\begin{equation*}
\sum_{\{x,y\}\in \binom{V(H)}{2}} d(x,y)^2 \leq (2n-3)|E(H)|\text{.}
\end{equation*}
Prove that the left side of the inequality in the previous part of the question is at least \(\frac{9|E(H)|^2}{\binom{n}{2}}\text{.}\) Conclude that \(|E(H)|\leq \frac{2n-3}{9}\binom{n}{2}\text{.}\)
For \(r\geq2\text{,}\) \(k\geq 1\) and \(m\geq1\text{,}\) let \(K_{k}^{(r)}(m)\) be an \(r\)-uniform hypergraph whose vertices are partitioned into \(k\) classes \(A_1,A_2,\dots,A_k\text{,}\) each of cardinality \(m\text{,}\) and whose hyperedges are precisely the sets \(e\) of cardinality three such that \(|e\cap A_i|\leq1\) for \(1\leq i\leq n\text{.}\) Given an \(r\)-uniform hypergraph \(H\) and \(n\geq1\text{,}\) let \(\ex(n,H)\) be the maximum number of hyperedges in an \(r\)-uniform hypergraph on \(n\) vertices which does not contain a copy of \(H\text{.}\)
Prove that
\begin{equation*}
\ex\left(n,K_{r}^{(r)}(m)\right)=O\left(n^{r-\frac{1}{m^{r-1}}}\right)\text{.}
\end{equation*}
Let
\(K_r(m)\) denote the complete
\(r\)-partite graph with parts of size
\(m\text{.}\) Using
question 37.a, prove that, for every
\(\varepsilon>0\text{,}\) there exists
\(\delta>0\) such that if
\(G\) is a graph containing at least
\(\varepsilon\binom{n}{r}\) copies of
\(K_r\text{,}\) then
\(G\) has at least
\(\delta\binom{n}{rm}\) copies of
\(K_r(m)\text{.}\)
Define a notion of
Turán density for
\(k\)-uniform hypergraphs that is analogous to
Definition 3.3.8.
Prove that your definition of the Turán density of a hypergraph is well-defined.
For \(n\geq1\text{,}\) let \(X\) and \(Y\) be independent identically distributed random variables in \(\mathbb{R}^n\text{.}\) Prove that
\begin{equation*}
\mathbb{P}(\|X+Y\|_2\geq 1) \geq \frac{1}{2}\mathbb{P}(\|X\|_2\geq 1)^2\text{.}
\end{equation*}
Hint 1: It might help to start with small dimensions, like \(n=1\) and \(n=2\text{,}\) to build some intuition. Hint 2: Choose \(X_1,X_2,\dots,X_n\) independently according to the same distribution as \(X\text{.}\) Take a limit of an appropriate quantity as \(n\to\infty\text{.}\)
