Hadwiger conjecture (combinatorial geometry): Difference between revisions

Revision as of 22:00, 20 July 2010

Revision as of 20:15, 24 July 2010

Line 1:

[[File:Hadwiger covering.svg|thumb|300px|A triangle can be covered by three smaller copies of itself, but a square requires four smaller copies]]

{{unsolved|mathematics|Can every ''n''-dimensional convex body be covered by 2^''n'' smaller copies of itself?}}

In [[combinatorial geometry]], the '''Hadwiger conjecture''' states that any [[convex body]] in ''n''-dimensional [[Euclidean space]] can be covered by 2^''n'' or fewer smaller bodies [[homothety|homothetic]] with to the original body, and that furthermore, the upper bound of 2^''n'' is necessary [[if and only if|iff]] the body is a [[parallelpiped]]. There also exists an equivalent formulation in terms of the number of floodlights needed to illuminate the body.

The Hadwiger conjecture is named after [[Hugo Hadwiger]], who included it on a list of unsolved problems in 1957; it was, however, previously studied by {{harvtxt|Levi|1955}} and independently, {{harvtxt|Gohberg|Markus|1960}}. Additionally, there is a different [[Hadwiger conjecture (graph theory)|Hadwiger conjecture]] concerning [[graph coloring]]—and in some sources the geometric Hadwiger conjecture is also called the Levi–Hadwiger conjecture or the Hadwiger–Levi covering problem.