Розкладність графів. Морфізми кульових структур груп і графів

Позначимо через I граф з множиною вершин N={1,2…} і множиною ребер E={(1,2),(2,3),…}. В цьому параграфі охарактеризовано кульові B структури графів і груп, для яких справедливе одне з таких співвідношень.

B B(I), B(I) B, B(I) B.

Нехай Gr1(V1,E1), Gr2(V2,E2) ─ графи, kN. Відображення f множини V1 на множину V2 називається k-домінантним, якщо B(f(x),1) f(B(x,k)) для кожного xV1. Лема 1 стверджує, що відображення f: V1 V2 є -відображенням кульової структури B(Gr1) на кульову структуру B(Gr2) тоді і тільки тоді, коли f ─ домінантне відображення для деякого kN.

Лема 1. Нехай Gr1(V1,E1), Gr2(V2,E2) ─ графи, kN, f ─ k-домінантне відображення V1 на V2 . Тоді B(f(x),m) f(B(x,km)) для всіх xV1, m.

Доведення. Зафіксуємо довільні xV1, m. Для елемента yB(f(x),m) виберемо елементи y1, y2, …, yn, n
Лема 2. Нехай Gr1(V1,E1), Gr2(V2,E2) ─ графи. Припустимо що існує відображення g:, таке що |B(x,m)| g(m) для всіх xV1, m . Якщо B(Gr1) B(Gr2), то існує k, таке що |B(y,m)| g(km) для всіх yV2, m.

Доведення. Нехай f ─ -відображення B(Gr1) на B(Gr2). Виберемо k так, що B(f(x),1) f(B(x,k)) для всіх xV1. За лемою 1 B(f(x),m) f(B(x,km)) для всіх xV1. Отже, |B(f(x),m) g(k,m) для всіх xV1, m. Оскільки f відображає V1 на V2 , то |B(y,m)| g(km) для всіх yV2, m.

Лема 3. Для довільного нескінченного графа Gr(V,E), B(I) B(Gr) тоді і тільки тоді, коли існують розбиття V=i Vi і натуральне число m, такі що |Vi| m і B(x,1)Vj для всіх xVi, i і всіх j>i+1.

Доведення. Припустимо, що B(I) B(Gr) і зафіксуємо -відображення f: N V. Виберемо натуральне число k так, що B(f(y),1) f(B(y,k)) для всіх yN. Покладемо m=2k+1 і розіб'ємо множину натуральних чисел N на послідовні відрізки A0, A1,… довжини m. Покладемо

V0 =f(A0), V1 =f(A1)\V0 , V2=f(A2)\(V1V2), ….

Ясно, що |Vi| m і Vi Vi. Зафіксуємо i і візьмемо довільний елемент xVi. Виберемо aAi, для якого f(a)=x. Тоді

B(x,1) =B(f(a),1) f(B(a,k)) f(Ai-1Ai Ai+1).

Отже, B(x,1) Vj для всіх j>i+1.

Припустимо, що існує розбиття V=i Vi і натуральне число m, що задовольняють припущенню леми. Визначимо бієкцію f: N V так, що з умов a,bN, a
B(f(a),1)=B(x,1) Vi-1ViVi+1 .

Отже, B(f(a),1) B(a,2m). Звідси випливає, що f ─ 2m- домінантне відображення. За лемою 1, f є -відображення B(I) на B(Gr).

Нехай B(X,P,B) ─ довільна кульова структура, P. Ін'єктивну послідовність n елементів множини X назвемо -променем, якщо xn+1 B(xn,) для всіх n.

Лема 4. Нехай B(X,P,B) ─ кульова структура, P. Якщо B(I) B, то кожна диз'юнктна сім'я променів на множині X скінченна.

Доведення. Нехай f: N X -відображення. Виберемо m так, що

() B(f(y),) f(B(y,m))