WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

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

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


Реферат на тему:
Розкладність графів. Морфізми кульових структур груп і графів
Позначимо через 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 ? домінантне відображення для деякого k N.
Лема 1. Нехай Gr1(V1,E1), Gr2(V2,E2) ? графи, k N, f ? 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, ni+1.
Доведення. Припустимо, що B(I) B(Gr) і зафіксуємо -відображення 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, aB(f(a),1)=B(x,1) Vi-1 Vi Vi+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))
для всіх 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 ) B(i ), B(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)),…).
Тоді B(f(x),m)=f(B(x,m)) для всіх x i [ki], m . Отже, f ? -відображення.
Для кожного i зафіксуємо ін'єктивне відображення gi: [mi] [ki] таке що gi(1)=1. Визначимо відображення g: i [mi] i [ki] за правилом
g((y(0), y(1), …, y(i) ,…)) = (g0(y(0)), g1( y(1)), …, gi( y(i)) ,…).
Тоді g(B(y,m)) B(g(y),m) для всіх y [mi], m . Отже, g є -відображенням.
Лема 6. Нехай i ? послідовність натуральних чисел, g: ? неспадне відображення. Покладемо m0=k0 k1 … kg(0), mi+1=kg(i)+1 kg(i)+2 … kg(i+1). Тоді кульові структури B(i ) і B(i ) ізоморфні .
Доведення. Зафіксуємо довільну бієкцію f0: [m0] [k0] [k1] … [kg(0)] і для кожного i визначимо деяку бієкцію
fi: [mi] [kg(i)+1] [kg(i)+2] … [kg(i+1)] .
Бієкцію f: i [mi] i [ki] визначимо за правилом
f((x(0), x(1), …, x(i) ,…)) = (f0(x(0)), f1( x(1)), …, fi( x(i)) ,…).
Оскільки f(B(x,m))=B(f(x),g(0) + g(1)+ …g(m-1)) для кожного x i [mi] і кожного натурального числа m, то f ? ізоморфізм.
Лема 7. Нехай i і i ? послідовності натуральних чисел, ki>1, mi>1 для всіх i . Тоді
B(i ) B(i ), B(i ) B(i ).
Доведення. За лемою 10.6 існує послідовність i натуральних чисел така що кульові структури B(i ) і B(i ) ізоморфні, причому Ki mi для всіх i . За лемою 10.5
B(i ) B(i ), B(i ) B(i ).
Лема 8. Нехай i , i ? послідовності натуральних чисел. Для кожного i покладемо Ki=k0k1…ki, Mi=m0m1…mi. Кульові структури B(i ) і B(i ) ізоморфні тоді і тільки тоді, коли для кожного k існують l,m такі, що Kk|Ml i Mk|Km.
Доведення. Припустимо, що ці кульові структури ізоморфні і зафіксуємо деякий ізоморфізм
f: i [ki] i [mi].
Оскільки f -відображення, то існує l , таке що f(B(x,k)) B(f(x),l) для кожного x i [ki]. Зафіксуємо довільний елемент a i [mi] і виберемо x i [ki], для якого f(x) B(a,l). Тоді B(f(x),l)=B(a,l) i f(B(x,k)) B(a,l). Звідси випливає, що f -1(B(a,l)) є диз'юнктним об'єднанням куль радіуса k. Помітимо, що кожна куля радіуса l в i [mi] має потужність Ml , а кожна куля радіуса k в i [ki]має потужність Kk. Отже, Kk|Mb . Для того, щоб знайти число m досить повторити ці міркування для ізоморфізму f -1.
Припустимо, що для кожного k існують l,m , такі що Kk|Ml , Mk|Km. Застосовуючи лему 10.6, можна вважати, що
K0|M0 , M0|K1 , K1|M1, M1|K2 , K2|M2, …
Покладемо
s0=K0, s1=M0/K0, s2=K1/M0, s3=M1/K1 , s4=K2/M1, …
За лемою 6 кульові структури B(i ) і B(i ) ізоморфні.
Лема 9. Нехай група G є об'єднанням зростаючого ланцюга своїх скінченних підгруп G0 G1 … Gi …, G0={e}, e ? одиниця групи G. Покладемо ki=|Gi+1:Gi|, i . Тоді кульова структура B(G) ізоморфна B(i ).
Доведення. Для кожного i розкладемо Gi+1 на праві суміжні класи по підгрупі Gi і виберемо деяку множину Xi представників суміжних класів, e Xi. Таким чином, Gi+1 =GiXi. Візьмемо довільний елемент g G і виберемо найменшу підгрупу Gm+1, для якої y Gm+1. Для g=e виберемо підгрупу G1. Тоді g= gm-1 xm-1, gm-1 Gm , xm Xm-1 . Оскільки gm-1 Gm , то gm-1=gm-2 xm-1 для деяких елементів gm-2 Gm-1, xm-1 Xm-1. Після m+1 кроків отримаємо представлення
g=x0x1…xm-1xm, x0 X0, x1 X1, …, xm Xm.
Зауважимо, що таке представлення однозначне. Для кожного i зафіксуємо довільну бієкцію fi: Xi [ki], таку що fi(e)=1. Визначимо бієкцію f: G i [ki] за правилом
f(g)= (f0(x0), f1( x1), …, fm( xm), 1,1,1,…).
Оскільки кожна скінченна підмножина групи G міститься в деякій скінченнійпідгрупі, то f ? ізоморфізм між B(G) і B(i ).
Лема 10. Нехай G= Z2 ? пряма сума копій групи Z2={0,1}. Тоді B(I) B(G).
Доведення. Зручно вважати, що I ? граф з множиною вершин і множиною ребер E={(i,i+1): i }. Для кожного k розглянемо бінарний розклад
k=a020+a121+…+an2n.
Визначимо відображення f: G за правилом
f(k)=(a0, a1,…, an, 0,0,0,…).
Для кожного m позначимо
Gm={g G: g=(z0,z1,…, zm, 0, 0, 0, …), z0,…, zm {0,1}}.
Помітимо, що
B(f(k), Gm) f([k-2m+1, k+2m+1]).
Звідси випливає, що f ? - відображення B(I) на B(G) .
Теорема 1. Для довільного нескінченного зв'язного графа Gr(V,E) справедливі твердження
B(Gr) B(I), B(I) B(Gr).
Доведення. За теоремою граф Gr(V,E) розкладається на квазіпромені. Кожен квазіпромінь допускає 3-домінантне відображення на I. Отже, B(Gr) B(I).
Доведемо твердження B(I) B(Gr). Припустимо спочатку, що граф Gr локально скінченний. За лемою Кьоніга існує промінь n в графі Gr. Покладемо f(n+1)=xn, n
Loading...

 
 

Цікаве