Hint: Order the vertices randomly and then choose a set of vertices that is guaranteed to be an independent set (in a clever way). Show that the average size of an independent set generated in this way is at least \(\sum_{v\in V(G)}\frac{1}{d(v)+1}\text{.}\)
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
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),
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
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.
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
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.
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?
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{.}\)
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 \(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{.}\)
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
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{.}\)
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{.}\)
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{.}\)
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{.}\)
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{.}\)
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{.}\)
