Lesson 3

Optional Problems.

1. (10 points) Show that for every fixed \(\ell \ge 3\), there exist graphs with \(\Omega(n^{2})\) edges and no induced \(C_{2\ell}\).
2. (20 points) Given \(n\) irrational numbers \(x_{1},…,x_{n}\), let \(f(x_{1},…,x_{n})\) be the number of unordered pairs \(\{x_{i},x_{j}\}\) with \(i<j\) such that \(x_{i}+x_{j}\) is rational. Determine the maximum value of \(f(x_{1},…,x_{n})\) over all choices of \(x_{1},…,x_{n}\in\mathbb{R}\setminus\mathbb{Q}\).