# Into Darkness

Two things are infinite: the universe and human stupidity; and I’m not sure about the universe.
― Albert Einstein

#### Combinatorics

• (The linear arboricity conjecture) The linear arboricity of every d-regular graph is \lceil (d+1)/2 \rceil.
• (Packing squares) Let s(x) denote the maximum number of non-overlapping unit squares which can be packed into a large square of side length x. Find the best asymptotics of the “wasted” area W(x)=x^2-s(x).
• (Graham’s conjecture on sub-multiplicativity of pebbling number) \pi(G_1\times G_2) \le \pi(G_1)\pi(G_2).

#### Discrete Geometry

• (Erdös-Szekeres problem) For any integer n\geq 3, any set of at least 2^{n-2}+1 points in general position in the plane contains n points that are the vertices of a convex n-gon.
• (Makai–Pach’s conjecture on translative slab covering) A sequence of slabs (region enclosed by two parallel hyperplanes) in \mathbb{R}^d with widths (distance between two hyperplanes) w_1, w_2, \dots permits a translative covering if \sum_i w_i = \infty.

#### Computability

• (Freeness of matrix semigroup) Is it decidable whether the multiplicative semigroup generated by two 2\times 2 matrices in the modular group SL_2(\mathbb{Z}) is free?

#### Metric Geometry

• (Inequality of the Means) Is is possible to pack n^n rectangular n -dimensional boxes each of which has side lengths a_1,a_2,\ldots,a_n inside an n-dimensional cube with side length a_1 + a_2 + \ldots a_n?
• (Michael Atiyah) Let x_1, \ldots, x_n be n distinct points in the unit ball. Let the oriented line x_ix_j meet the boundary 2-sphere in a point t_{ij} (regarded as a point of the complex Riemann sphere \mathbb{C}\cup\infty). For the complex polynomial p_i of degree n-1, whose roots are t_{ij}. For all (x_1, \ldots, x_n) the n polynomials are linearly independent.

#### Number Theory

• (Lehmer’s conjecture) Is there an absolute constant \mu > 1 such that for every monic polynomial p(x) with integer coefficients, the product of the roots of p(x) with length greater than 1 is greater than \mu?

#### Topology

• Is there a continuous mapping f: [0,1]\to\mathbb{R}^2 such that for all \epsilon>0, the image of [0,\epsilon] under f is a convex set with three points not on a line?