1
$\begingroup$

One of the many equivalent phrasings of the Ruzsa-Szemeredi theorem is as follows. Suppose one has a three-layered $n$-node graph $G = (V=L_1 \cup L_2 \cup L_3, E)$, and one can partition $E$ into two-edge paths going across the layers that are each the unique shortest path between their endpoints. The theorem then states that $|E| = o(n^2)$.

If $G$ can have edge weights, then the corresponding statement is false: one can have $|E| = \Omega(n^2)$. The standard construction is to embed the graph nodes in the integer lattice, in $[3] \times [n/3]$, and put edge weights corresponding to Euclidean distance. Each triple of colinear points across the three layers then gives a unique shortest path, and there are $\Omega(n^2)$ such triples in total.

This construction has aspect ratio (max edge weight / min edge weight) $\alpha = \Omega(n)$, whereas the Ruzsa-Szemeredi theorem basically constrains graphs with $\alpha=1$. My question is whether there are any results making progress on this gap on either side. For example, can there be a construction with $\alpha = O(\sqrt{n})$ but $|E| = \Omega(n^2)$?

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .