Namespaces
Variants
Actions

Difference between revisions of "Erdös problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (moved Erdos problem to Erdös problem over redirect: accented title)
m (tex encoded by computer)
 
Line 1: Line 1:
The problem on the existence in an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e0361201.png" />-dimensional Euclidean space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e0361202.png" /> of a set of more than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e0361203.png" /> points, any three of which form a non-obtuse triangle (the Erdös property). It was posed by P. Erdös (see [[#References|[1]]]), who also made the conjecture (proved in [[#References|[2]]]) that the problem has a negative answer and that a set having the Erdös property contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e0361204.png" /> elements if and only if it consists of the set of vertices of a rectangular parallelopipedon in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e0361205.png" />. The proof of this assertion also solved the so-called Klee problem: What is the number of vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e0361206.png" /> of a polyhedron <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e0361207.png" /> if any two of its vertices lie in distinct parallel supporting hyperplanes of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e0361208.png" /> (the Klee property). If a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e0361209.png" /> has the Erdös property, then the convex hull <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e03612010.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e03612011.png" /> is a polyhedron having the Klee property and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e03612012.png" /> is equal to the cardinality of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e03612013.png" />. If a polyhedron <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e03612014.png" /> has the Klee property, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e03612015.png" />. The equality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e03612016.png" /> characterizes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e03612017.png" />-dimensional parallelopipeda in the set of all polyhedra having the Klee property.
+
<!--
 +
e0361201.png
 +
$#A+1 = 19 n = 0
 +
$#C+1 = 19 : ~/encyclopedia/old_files/data/E036/E.0306120 Erd\AGos problem
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
The Erdös problem is connected with the [[Hadwiger hypothesis|Hadwiger hypothesis]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e03612018.png" />.
+
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
 +
The problem on the existence in an  $  n $-
 +
dimensional Euclidean space  $  E  ^ {n} $
 +
of a set of more than  $  2  ^ {n} $
 +
points, any three of which form a non-obtuse triangle (the Erdös property). It was posed by P. Erdös (see [[#References|[1]]]), who also made the conjecture (proved in [[#References|[2]]]) that the problem has a negative answer and that a set having the Erdös property contains  $  2  ^ {n} $
 +
elements if and only if it consists of the set of vertices of a rectangular parallelopipedon in  $  E  ^ {n} $.
 +
The proof of this assertion also solved the so-called Klee problem: What is the number of vertices  $  m ( K) $
 +
of a polyhedron  $  K \subset  E  ^ {n} $
 +
if any two of its vertices lie in distinct parallel supporting hyperplanes of  $  K $(
 +
the Klee property). If a set  $  N \subset  E  ^ {n} $
 +
has the Erdös property, then the convex hull  $  M =  \mathop{\rm conv}  N $
 +
of  $  N $
 +
is a polyhedron having the Klee property and  $  m ( M) $
 +
is equal to the cardinality of  $  N $.
 +
If a polyhedron  $  K $
 +
has the Klee property, then  $  m ( K) \leq  2  ^ {n} $.
 +
The equality  $  m ( K) = 2  ^ {n} $
 +
characterizes  $  n $-
 +
dimensional parallelopipeda in the set of all polyhedra having the Klee property.
 +
 
 +
The Erdös problem is connected with the [[Hadwiger hypothesis|Hadwiger hypothesis]] $  b ( M) = m ( M) $.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  P. Erdös,  "Some unsolved problems"  ''Michigan J. Math.'' , '''4'''  (1957)  pp. 291–300</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  L. Danzer,  B. Grünbaum,  "Ueber zwei Probleme bezüglich konvexer Körpern von P. Erdös und von V.L. Klee"  ''Math.Z.'' , '''79'''  (1962)  pp. 95–99</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  P. Erdös,  "Some unsolved problems"  ''Michigan J. Math.'' , '''4'''  (1957)  pp. 291–300</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  L. Danzer,  B. Grünbaum,  "Ueber zwei Probleme bezüglich konvexer Körpern von P. Erdös und von V.L. Klee"  ''Math.Z.'' , '''79'''  (1962)  pp. 95–99</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
This Erdös problem was first stated (for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036120/e03612019.png" />) in [[#References|[a1]]], the Klee problem in [[#References|[a2]]].
+
This Erdös problem was first stated (for $  n = 3 $)  
 +
in [[#References|[a1]]], the Klee problem in [[#References|[a2]]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P. Erdös,  "Problem 4306"  ''Amer. Math. Monthly'' , '''55'''  (1948)  pp. 431</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  V.L. Klee,  "Unsolved problems in intuitive geometry" , Seattle  (1960)  (Mimeographed notes)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P. Erdös,  "Problem 4306"  ''Amer. Math. Monthly'' , '''55'''  (1948)  pp. 431</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  V.L. Klee,  "Unsolved problems in intuitive geometry" , Seattle  (1960)  (Mimeographed notes)</TD></TR></table>

Latest revision as of 19:37, 5 June 2020


The problem on the existence in an $ n $- dimensional Euclidean space $ E ^ {n} $ of a set of more than $ 2 ^ {n} $ points, any three of which form a non-obtuse triangle (the Erdös property). It was posed by P. Erdös (see [1]), who also made the conjecture (proved in [2]) that the problem has a negative answer and that a set having the Erdös property contains $ 2 ^ {n} $ elements if and only if it consists of the set of vertices of a rectangular parallelopipedon in $ E ^ {n} $. The proof of this assertion also solved the so-called Klee problem: What is the number of vertices $ m ( K) $ of a polyhedron $ K \subset E ^ {n} $ if any two of its vertices lie in distinct parallel supporting hyperplanes of $ K $( the Klee property). If a set $ N \subset E ^ {n} $ has the Erdös property, then the convex hull $ M = \mathop{\rm conv} N $ of $ N $ is a polyhedron having the Klee property and $ m ( M) $ is equal to the cardinality of $ N $. If a polyhedron $ K $ has the Klee property, then $ m ( K) \leq 2 ^ {n} $. The equality $ m ( K) = 2 ^ {n} $ characterizes $ n $- dimensional parallelopipeda in the set of all polyhedra having the Klee property.

The Erdös problem is connected with the Hadwiger hypothesis $ b ( M) = m ( M) $.

References

[1] P. Erdös, "Some unsolved problems" Michigan J. Math. , 4 (1957) pp. 291–300
[2] L. Danzer, B. Grünbaum, "Ueber zwei Probleme bezüglich konvexer Körpern von P. Erdös und von V.L. Klee" Math.Z. , 79 (1962) pp. 95–99

Comments

This Erdös problem was first stated (for $ n = 3 $) in [a1], the Klee problem in [a2].

References

[a1] P. Erdös, "Problem 4306" Amer. Math. Monthly , 55 (1948) pp. 431
[a2] V.L. Klee, "Unsolved problems in intuitive geometry" , Seattle (1960) (Mimeographed notes)
How to Cite This Entry:
Erdös problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Erd%C3%B6s_problem&oldid=46848
This article was adapted from an original article by P.S. Soltan (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article