Into Darkness – Discrete Thoughts

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

(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)$ .

(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$ .

(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?

(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.

(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$ ?

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?

Leave a comment Cancel reply