On embedding of graphs into Euclidean spaces of small dimension (Q1204473)

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\).