On embedding of graphs into Euclidean spaces of small dimension (Q1204473): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3852212 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cycles of even length in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Johnson-Lindenstrauss lemma and the sphericity of some graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a problem of K. Zarankiewicz / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Embeddings of graphs in Euclidean spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Geometrical embeddings of graphs / rank | |||
Normal rank |
Latest revision as of 14:59, 17 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On embedding of graphs into Euclidean spaces of small dimension |
scientific article |
Statements
On embedding of graphs into Euclidean spaces of small dimension (English)
0 references
10 March 1993
0 references
Suppose \(G=(V,E)\) is a finite graph with an embedding \(f:V\to R^ d\). If there is a number \(t\) so that \((x,y)\in E\) if and only if the scalar product \(f(x)\cdot f(y)\geq t\), we say \(G\) has a scalar product embedding. The least \(d\) for which \(G\) has such an embedding is called the scalar product dimension and is denoted \(d(G)\). If \(G\) has \(n\) vertices, then clearly \(d(G)\leq n\). The best known general upper bound is \(d(G)\leq n- \sqrt n\). The paper under review gives another upper bound based on the edge density of \(G\), \(\rho(G)\). The edge density is defined to be the maximum over all subgraphs \((V',E')\) of \(G\) of the quantities \(2| E'|/| V'|\). The main result is that there is an absolute constant \(c\) with \(d(G)\leq c\rho^ 2\log n\), where \(\rho(G)\leq \rho\).
0 references
finite graph
0 references
embedding
0 references
scalar product embedding
0 references
scalar product dimension
0 references
upper bound
0 references
edge density
0 references