On a problem of Specker about Euclidean representations of finite graphs
| Autor: | Nguyen Van Thé, Lionel |
|---|---|
| Přispěvatelé: | Institut de Mathématiques de Marseille (I2M), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
010201 computation theory & mathematics
General Mathematics 010102 general mathematics [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] FOS: Mathematics Mathematics - Combinatorics Combinatorics (math.CO) 05C62 0102 computer and information sciences 0101 mathematics 01 natural sciences ComputingMilieux_MISCELLANEOUS |
| Zdroj: | Expositiones Mathematicae Expositiones Mathematicae, Elsevier, 2019, 37 (2), pp.192-199. ⟨10.1016/j.exmath.2018.07.006⟩ Expositiones Mathematicae, 2019, 37 (2), pp.192-199. ⟨10.1016/j.exmath.2018.07.006⟩ |
| ISSN: | 0723-0869 |
| DOI: | 10.1016/j.exmath.2018.07.006⟩ |
| Popis: | Say that a graph $G$ is \emph{representable in $\R ^n$} if there is a map $f$ from its vertex set into the Euclidean space $\R ^n$ such that $\| f(x) - f(x')\| = \| f(y) - f(y')\|$ iff $\{x,x'\}$ and $\{y, y'\}$ are both edges or both non-edges in $G$. The purpose of this note is to present the proof of the following result, due to Einhorn and Schoenberg: if $G$ finite is neither complete nor independent, then it is representable in $\R ^{|G|-2}$. A similar result also holds in the case of finite complete edge-colored graphs. Comment: 8 pages, 2 figures. The 2011 version of this article was supposed to remain unpublished because the question it answers was actually answered in 1966 (even before the question existed!). This new version, with a typo corrected on p.3, will nevertheless appear as an expository article in Expo. Math |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect