The k-sum embedding conjecture for graph families

For a graph family F\mathcal F, let kF\oplus_k\mathcal F denote its closure under kk-clique sums, and let c1(F)c_1(\mathcal F) denote the supremum of the least distortion needed to embed members of F\mathcal F into L1L_1.

kk-sum embedding conjecture. For any family of graphs F\mathcal F, we have

c1(F)=O(1)if and only ifc1(kF)=O(1) for every kN.c_1(\mathcal F)=O(1) \quad\text{if and only if}\quad c_1(\oplus_k\mathcal F)=O(1) \text{ for every } k\in\mathbb N.

Lee and Sidiropoulos showed that this conjecture together with the planar embedding conjecture is equivalent to the GNRS conjecture. The case k=1k=1 is folklore, and the case k=2k=2 has seen progress but remains open.

Sources & referencesView supporting material

Primary source

Anastasios Sidiropoulos, “Non-positive curvature, and the planar embedding conjecture”, arXiv:1304.7512 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.