RUS  ENG
Full version
JOURNALS // Matematicheskii Sbornik // Archive

Mat. Sb., 2012 Volume 203, Number 10, Pages 145–160 (Mi sm7878)

Embeddings of graphs into Euclidean space under which the number of points that belong to a hyperplane is minimal

K. I. Oblakov, T. A. Oblakova

M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: 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.

UDC: 515.125

MSC: Primary 05C10; Secondary 57M15

Received: 14.04.2011 and 30.12.2011

DOI: 10.4213/sm7878


 English version:
Sbornik: Mathematics, 2012, 203:10, 1518–1533

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024