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

Реферат на тему:

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

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

B.

-відображенням кульової структури B(Gr1) на кульову структуру B(Gr2) тоді і тільки тоді, коли f \x2500 домінантне відображення для деякого k(N.

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

Доведення. Зафіксуємо довільні x(V1, m ((. Для елемента y(B(f(x),m) виберемо елементи y1, y2, …, yn, n
B(Gr2), то існує k((, таке що |B(y,m)|( g(km) для всіх y(V2, m ((.

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

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

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

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

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

B(x,1) =B(f(a),1)( f(B(a,k))( f(Ai-1(Ai (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-1(Vi(Vi+1 .

-відображення B(I) на B(Gr).

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

B, то кожна диз'юнктна сім'я (-променів на множині X скінченна.

-відображення. Виберемо m(( так, що

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

для всіх y(N. Нехай n(( (-промінь. Виберемо y0(N з f(y0)=x0. Користуючись співвідношенням ((), побудуємо індуктивну послідовність n(( в N, таку що f(yn)=xn і |yn+1 - yn|( m для всіх n((. Оскільки послідовність n(( ін'єктивна, то відрізок [a,b](N довжини m, містить точку e, таку що f(e)({xn: n((}. Звідси випливає, що кожна диз'юнктна сім'я (-променів в X має потужність ( m.

Для довільної послідовності i(( натуральних чисел позначимо [ki]= {1,2,…,ki}, i((. Прямим добутком X=(i(( [ki] називається множина усіх векторів x=(x(0), x(1),…, x(i),…), таких що x(i)([ki] і x(i)=1 для всіх i((, за винятком деякого скінченного числа індексів. Для довільних x(X, m(( покладемо

B(x,m)={y(X: y(i)=x(i) для всіх i( m}.

Кульову структуру (X, (, B) позначимо через B(i(().

Лема 5. Нехай i(( , i(( послідовності натуральних чисел . Якщо ki( mi для всіх i((, то

B(i(().

Доведення. Для кожного i(( зафіксуємо деяке відображення fi [ki] на [mi]. Відображення f: (i(( [ki]((i(( [mi] визначимо за правилом

f(x(0), x(1),…, x(i),…)=(f0 (x(0)), f1 ( x(1)),…, fi ( x(i)),…).