Geodesic
Embeddings of graphs into Euclidean space under which the number of points that belong to a hyperplane is minimal
Sbornik. Mathematics, Tome 203 (2012) no. 10, pp. 1518-1533 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper is devoted to the characteristic of a graph that is the minimal (over all embeddings of the graph into a space of given dimension) number of points that belong to the same hyperplane. Upper and lower estimates for this number are given that linearly depend on the dimension of the space. For trees a more precise upper estimate is obtained, which asymptotically coincides with the lower one for large dimension of the space. Bibliography: 9 titles.
Keywords: graph, embedding, hyperplane. 
@article{SM_2012_203_10_a4,
     author = {K. I. Oblakov and T. A. Oblakova},
     title = {Embeddings of graphs into {Euclidean} space under which the number of points that belong to a~hyperplane is minimal},
     journal = {Sbornik. Mathematics},
     pages = {1518--1533},
     year = {2012},
     volume = {203},
     number = {10},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2012_203_10_a4/}
}
TY  - JOUR
AU  - K. I. Oblakov
AU  - T. A. Oblakova
TI  - Embeddings of graphs into Euclidean space under which the number of points that belong to a hyperplane is minimal
JO  - Sbornik. Mathematics
PY  - 2012
SP  - 1518
EP  - 1533
VL  - 203
IS  - 10
UR  - http://geodesic.mathdoc.fr/item/SM_2012_203_10_a4/
LA  - en
ID  - SM_2012_203_10_a4
ER  - 
%0 Journal Article
%A K. I. Oblakov
%A T. A. Oblakova
%T Embeddings of graphs into Euclidean space under which the number of points that belong to a hyperplane is minimal
%J Sbornik. Mathematics
%D 2012
%P 1518-1533
%V 203
%N 10
%U http://geodesic.mathdoc.fr/item/SM_2012_203_10_a4/
%G en
%F SM_2012_203_10_a4
K. I. Oblakov; T. A. Oblakova. Embeddings of graphs into Euclidean space under which the number of points that belong to a hyperplane is minimal. Sbornik. Mathematics, Tome 203 (2012) no. 10, pp. 1518-1533. http://geodesic.mathdoc.fr/item/SM_2012_203_10_a4/

[1] T. A. Antonova, K. I. Oblakov, “Special embeddings of graphs into a three-dimensional space”, Moscow Univ. Math. Bull., 63:6 (2008), 245–250 | DOI | MR

[2] T. A. Oblakova, K. I. Oblakov, “Special embeddings of some disconnected graphs into Euclidean space”, Moscow Univ. Math. Bull., 66:2 (2011), 90–92 | DOI | MR

[3] K. Borsuk, “On the $k$-independent subsets of the Euclidean space and of the Hilbert space”, Bull. Acad. Polon. Sci. Cl. III, 5:4 (1957), 351–356 | MR | Zbl

[4] V. G. Boltyanskij, S. S. Ryshkov, Yu. A. Shashkin, “On $k$-regular imbeddings and their application to the theory of approximation of functions”, Amer. Math. Soc. Transl. (2), 28 (1963), 211–219 | MR | MR | Zbl | Zbl

[5] S. A. Bogatyǐ, “Borsuk's conjecture, Ryshkov obstruction, interpolation, Chebyshev approximation, transversal Tverberg's theorem, and problems”, Proc. Steklov Inst. Math., 239 (2002), 55–73 | MR | Zbl | Zbl

[6] S. A. Bogatyi, V. M. Valov, “Roberts-type embeddings and conversion of transversal Tverberg's theorem”, Sb. Math., 196:11 (2005), 1585–1603 | DOI | MR | Zbl

[7] J. C. Mairhuber, “On Haar's theorem concerning Chebychev approximation problems having unique solutions”, Proc. Amer. Math. Soc., 7:4 (1956), 609–615 | DOI | MR | Zbl

[8] A. Brøndsted, An introduction to convex polytopes, Grad. Texts in Math., 90, Springer-Verlag, New York–Berlin, 1983 | MR | MR | Zbl | Zbl

[9] R. P. Dilworth, “A decomposition theorem for partially ordered sets”, Ann. of Math. (2), 51:1 (1960), 161–166 | DOI | MR | Zbl