Namespaces
Variants
Actions

Difference between revisions of "Hadwiger hypothesis"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
 +
{{TEX|done}}
 
''Hadwiger conjecture''
 
''Hadwiger conjecture''
  
A problem in [[Combinatorial geometry|combinatorial geometry]] on the covering of a convex body by figures of a special form, which was put forth by H. Hadwiger in [[#References|[1]]]. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h0461101.png" /> be a convex body in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h0461102.png" />-dimensional Euclidean space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h0461103.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h0461104.png" /> the minimal number of bodies homothetic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h0461105.png" /> with homothety coefficient <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h0461106.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h0461107.png" />, that are sufficient to cover <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h0461108.png" />. The Hadwiger conjecture consists in the following: Any bounded set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h0461109.png" /> satisfies the inequality
+
A problem in [[Combinatorial geometry|combinatorial geometry]] on the covering of a convex body by figures of a special form, which was put forth by H. Hadwiger in [[#References|[1]]]. Let $K$ be a convex body in the $n$-dimensional Euclidean space $\mathbf R^n$, and let $b(K)$ the minimal number of bodies homothetic to $K$ with homothety coefficient $k$, $0<k<1$, that are sufficient to cover $K$. The Hadwiger conjecture consists in the following: Any bounded set $K\subset\mathbf R^n$ satisfies the inequality
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611010.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
$$n+1\leq b(K)\leq2^n.\tag{*}$$
  
Here the equality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611011.png" /> characterizes a parallelepiped (see [[#References|[1]]]). The Hadwiger conjecture has been proved for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611012.png" />; for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611013.png" /> there are (1988) only partial results. For example, for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611014.png" />-dimensional bounded polyhedron <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611015.png" /> in which any two vertices belong to two distinct parallel supporting hyperplanes to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611016.png" /> the inequality (*) holds. Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611017.png" /> coincides with the number of vertices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611018.png" />, but in the set of such polyhedra the equality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611019.png" /> has been verified only for parallelepipeds. This result is connected with the solution of the [[Erdös problem|Erdös problem]] on the number of points in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611020.png" /> any three of which form a triangle that is not obtuse angled. The Hadwiger conjecture is also connected with [[Covering|covering]]; [[Decomposition|decomposition]] and the [[Illumination problem|illumination problem]]. For example, the Hadwiger conjecture can be regarded as a generalization of the [[Borsuk problem|Borsuk problem]] on the decomposition of a set into parts of smaller diameter, when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611021.png" /> is replaced by a Minkowski space. For an unbounded set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611022.png" /> the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611023.png" /> is either equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611024.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611025.png" /> is a convex bounded body of lower dimension, or is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611026.png" />. For example, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611027.png" /> the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611028.png" /> can only take one of the values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611029.png" /> (see [[#References|[2]]]).
+
Here the equality $b(K)=2^n$ characterizes a parallelepiped (see [[#References|[1]]]). The Hadwiger conjecture has been proved for $n\leq2$; for $n\geq3$ there are (1988) only partial results. For example, for any $n$-dimensional bounded polyhedron $K\subset\mathbf R^n$ in which any two vertices belong to two distinct parallel supporting hyperplanes to $K$ the inequality \ref{*} holds. Here $b(K)$ coincides with the number of vertices of $K$, but in the set of such polyhedra the equality $b(K)=2^n$ has been verified only for parallelepipeds. This result is connected with the solution of the [[Erdös problem|Erdös problem]] on the number of points in $\mathbf R^n$ any three of which form a triangle that is not obtuse angled. The Hadwiger conjecture is also connected with [[Covering|covering]]; [[Decomposition|decomposition]] and the [[Illumination problem|illumination problem]]. For example, the Hadwiger conjecture can be regarded as a generalization of the [[Borsuk problem|Borsuk problem]] on the decomposition of a set into parts of smaller diameter, when $\mathbf R^n$ is replaced by a Minkowski space. For an unbounded set $K\subset\mathbf R^n$ the number $b(K)$ is either equal to $b(K')$, where $K'$ is a convex bounded body of lower dimension, or is $\infty$. For example, for $K\subset\mathbf R^3$ the number $b(K)$ can only take one of the values $1,2,3,4,\infty$ (see [[#References|[2]]]).
  
 
====References====
 
====References====
Line 13: Line 14:
  
 
====Comments====
 
====Comments====
For bounded centrally-symmetric bodies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611030.png" /> Hadwiger's conjecture holds, see [[#References|[a1]]].
+
For bounded centrally-symmetric bodies $K\subset\mathbf R^3$ Hadwiger's conjecture holds, see [[#References|[a1]]].
  
 
See also [[Geometry of numbers|Geometry of numbers]] and the standard work [[#References|[a4]]].
 
See also [[Geometry of numbers|Geometry of numbers]] and the standard work [[#References|[a4]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  M. Lassak,  "Solution of Hadwiger's covering problem for centrally symmetric convex bodies in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h046/h046110/h04611031.png" />"  ''J. London Math. Soc. (2)'' , '''30'''  (1984)  pp. 501–511</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  L. Danzer,  B. Grünbaum,  V.L. Klee,  "Helly's theorem and its relatives"  V.L. Klee (ed.) , ''Convexity'' , ''Proc. Symp. Pure Math.'' , '''7''' , Amer. Math. Soc.  (1963)  pp. 101–180</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  H. Hadwiger,  H. Debrunner,  "Kombinatorische Geometrie in der Ebene"  ''L'Enseign. Math.'' , '''2'''  (1959)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  P.M. Gruber,  C.G. Lekkerkerker,  "Geometry of numbers" , North-Holland  (1987)  pp. Sect. (iv)  (Updated reprint)</TD></TR></table>
+
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  M. Lassak,  "Solution of Hadwiger's covering problem for centrally symmetric convex bodies in $E^3$"  ''J. London Math. Soc. (2)'' , '''30'''  (1984)  pp. 501–511</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  L. Danzer,  B. Grünbaum,  V.L. Klee,  "Helly's theorem and its relatives"  V.L. Klee (ed.) , ''Convexity'' , ''Proc. Symp. Pure Math.'' , '''7''' , Amer. Math. Soc.  (1963)  pp. 101–180</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  H. Hadwiger,  H. Debrunner,  "Kombinatorische Geometrie in der Ebene"  ''L'Enseign. Math.'' , '''2'''  (1959)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  P.M. Gruber,  C.G. Lekkerkerker,  "Geometry of numbers" , North-Holland  (1987)  pp. Sect. (iv)  (Updated reprint)</TD></TR></table>

Latest revision as of 18:42, 5 August 2014

Hadwiger conjecture

A problem in combinatorial geometry on the covering of a convex body by figures of a special form, which was put forth by H. Hadwiger in [1]. Let $K$ be a convex body in the $n$-dimensional Euclidean space $\mathbf R^n$, and let $b(K)$ the minimal number of bodies homothetic to $K$ with homothety coefficient $k$, $0<k<1$, that are sufficient to cover $K$. The Hadwiger conjecture consists in the following: Any bounded set $K\subset\mathbf R^n$ satisfies the inequality

$$n+1\leq b(K)\leq2^n.\tag{*}$$

Here the equality $b(K)=2^n$ characterizes a parallelepiped (see [1]). The Hadwiger conjecture has been proved for $n\leq2$; for $n\geq3$ there are (1988) only partial results. For example, for any $n$-dimensional bounded polyhedron $K\subset\mathbf R^n$ in which any two vertices belong to two distinct parallel supporting hyperplanes to $K$ the inequality \ref{*} holds. Here $b(K)$ coincides with the number of vertices of $K$, but in the set of such polyhedra the equality $b(K)=2^n$ has been verified only for parallelepipeds. This result is connected with the solution of the Erdös problem on the number of points in $\mathbf R^n$ any three of which form a triangle that is not obtuse angled. The Hadwiger conjecture is also connected with covering; decomposition and the illumination problem. For example, the Hadwiger conjecture can be regarded as a generalization of the Borsuk problem on the decomposition of a set into parts of smaller diameter, when $\mathbf R^n$ is replaced by a Minkowski space. For an unbounded set $K\subset\mathbf R^n$ the number $b(K)$ is either equal to $b(K')$, where $K'$ is a convex bounded body of lower dimension, or is $\infty$. For example, for $K\subset\mathbf R^3$ the number $b(K)$ can only take one of the values $1,2,3,4,\infty$ (see [2]).

References

[1] H. Hadwiger, "Ueber Treffanzahlen bei translationsgleichen Eikörpern" Arch. Math. (Basel) , 8 (1957) pp. 212–213
[2] V.G. Boltyanskii, P.S. Soltan, "The combinatorial geometry of various classes of convex sets" , Kishinev (1978) (In Russian)


Comments

For bounded centrally-symmetric bodies $K\subset\mathbf R^3$ Hadwiger's conjecture holds, see [a1].

See also Geometry of numbers and the standard work [a4].

References

[a1] M. Lassak, "Solution of Hadwiger's covering problem for centrally symmetric convex bodies in $E^3$" J. London Math. Soc. (2) , 30 (1984) pp. 501–511
[a2] L. Danzer, B. Grünbaum, V.L. Klee, "Helly's theorem and its relatives" V.L. Klee (ed.) , Convexity , Proc. Symp. Pure Math. , 7 , Amer. Math. Soc. (1963) pp. 101–180
[a3] H. Hadwiger, H. Debrunner, "Kombinatorische Geometrie in der Ebene" L'Enseign. Math. , 2 (1959)
[a4] P.M. Gruber, C.G. Lekkerkerker, "Geometry of numbers" , North-Holland (1987) pp. Sect. (iv) (Updated reprint)
How to Cite This Entry:
Hadwiger hypothesis. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Hadwiger_hypothesis&oldid=16700
This article was adapted from an original article by P.S. Soltan (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article