Hadwiger conjecture (combinatorial geometry): Difference between revisions

Revision as of 14:57, 2 July 2016

Latest revision as of 21:53, 20 August 2025

(33 intermediate revisions by 19 users not shown)

Line 1:

{{see also|Hadwiger conjecture (graph theory)}}

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

{{unsolved|mathematics|Can every ''<math>n''</math>-dimensional convex body be covered by 2<supmath>''2^n''</supmath> 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 [[Homothetic transformation|homothetic]] with the original body, and that furthermore, the upper bound of 2^''n'' is necessary [[if and only if|iff]] the body is a [[parallelepiped]]. 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'''.

The [[conjecture]] remains unsolved even in three dimensions, though the two dimensional case was resolved by {{harvtxt|Levi|1955}}.

==Formal statement==

Line 13:

: <math>K\subseteq\bigcup_{i=1}^{2^n} s_i K + v_i.</math>

Furthermore, the upper bound is necessary iffif and only if ''K'' is a parallelepiped, in which case all 2^''n'' of the scalars may be chosen to be equal to 1/2.

===Alternate formulation with illumination===

As shown by [[Vladimir Boltyansky|Boltyansky]], the problem is equivalent to [[illumination problem|one of illumination]]: how many floodlights must be placed outside of an opaque convex body in order to completely illuminate its exterior? For the purposes of this problem, a body is only considered to be illuminated if for each point of the boundary of the body, there is at least one floodlight that is separated from the body by all of the [[tangent plane]]s intersecting the body on this point; thus, although the faces of a cube may be lit by only two floodlights, the planes tangent to its vertices and edges cause it to need many more lights in order for it to be fully illuminated. For any convex body, the number of floodlights needed to completely illuminate it turns out to equal the number of smaller copies of the body that are needed to cover it.<ref name="BMP"/>

==Examples==

Line 22:

==Known results==

The two-dimensional case was settled by {{harvtxt|Levi|1955}}: every two-dimensional bounded convex set may be covered with four smaller copies of itself, with the fourth copy needed only in the case of parallelograms. However, the conjecture remains open in higher dimensions except for some special cases. The best known asymptotic upper bound on the number of smaller copies needed to cover a given body is<ref>{{harvtxt|Campos|van Hintum|Morris|Tiba|2023}}.</ref>

:<math>\displaystyle 4^n (5n\lnexp\frac{-cn}{\log^8 n).}</math>

where <math>c</math> is a positive constant. For small <math>n</math> the upper bound of <math>(n+1)n^{n-1}-(n-1)(n-2)^{n-1}</math> established by {{harvtxt|Lassak|1988}} is better than the asymptotic one. In three dimensions it is known that sixteen16 copies always suffice, but this is still far from the conjectured bound of eight8 copies.<ref name="BMP">{{harvtxt|Brass|Moser|Pach|2005}}.</ref>

The conjecture is known to hold for certain special classes of convex bodies, including, in dimension three, centrally symmetric polyhedra and [[Surface of constant width|bodies of constant width]] in three dimensions.<ref name="BMP"/> The number of copies needed to cover any [[zonotope]] (other than a parallelepiped) is at most <math>(3/4)2<sup>''^n''</supmath>, while for bodies with a smooth surface (that is, having a single tangent plane per boundary point), at most ''<math>n''&nbsp;+&nbsp;1</math> smaller copies are needed to cover the body, as [[Friedrich Wilhelm Levi|Levi]] already proved.<ref name="BMP"/>

==See also==

Line 35:

==References==

* {{citation|title=Resultscite andbook Problems| in Combinatoriallast1=Boltjansky Geometry| first1=VVladimir G. |last1 author-link1 =Boltjansky Vladimir Boltyansky | last2=Gohberg | first2=I.Israel |last2author-link2=Israel Gohberg | title=Results and Problems in Combinatorial Geometry | publisher=[[Cambridge University Press]] | publication-place=Cambridge | year=1985|contribution=11. Hadwiger's Conjecture |pages=44–46 | isbn=978-0-521-26923-0}}.

*{{citationcite book|first1=Peter|last1=Brass|first2=William|last2=Moser|
first3=János|last3=Pach|author3-link=János Pach|contribution=3.3 Levi–Hadwiger Covering Problem and Illumination|pages=136–142|title=Research Problems in Discrete Geometry|publisher=Springer-Verlag|year=2005| isbn=978-0-387-23815-9}}.

*{{citation|first1=I. Ts.Marcelo|last1=GohbergCampos|first2=A. S.Peter|last2=Markusvan Hintum|formatfirst3=InRobert|last3=Morris|author3-link=Robert RussianMorris (mathematician)|yearfirst4=1960Marius|last4=Tiba|title=ATowards certainHadwiger's problemConjecture aboutvia theBourgain covering of convex sets with homothetic onesSlicing|journal=Izvestiya[[International MoldavskogoMathematics FilialaResearch Akademii Nauk SSSRNotices]]|volumedoi=10.1093/imrn/rnad198|year=2023|volume=2024 |issue=7610 |pages=87–908282–8295 |arxiv=2206.11227}}.

*{{citation|first1=Israel Ts.|last1=Gohberg|authorlink1=Israel Gohberg|first2=Alexander S.|last2=Markus|language= Russian|year=1960|title=A certain problem about the covering of convex sets with homothetic ones|journal=Izvestiya Moldavskogo Filiala Akademii Nauk SSSR|volume=10|issue=76|pages=87–90}}.

*{{citation|first=H.|last=Hadwiger|year=1957|title=Ungelöste Probleme Nr. 20|journal=Elemente der Mathematik|volume=12|pages=121}}.

*{{citation|first=F. W.Hugo|last=LeviHadwiger|authorlink=FriedrichHugo Wilhelm LeviHadwiger|year=1957|title=ÜberdeckungUngelöste einesProbleme EibereichesNr. durch Parallelverschiebungen seines offenen Kerns20|journal=[[ArchivElemente der Mathematik]]|volume=6|year=195512|pages=369–370|issue=5|doi=10.1007/BF01900507121}}.

*{{Citation |last1=Huang |first1=Han |last2=Slomka |first2=Boaz A. |last3=Tkocz |first3=Tomasz |last4=Vritsiou |first4=Beatrice-Helen |date=2022 |title=Improved bounds for Hadwiger's covering problem via thin-shell estimates |journal=[[Journal of the European Mathematical Society]] |language=en |volume=24 |issue=4 |pages=1431–1448 |doi=10.4171/jems/1132 |doi-access=free |issn=1435-9855|arxiv=1811.12548 }}.

*{{citation|first=Marek|last=Lassak|year=1988|title=Covering the boundary of a convex set by tiles|journal=[[Proceedings of the American Mathematical Society]]|volume=104|issue=1|pages=269–272|mr=0958081|doi=10.1090/s0002-9939-1988-0958081-7|doi-access=free}}.

*{{citation|first=Friedrich Wilhelm|last=Levi|authorlink=Friedrich Wilhelm Levi|title=Überdeckung eines Eibereiches durch Parallelverschiebungen seines offenen Kerns|journal=[[Archiv der Mathematik]]|volume=6|year=1955|pages=369–370|issue=5|doi=10.1007/BF01900507|doi-access=free|s2cid=121459171}}.

[[Category:Discrete geometry]]

[[Category:Conjectures]]

[[Category:Unsolved problems in geometry]]

[[Category:Eponyms in geometry]]