Probability in Computer Science · Theory Problems
Lesson 2
Advanced Problems.
- (20 points) Given a graph \(G = (V,E)\), an embedding of \(G\) into the plane is a planar representation of \(G\), where each vertex is represented by a point, and each edge from \(u\) to \(v\) is represented by a curve between the points representing \(u\) and \(v\). The crossing number of an embedding of a graph is the number of pairs of curves which intersect and do not share endpoints. The crossing number of \(G\), \(\mathrm{cr}(G)\), is the minimal crossing number of a planar embedding of \(G\).
Let \(G\) be a graph such that \(\lvert E\rvert \geq 4\lvert V\rvert\), show that \[\mathrm{cr}(G) \geq \frac{\lvert E\rvert^{3}}{64\ \lvert V\rvert^{2}}.\]
- (20 points) A set \(A \subset \mathbb{N}\) is called a Sidon set if all sums \(x+y\) with \(x, y \in A\) and \(x \le y\) are distinct. Prove that for sufficiently large \(n\), there exists a Sidon set \(A \subseteq \{1, …, n\}\) of size at least \(c \cdot n^{1/3}\) for some constant \(c\).
Hint:
Choose a random subset \(S \subseteq \{1, …, n\}\) by including each element independently with probability \(p\). Since \(S\) might not be a Sidon set, define a random variable \(Y\) that counts the number of "bad" quadruples \((x, y, z, w)\) in \(S\) satisfying \(x+y=z+w\). Form a set \(A\) by removing one element from each such quadruple. Optimize \(p\) to maximize the expected size of \(A\). - (20 points) Let \(G=(V, E)\) be a graph on \(n\) vertices with minimum degree \(\delta > 1\). A dominating set is a subset \(D \subseteq V\) such that every vertex \(v \in V \setminus D\) is adjacent to at least one vertex in \(D\). Prove that \(G\) has a dominating set of size at most: \[\frac{n(1 + \ln(\delta + 1))}{\delta + 1}.\]
- (20 points) Let \(\mathcal{F}\) be a family of subsets of \([n]\) such that every set has size \(k\), and every pair of sets in \(\mathcal{F}\) has a non-empty intersection. Prove that if \(n \ge 2k\), then \(|\mathcal{F}| \le \binom{n-1}{k-1}\).
Hint:
Consider arranging the numbers \(1, …, n\) uniformly at random on a circle (a cyclic permutation). Estimate the expected number of sets in \(\mathcal{F}\) that appear as contiguous intervals on this circle. - (25 points) Prove the lower bound \(R(3, k) = \Omega\left(\frac{k^2}{\log^2 k}\right)\). Specifically, show that there is a graph on \(n = \Omega\left(\frac{k^2}{\log^2 k}\right)\) vertices with no triangles and no independent sets of size \(k\).
- (25 points) Let \(T=(V, E)\) be a tournament on \(n\) vertices with \(m = \binom{n}{2}\) arcs. Prove that there exists an arrangement of the vertices \(v_{1}, …, v_{n}\) such that more than half the arcs point “forward” (from \(v_{i}\) to \(v_{j}\) where \(i < j\)), and specifically, we can achieve at least: \[\frac{m}{2}+ \Omega(n) \text{ forward arcs.}\]
Hint:
Let \(\pi\) be a uniform random permutation of the vertex set \(V\). Let \(X\) be the random variable representing the number of forward arcs in the arrangement defined by \(\pi\). Prove that \(\operatorname{Var}[X] = \Omega(n^{2})\). Use the symmetry between an ordering and its reverse to prove that there always exists an arrangement with at least \(E[X] + \sqrt{\operatorname{Var}[X]}\) forward arcs. - (30 points) A function \(r\colon \mathbb{N}\to \mathbb{R}\) is a threshold function for a monotone graph property \(A\), if for any \(p\colon \mathbb{N}\to [0, 1]\):
- \(p(n) = o(r(n)) \implies \lim_{n \to \infty}\mathbb{P}\left[ A \text{holds for} G(n, p(n)) \right] = 0\),
- \(r(n) = o(p(n)) \implies \lim_{n \to \infty}\mathbb{P}\left[ A \text{holds for} G(n, p(n)) \right] = 1\).
(A property \(A\) is monotone if for any two graphs \(G\) and \(H\) with \(V(H) = V(G)\), \(E(H) \subseteq E(G)\), and \(H\) having property \(A\), \(G\) has property \(A\) as well). - (30 points) Let \(G \sim G(n, 1/2)\). Prove that with high probability both the clique number \(\omega(G)\) and the independence number \(\alpha(G)\) lie within an interval of length \(O(\log \log n)\) centered at \(2 \log_{2} n\).
Hint:
Count \(k\)-cliques using \(X_{k}\). Show that \(E[X_{k}]=\binom{n}{k}2^{-\binom{k}{2}}\) drops from “\(\gg 1\)” to “\(\ll 1\)” when \(k\) passes roughly \(2\log_{2} n\).For the upper bound use Markov on \(X_{k}\). For the lower bound, compute \(E[X_{k}^{2}]\) by grouping pairs of \(k\)-sets by their intersection size, and use \(\Pr[X_{k}=0]\le \operatorname{Var}[X_{k}]/E[X_{k}]^{2}\).
Let \(H\) be a graph with \(v\) vertices and \(e \ge 1\) edges. We define the density of \(H\) as \[\rho(H) = \frac{e}{v}.\] We call \(H\) balanced if no subgraph of \(H\) has strictly greater density than \(H\) itself.
Let \(H\) be a balanced graph with density \(\rho\). Prove that \[r(n) = n^{-1/\rho}\] is a threshold function for the event that \(H\) is a subgraph of \(G(n, p)\).