Властивості біліпшицевих вкладень графів ліхтарника на зважених і незважених деревах

Анотація

У 2021 році F. Baudier, P. Motakis, Th. Schlumprecht та A. Zsák довели, що якщо послідовність $(G_k)_{k\in{\mathbb{N}}}$ графів містить послідовність повних графів з рівномірно обмеженим спотворенням, то послідовність графів ліхтарника над графами $G_k$ містить куби Геммінга з рівномірно обмеженим спотворенням. Вони також поставили питання, чи справджується обернене твердження.

Автори висловили припущення, що контрприкладом може бути послідовність дерев, у яких кожне ребро замінено шляхом довжини, що зростає "помірно". У цій роботі ми доводимо, що це справді так, а також показуємо, що іншим контрприкладом є послідовність "помірно" зважених дерев.

Крім того, ми доводимо, що діамантові графи не вкладаються з рівномірно обмеженим спотворенням у графи ліхтарника на деревах, у яких ребра замінено шляхами достатньо швидко зростаючих довжин.