Разделяющие функции, спектральная теория графов и локально-скалярные представления в гильбертовых пространствах
Розглядається зв'язок відокремлюючих функцій ρr з локально-скалярними зображеннями графів та зі спектральною теорією графів. We consider the connection of the separating functions ρr with locally scalar representations of graphs and with spectral theory of graphs....
Gespeichert in:
| Veröffentlicht in: | Український математичний журнал |
|---|---|
| Datum: | 2006 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут математики НАН України
2006
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/164045 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Разделяющие функции, спектральная теория графов и локально-скалярные представления в гильбертовых пространствах / И.К. Редчук // Український математичний журнал. — 2006. — Т. 58, № 1. — С. 36–46. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-164045 |
|---|---|
| record_format |
dspace |
| spelling |
Редчук, И.К. 2020-02-08T08:05:21Z 2020-02-08T08:05:21Z 2006 Разделяющие функции, спектральная теория графов и локально-скалярные представления в гильбертовых пространствах / И.К. Редчук // Український математичний журнал. — 2006. — Т. 58, № 1. — С. 36–46. — Бібліогр.: 10 назв. — рос. 1027-3190 https://nasplib.isofts.kiev.ua/handle/123456789/164045 519.1 Розглядається зв'язок відокремлюючих функцій ρr з локально-скалярними зображеннями графів та зі спектральною теорією графів. We consider the connection of the separating functions ρr with locally scalar representations of graphs and with spectral theory of graphs. ru Інститут математики НАН України Український математичний журнал Статті Разделяющие функции, спектральная теория графов и локально-скалярные представления в гильбертовых пространствах Separating functions, spectral theory of graphs, and locally scalar representations in Hilbert spaces Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Разделяющие функции, спектральная теория графов и локально-скалярные представления в гильбертовых пространствах |
| spellingShingle |
Разделяющие функции, спектральная теория графов и локально-скалярные представления в гильбертовых пространствах Редчук, И.К. Статті |
| title_short |
Разделяющие функции, спектральная теория графов и локально-скалярные представления в гильбертовых пространствах |
| title_full |
Разделяющие функции, спектральная теория графов и локально-скалярные представления в гильбертовых пространствах |
| title_fullStr |
Разделяющие функции, спектральная теория графов и локально-скалярные представления в гильбертовых пространствах |
| title_full_unstemmed |
Разделяющие функции, спектральная теория графов и локально-скалярные представления в гильбертовых пространствах |
| title_sort |
разделяющие функции, спектральная теория графов и локально-скалярные представления в гильбертовых пространствах |
| author |
Редчук, И.К. |
| author_facet |
Редчук, И.К. |
| topic |
Статті |
| topic_facet |
Статті |
| publishDate |
2006 |
| language |
Russian |
| container_title |
Український математичний журнал |
| publisher |
Інститут математики НАН України |
| format |
Article |
| title_alt |
Separating functions, spectral theory of graphs, and locally scalar representations in Hilbert spaces |
| description |
Розглядається зв'язок відокремлюючих функцій ρr з локально-скалярними зображеннями графів та зі спектральною теорією графів.
We consider the connection of the separating functions ρr with locally scalar representations of graphs and with spectral theory of graphs.
|
| issn |
1027-3190 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/164045 |
| citation_txt |
Разделяющие функции, спектральная теория графов и локально-скалярные представления в гильбертовых пространствах / И.К. Редчук // Український математичний журнал. — 2006. — Т. 58, № 1. — С. 36–46. — Бібліогр.: 10 назв. — рос. |
| work_keys_str_mv |
AT redčukik razdelâûŝiefunkciispektralʹnaâteoriâgrafovilokalʹnoskalârnyepredstavleniâvgilʹbertovyhprostranstvah AT redčukik separatingfunctionsspectraltheoryofgraphsandlocallyscalarrepresentationsinhilbertspaces |
| first_indexed |
2025-11-25T21:29:29Z |
| last_indexed |
2025-11-25T21:29:29Z |
| _version_ |
1850557872521347072 |
| fulltext |
UDK 519.1
Y. K. Redçuk (Yn-t matematyky NAN Ukrayn¥, Kyev)
RAZDELQGWYE FUNKCYY,
SPEKTRAL|NAQ TEORYQ HRAFOV
Y LOKAL|NO-SKALQRNÁE PREDSTAVLENYQ
V HYL|BERTOVÁX PROSTRANSTVAX
The connection of separating functions ρr with locally scalar representations of graphs and with the
spectral theory of graphs are considered.
Rozhlqda[t\sq zv’qzok vidokremlggçyx funkcij ρr z lokal\no-skalqrnymy zobraΩennqmy
hrafiv ta zi spektral\nog teori[g hrafiv.
1. Razdelqgwye funkcyy ρρρρr . Nastoqwaq stat\q posvqwena yzuçenyg svqzej
razdelqgwyx funkcyj ρr , vvedenn¥x v [1], s lokal\no-skalqrn¥my predstav-
lenyqmy hrafov, s odnoj storon¥, y so spektral\noj teoryej hrafov — s
druhoj.
V rabote [2] vvedena funkcyq P ( S ), stavqwaq v sootvetstvye çastyçno upo-
rqdoçennomu mnoΩestvu S poloΩytel\noe racyonal\noe çyslo. V termynax
funkcyy P v [2] sformulyrovan kryteryj koneçnoj predstavymosty y ruçnos-
ty proyzvol\noho çastyçno uporqdoçennoho mnoΩestva: çastyçno uporqdoçen-
noe mnoΩestvo S koneçno predstavymo (ruçnoe), esly y tol\ko esly P ( S ) < 4
( P ( S ) = 4). Esly çastyçno uporqdoçennoe mnoΩestvo S est\ obæedynenye s
neperesekagwyxsq cepej (t. e. takyx, çto dva lgb¥x πlementa, prynadleΩawye
razn¥m cepqm, nesravnym¥), to
P ( S ) = ρ ( n1 , n2 , … , ns ) =
i
s
in
=
∑
1
ρ( ) =
i
s
=
∑
1
1 +
n
n
i
i
−
+
1
1
, ni ∈ N.
Spysok vsex reßenyj uravnenyq ρ ( n1 , n2 , … , ns ) = 4 takov:
( 1, 1, 1, 1 ), ( 2, 2, 2 ), ( 1, 3, 3 ), ( 1, 2, 5 ). (1)
Poskol\ku funkcyq ρ vozrastagwaq (çastyçn¥j porqdok na celoçyslenn¥x
vektorax ( n1 , n2 , … , ns ) opredelqetsq estestvenn¥m obrazom), yz spyska (1)
lehko poluçyt\ spysok vsex reßenyj neravenstva ρ ( n1 , n2 , … , ns ) < 4:
( 1, 2, 2 ), ( 1, 2, 3 ), ( 1, 2, 4 ), ( 1, 1, k ), ( l, m ), ( n ), (2)
hde k, l, m, n — proyzvol\n¥e natural\n¥e çysla.
Prymeçatel\no, çto spysok (1) sootvetstvuet vsem rasßyrenn¥m hrafa D¥n-
kyna s odnoj toçkoj vetvlenyq (toçnoe opredelenye sm. v p. 4 dannoj stat\y)
D̃4 , Ẽ6 , Ẽ7 , Ẽ8: komponent¥ vektorov yz spyska (1) sootvetstvugt çyslu
verßyn na kaΩdoj vetvy. Toçno tak Ωe spysok (2) opys¥vaet hraf¥ D¥nkyna
E6 , E7 , E8 , Dn , An .
V termynax funkcyy ρ takΩe mohut b¥t\ zapysan¥ obwye formul¥ dlq
razmernostej y sformulyrovan¥ kryteryy koneçnomernosty y polynomyal\-
nosty rosta alhebr, zadann¥x obrazugwymy y lynejn¥my [3] yly polynejn¥my
sootnoßenyqmy (sm. [4]).
V rabote [1] predloΩeno estestvennoe obobwenye funkcyy ρ . Oboznaçym
çerez Vm , m ∈ N, mnoΩestvo neuporqdoçenn¥x m-ok neotrycatel\n¥x cel¥x
çysel; V = m mV∈N∪ . Pust\ dlq fyksyrovannoho r ∈ R, r ≥ 4, zadana rekur-
rentnaq çyslovaq posledovatel\nost\ { ui } : u0 = 0, u1 = 1, ui + 2 = ( r – 2 ) ui + 1 –
– ui . PoloΩym
© Y. K. REDÇUK, 2006
36 ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 1
RAZDELQGWYE FUNKCYY, SPEKTRAL|NAQ TEORYQ HRAFOV … 37
ρr ( 0 ) = 0,
(3)
ρr ( n ) = 1 +
u
u
n
n
−
+
1
1
, n ∈ N,
y dlq v ∈ V, v = ( n1 , n2 , … , ns )
ρr v( ) =
i
s
r in
=
∑
1
ρ ( )1
.
Lehko vydet\, çto ρ4 ≡ ρ.
Funkcyy ρr yspol\zovalys\ dlq opysanyq standartn¥x xarakterov lokal\-
no-skalqrn¥x predstavlenyj nekotor¥x typov hrafov (sm. [1, 5]).
V rabote [1] poluçen¥ sledugwye svojstva funkcyj ρr .
PredloΩenye 1. Dlq r > 4
ρr ( n ) =
( )( )λ λ
λ
+ −
−+
1 1
11
n
n , (4)
hde
λ =
r r r− + −2 4
2
2
.
PredloΩenye 2. Pry fyksyrovannom r ∈ Z uravnenye
ρr ( n1 , n2 , … , ns ) = r (5)
ymeet sledugwye reßenyq:
( , , , )1 1 1…
r
� �� �� , ( , , , )2 2 2
1
…
−r
� �� �� , ( , , , , )1 3 3 3
1
…
−r
� ��� ��� , ( , , , , , )1 2 5 5 5
1
…
−r
� ��� ��� .
Pry r ∈ Q \ Z uravnenye (5) reßenyj ne ymeet.
Zdes\ m¥ ukaΩem bolee prostoj put\ zadanyq funkcyj ρr . PokaΩem, çto
ρr ( n + 1 ) =
r
r nr− ρ ( )
(6)
dlq vsex r ∈ N ∪ { 0 }.
Dejstvytel\no, po formule (4)
r
r nr− ρ ( )
=
r
r n n− + − −+( )( ) ( )λ λ λ1 1 11 ;
tak kak r = ( λ + 1 )
2
/ λ y λ ≠ 1, poslednee ravenstvo pryvodytsq k vydu
( )( )
( )( ) ( )
λ λ
λ λ λ λ
+ −
+ − − −+
1 1
1 1 11
n
n n =
( )( )λ λ
λ
+ −
−
+
+
1 1
1
1
2
n
n = ρr ( n + 1 ),
çto y trebovalos\ pokazat\.
Dalee budem zadavat\ funkcyy ρr po formulam (6) dlq r ≥ 1, r ∈ R
(naçal\noe uslovye to Ωe: ρ ( 0 ) = 0). Odnako dlq 1 ≤ r < 4 λ
n
+
1
moΩet b¥t\
ravno 1 y ρr ( n ) budet ne opredeleno. Ravenstvo λ
n
+
1 = 1 ravnosyl\no λ =
1
Dannoe opredelenye neskol\ko otlyçaetsq ot takovoho v [1]: ρr ( n ) zdes\ sootvetstvugt
ρr – 4 v [1].
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 1
38 Y. K. REDÇUK
= cos
2
1
πk
n +
+ i
k
n
sin
2
1
π
+
, k = 1, n ( λ ≠ 1 ), çto oznaçaet r = 4
1
2cos
πk
n +
, k = 1, n.
Pry r = 4
1
2cos
πk
n +
, k = 1, n, budem formal\no polahat\ ρr ( n ) = ∞ y vse drob-
no-racyonal\n¥e preobrazovanyq s takym ρr ( n ) provodyt\, yspol\zuq estes-
tvenn¥j predel\n¥j perexod. V çastnosty, esly ρr ( n ) = ∞, to ρr ( n + 1 ) = 0,
yz çeho sleduet, çto pry r = 4 cos2
1
πk
n +
, k = 1, n, funkcyq ρr ( m ) peryodyçes-
kaq s peryodom n + 1.
Netrudno ubedyt\sq, çto formul¥ (3) y (4), a takΩe predloΩenye 2 ostagt-
sq spravedlyv¥my pry takom opredelenyy.
UkaΩem na ewe odyn sluçaj, hde funkcyy ρr poqvlqgtsq estestvenn¥m ob-
razom. V rabote [6] rassmatryvalys\ *-predstavlenyq *-alhebr
Pr, α = C p p p p p p er k k k
k
r
1 2
2
1
, , , ,*… = = =
=
∑ α
v H, hde e — edynyca alhebr¥, H — separabel\noe hyl\bertovo prostranstvo.
B¥lo pokazano, çto esly Σr — mnoΩestvo tex α ∈ R, pry kotor¥x P r, α ymeet
xotq b¥ odno predstavlenye, y r ≥ 4, to
Σr = Λ Λ Λ Λr r r r
r r r r r r
r r1 2
2 2
1 24
2
4
2
, , , , ,
− − + −
− −
,
hde Λr
1
, Λr
2
— dyskretn¥e mnoΩestva, kotor¥e b¥ly opysan¥ rekurrentno:
Λr
1 = 0 1
1
1
1
1
2 1 1
1
1
2
1
2
1
1 1
, ,
( ) ( )
, ,
( )
( )
( )
+
−
+
− − −
… +
− −
− −
− −
/
/
r r r r
r
r
�
,
Λr
2 =
1 1
1
2
1
1
2 1 2
1
1
2
1
2
1
1 2
, ,
( ) ( )
, ,
( )
( )
( )
+
−
+
− − −
… +
− −
− −
− −
/
/
r r r r
r
r
�
.
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 1
RAZDELQGWYE FUNKCYY, SPEKTRAL|NAQ TEORYQ HRAFOV … 39
Lehko vydet\, çto Λr
1 = ρr k( )2{ } , Λr
2 = ρr k( )2 1+{ }, k ∈ N0 , t. e.
2
Σr = ρ ρr rk
r r r r r r
r k( ) , , , ( ){ } − − + −
−{ }
2 24
2
4
2
.
V rabote [6] na katehoryqx Rep Pr, α *-predstavlenyj alhebr Pr, α vveden¥
funktor¥ Φ
+
y Φ
–
(funktor¥ Kokstera), s pomow\g kotor¥x opysan¥ vse
nepryvodym¥e *-predstavlenyq alhebr Pr, α (s toçnost\g do unytarnoj πkvy-
valentnosty) v toçkax dyskretnoho spektra mnoΩestva Σr . Tam Ωe b¥la dana
qvnaq (no dostatoçno sloΩnaq) formula dlq v¥çyslenyq Φ
+
k
( α ) = ( Φ
+
)
k
( α ).
PokaΩem, çto πta formula v termynax funkcyj ρr ymeet bolee prostoj vyd.
Dlq πtoho nam ponadobytsq sledugwaq lemma.
Lemma 1. ρr ( 2 k – 1 ) = 1 +
u
u
k
k
−1
.
Dokazatel\stvo. Esly r = 4, to
ρr ( 2 k – 1 ) = 1 +
2 2
2
k
k
−
= 1 +
k
k
−1
= 1 +
u
u
k
k
−1
.
Esly r > 4, to uk =
λ λk k
r r
−
−
−
2 4
= (sm. [1]) =
λ
λ λ
2
1 2
1
1
k
k
−
−− ( )
. Tohda
1 +
u
u
k
k
−1 = 1 +
λ
λ
λ
λ
2 2
2
1
2 1
1k
k
k
k
−
−
−
−
−
= ρr ( 2 k – 1 ).
Lemma dokazana.
PokaΩem teper\, çto
Φ
+
k
( α ) =
r k
r k
r
r
− −
− − −
ρ α
ρ α
( )
( )
2 1
2 1
.
V rabote [6] poluçeno Φ
+
k
( α ) = 1 +
a
a
k
k
−1
, hde ak zadaetsq rekurrentno:
a1 = 1, a2 = r – 1 – α, ak + 2 = ( r – 2 ) ak + 1 – ak
. Netrudno ubedyt\sq po yndukcyy,
çto ak = uk + 1 + ( 1 – α ) uk . Tohda Φ
+
k
( α ) = 1 +
a
a
k
k
−1 = 1 +
u u u
u u u
k k k
k k k
+ −
+ −
− −
+
1 1
1
α
α
=
( )3�
=
( )3�
ru u u
ru u u
k k k
k k k
− +
− +
−
−
α( )
( )
1
1
=
r k
r k
r
r
− −
− − −
ρ α
ρ α
( )
( )
2 1
2 1
, çto y trebovalos\ dokazat\.
2. Spektr¥ y yndeks¥ hrafov. Zdes\ y vsgdu dalee (esly specyal\no ne
ohovoreno protyvnoe) vse rassmatryvaem¥e hraf¥ predpolahagtsq koneçn¥my,
svqzn¥my y ne soderΩawymy petel\ y kratn¥x reber.
Pust\ Gv — mnoΩestvo verßyn, a Ge — mnoΩestvo reber hrafa G. Zada-
dym numeracyg na verßynax hrafa G : Gv = { g1 , g2 , … , gn }, n ∈ N. Oboznaçym
M ( gk ) = g gi i{ svqzana s gk }, 1 ≤ k, i ≤ n.
Matryca AG = aij i j n, ,=1
, hde
2
Vvedenye funkcyj ρr b¥lo predloΩeno A. V. Rojterom ymenno v svqzy s opysanyem πtyx
mnoΩestv.
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 1
40 Y. K. REDÇUK
ai j =
1
0
, ( ),
, ( ),
esly
esly
g M g
g M g
i j
i j
∈
∉
naz¥vaetsq matrycej smeΩnosty hrafa G.
Poskol\ku matryca AG symmetryçeskaq, nad polem C kompleksn¥x çysel
vse ee sobstvenn¥e znaçenyq dejstvytel\n¥. Lynejno uporqdoçennoe mnoΩest-
vo σ ( G ) = { λmin = λ1 ≤ λ2 ≤ … ≤ λn = λmax } sobstvenn¥x znaçenyj matryc¥ AG
naz¥vaetsq spektrom hrafa G, a çyslo ind ( G ) = λmax — yndeksom hrafa G.
Oboznaçym çerez VG lynejnoe prostranstvo nad polem R, sostoqwee yz na-
borov x = ( xi ), otoΩdestvyv pry πtom vektor x ∈ VG s funkcyej x : Gv → R,
xi = x ( gi ). ∏lement¥ x ∈ VG naz¥vagtsq G-vektoramy [5]. Matrycu smeΩ-
nosty AG moΩno rassmatryvat\ kak matrycu lynejnoho operatora v estestven-
nom bazyse prostranstva VG .
Teoryq spektrov hrafov v nastoqwee vremq dostatoçno hluboko yzuçena
(sm.P[7, 8]). V çastnosty, ymeet mesto sledugwee utverΩdenye, yzvestnoe kak
teorema Smyta.
Teorema 1 [9]. Pust\ λ = ind ( G ) dlq svqznoho hrafa G. Tohda λ < 2
tohda y tol\ko tohda, kohda G — hraf D¥nkyna (
An
, Dn
, E6
, E7
, E8
); λ = 2
tohda y tol\ko tohda, kohda G — rasßyrenn¥j hraf D¥nkyna Ãn( , D̃n , Ẽ6 ,
Ẽ7 , Ẽ8).
Zametym, çto esly G nesvqzen, to eho yndeks raven naybol\ßemu yz yn-
deksov eho svqzn¥x komponent. Ymegt mesto takΩe sledugwye utverΩdenyq
[7, 8].
PredloΩenye 3. Dlq lgboho hrafa G v¥polnqgtsq neravenstva 1 ≤
≤ ind ( G ) ≤ | Gv | – 1.
PredloΩenye 4. Yndeks λ = ind ( G ) proyzvol\noho hrafa G — prostoe
sobstvennoe znaçenye, esly y tol\ko esly hraf G svqzen, y v πtom sluçae sob-
stvennoe podprostranstvo prostranstva VG , prynadleΩawee λº, poroΩda-
etsq vektorom, vse koordynat¥ kotoroho poloΩytel\n¥.
∏tot vektor naz¥vaetsq hlavn¥m sobstvenn¥m vektorom hrafa G . Esly
λ = ind ( G ), AG = || ai j ||, to uslovye „x = ( x1 , x2 , … , xn ) — hlavn¥j sobstvenn¥j
vektor hrafa G” moΩno zapysat\ v vyde system¥ uravnenyj
λ xi =
j
n
ij ja x
=
∑
1
, i, j = 1, n. (7)
Hraf G naz¥vaetsq dvudol\n¥m, esly Gv = Gv
•
� Gv
, pryçem Gv
•
∩ G
= ∅ y
yz g ∈ Gv
•
sleduet M ( g ) ⊆ Gv
y, naoborot, yz h ∈ Gv
sleduet M ( g ) ⊆ Gv
•
.
MnoΩestvo Gv
naz¥vaetsq mnoΩestvom çetn¥x verßyn hrafa G , a mnoΩest-
vo Gv
•
— mnoΩestvom neçetn¥x verßyn hrafa G [5]. Esly hraf G dvudol\-
n¥j y snaçala zanumerovan¥ neçetn¥e, a potom çetn¥e verßyn¥, to eho matryca
smeΩnosty ymeet vyd
AG =
O B
B O
1
2
*
,
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 1
RAZDELQGWYE FUNKCYY, SPEKTRAL|NAQ TEORYQ HRAFOV … 41
hde O1
, O 2 — kvadratn¥e nulev¥e matryc¥ porqdkov | Gv
•
| y | Gv
| sootvet-
stvenno, B
*
— transponyrovannaq matryca k B.
Oçevydno, çto lgboe derevo est\ dvudol\n¥j hraf, a cykl s n verßynamy
dvudol\n¥j tohda y tol\ko tohda, kohda n çetno. (Yz yzloΩennoho sleduet,
çto dvudol\n¥my budut vse hraf¥ D¥nkyna y rasßyrenn¥e hraf¥ D¥nkyna, za
ysklgçenyem Ãn−1 pry neçetnom çysle verßyn n.)
3. Standartn¥e xarakter¥ zvezdoçn¥x hrafov. Pust\ G — dvudol\n¥j
hraf, Gv = Gv
•
� Gv
. Zafyksyruem numeracyg verßyn hrafa G tak, çto
Gv
•
= { g1 , g2 , … , gp }, Gv
= { gp + 1 , gp + 2 , … , gn }. Pust\ (v sootvetstvyy s πtoj
numeracyej) y = ( y1 , y2 , … , yn ) — hlavn¥j sobstvenn¥j vektor hrafa G, t. e.
vektor y udovletvorqet ravenstvam (7):
λ yi =
j
n
ij ja y
=
∑
1
, i, j = 1, n, (8)
hde λ = ind ( G ). Vektor y• = ( y1 , y2 , … , yp , 0, 0, … , 0 ) nazovem neçetn¥m stan-
dartn¥m vektorom, a vektor y° = ( 0, 0, … , 0, yp + 1 , yp + 2 , … , yn ) — çetn¥m
standartn¥m vektorom G. Poskol\ku hlavn¥j sobstvenn¥j vektor y opre-
delen s toçnost\g do nenulevoho dejstvytel\noho mnoΩytelq, y• y y° takΩe
opredelen¥ s toçnost\g do obweho dlq oboyx vektorov y• , y° nenulevoho
mnoΩytelq.
Preobrazovanye Kokstera v prostranstve VG est\ lynejnoe preobrazovanye
c = σgn
… σg1
, hde σg ji
x( )( ) = xj pry i ≠ j y σg ii
x( )( ) = – xi +
j g M g j
j j
x∈∑ ( )
.
Oboznaçym c• = σgp
… σg1
, c
= σgn
… σgp+1
, t. e. c = c
c•. Oçevydno, c
–
1 = c• c
y c•( )2 =
c ( )2 = id. PoloΩym ct =
…• •ccc
t
��� pry t > 0, ct =
… •ccc
t
��� pry t < 0 y c0 =
= id. Dlq G-vektorov v y w budem oboznaçat\ v � w, esly v y w lynejno
zavysym¥.
V rabote [1] poluçen¥ qvn¥e formul¥ v termynax funkcyj ρr , pokaz¥vag-
wye, kak menqgtsq çetn¥e y neçetn¥e standartn¥e vektor¥ pod dejstvyem pre-
obrazovanyj ct dlq nekotor¥x hrafov specyal\noho vyda. NyΩe m¥ dokaΩem
analohyçnoe utverΩdenye dlq lgboho dvudol\noho hrafa G.
PredloΩenye 5. Pust\ G — dvudol\n¥j hraf, r = ( ind ( G ) )
2 ≥ 4, y • y
y° — eho neçetn¥j y çetn¥j standartn¥j vektor¥, t ∈ N. Tohda ymegt mes-
to ravenstva
c2 t – 1 ( y° ) � y
r
t
y
r
+ −
•ρ ( )2 1
, c2 t ( y° ) � y
t
r
yr
+
•
ρ ( )2
,
(9)
c– ( 2 t + 1 ) ( y• ) �
y
r
t
y
r
• + −
ρ ( )2 1 , c– 2 t ( y• ) �
y
t
r
yr
• +
ρ ( )2
.
Dokazatel\stvo. DokaΩem predloΩenye po yndukcyy dlq sluçaq cm ( y• ),
hde m < 0 (v sluçae m > 0 dokazatel\stvo takoe Ωe s toçnost\g do „çet-
nosty”.)
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 1
42 Y. K. REDÇUK
Pry t = – 1 ymeem c– 1 ( y• ) = c y ( )• = c y yp
( , , , , , )1 0 0… … = y yp1, ,…( ,
x xp n+ … )1, , , hde xk =
g M g i
i k
y∈∑ ( )
= r yk , k = 1, p (formul¥ (8)). Otsgda
c– 2 ( y• ) = ( r – 1 ) y• + r y � y• + r y r ( )−1 = y• + ρr y r( )2 , poskol\ku
ρr ( 2 ) = r / ( r – 1 ).
PredpoloΩym teper\, çto formul¥ (9) spravedlyv¥ dlq vsex m ≤ 2 t. Tohda
c– ( 2 m + 1 ) ( y• ) = c
c– 2 t ( y• ) �
�
c y
t
r
yr
• +
ρ ( )2
=
c y y
t
r
y
t
r
yp
r
p
r
n
1 1
2 2
, , ,
( )
, ,
( )… …
+
ρ ρ
=
= c y y x xp p n
1 1, , , , ,… …( )+ ,
hde
xk =
g M g
i
i k
y
∈
∑
( )
–
ρr
k
t
r
y
( )2
= y r
t
rk
r−
ρ ( )2
=
r t
r
yr
k
− ρ ( )2
=
r
t
y
r
kρ ( )2 1+
,
otkuda ymeem c– ( 2 m + 1 ) ( y• ) = y• +
r
t
y
rρ ( )2 1+ .
Dalee,
c– ( 2 t + 2 ) ( y• ) = c•c– ( 2 t + 1 ) ( y• ) =
c y
r
t
y
r
•
• + +
ρ ( )2 1 =
= c y y
r
t
y
r
t
yp
r
p
r
n
•
+…
+
…
+
1 12 1 2 1
, , ,
( )
, ,
( )ρ ρ
=
= x x
r
t
y
r
t
yp
r
p
r
n1 12 1 2 1
, , ,
( )
, ,
( )
…
+
…
+
+ρ ρ
,
hde
xk =
r
t
y
r g M g
i
i k
ρ ( ) ( )2 1+ ∈
∑ – yk = y
r
tk
rρ ( )2 1
1
+
−
.
Otsgda
c– ( 2 t + 2 ) ( y• ) =
r
t
y
rρ ( )2 1
1
+
−
• +
r
t
y
rρ ( )2 1+ �
� y• +
r
t
t
r t
y
r
r
rρ
ρ
ρ( )
( )
( )2 1
2 1
2 1+
+
− + = y• +
1
2 1r
r
r t
y
r− +ρ ( ) = y• +
ρr t
r
y
( )2
.
PredloΩenye dokazano
3
.
Rassmotrym svqz\ standartn¥x vektorov dvudol\noho hrafa G s lokal\no-
skalqrn¥my predstavlenyqmy πtoho hrafa. Lokal\no-skalqrn¥e predstavle-
nyq hrafov b¥ly vveden¥ y yzuçalys\ v [5]. Napomnym nekotor¥e ponqtyq, vve-
denn¥e v πtoj rabote.
Pust\ H — katehoryq hyl\bertov¥x prostranstv, obæektamy kotoroj qvlq-
gtsq separabel\n¥e hyl\bertov¥ prostranstva, a morfyzmamy — ohranyçenn¥e
operator¥. Predstavlenye π hrafa G v H sopostavlqet kaΩdoj verßyne
3
∏ty formul¥ b¥ly nezavysymo poluçen¥ V. L. Ostrovskym dlq sluçaq zvezdoçn¥x hrafov.
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 1
RAZDELQGWYE FUNKCYY, SPEKTRAL|NAQ TEORYQ HRAFOV … 43
a ∈ Gv obæekt π ( a ) = Ha ∈ Ob H y kaΩdomu rebru γ ∈ Ge , soedynqgwemu ver-
ßyn¥ a y b, — paru vzaymosoprqΩenn¥x lynejn¥x operatorov π ( γ ) = { Γa b ,
Γb a }, hde Γa b : Hb → Ha . Oboznaçym Ag =
b M g gb bg∈∑ ( )
Γ Γ , b , g ∈ Gv . Pred-
stavlenye π naz¥vaetsq lokal\no-skalqrn¥m, esly vse operator¥ Ag skalqr-
n¥, Ag = αg IHg
, hde IHg
— edynyçn¥j operator v prostranstve Hg . Poskol\ku
operator¥ Ag ohranyçen¥, to αg ≥ 0. G -vektor f takoj, çto f ( g ) = αg dlq
vsex g ∈ Gv , naz¥vaetsq xarakterom predstavlenyq, a G-vektor d takoj, çto
d ( g ) = dim π ( g ), — razmernost\g predstavlenyq π. Zametym, çto dlq fyksy-
rovannoho predstavlenyq π razmernost\ opredelena odnoznaçno, a xarakter,
voobwe hovorq, net (on opredelen odnoznaçno na nosytele G
π
= a G∈{ v π( )a ≠
≠ 0} predstavlenyq.) Predstavlenye π naz¥vaetsq toçn¥m, esly G
π
= Gv .
V rabote [5] dlq proyzvol\noho hrafa G rassmotren¥: katehoryq Rep ( G,
H ) predstavlenyj G v katehoryy hyl\bertov¥x prostranstv, katehoryq
Rep ( G ) lokal\no-skalqrn¥x predstavlenyj, ee (polnaq) podkatehoryq Rep ( G,
d, f ) predstavlenyj s fyksyrovannoj razmernost\g d y xarakterom f. V [1]
dlq dvudol\noho hrafa G opredelen¥: katehoryq Rep ( G, �′ ) — obæedynenye
katehoryj Rep ( G, d, f ) takyx, çto f ( g ) > 0 pry vsex g ∈ M ( G
π
); katehoryq
Rep° ( G, �′ ) ⊂ Rep ( G, �′ ) — polnaq podkatehoryq predstavlenyj s xarakte-
rom f, dlq kotor¥x ( d, f ) takye, çto f ( g ) > 0 pry g ∈ ( M ( G
π
) ∪ G
π
) ∩ Gv
•
, y
analohyçnaq katehoryq Rep• ( G, �′ ); funktor Φ
, osuwestvlqgwyj πkvyva-
lentnost\ katehoryy Rep° ( G, �′ ) s soboj, takoj, çto Φ
( )f i = fi pry gi ∈ Gv
,
a esly gi ∈ Gv
•
, to pry di = 0, gi ∈ M ( G
π
) v¥polnqetsq Φ
( )f i = fi , v ostal\-
n¥x sluçaqx — Φ
( )f i = σi ( f ) ; analohyçn¥j funktor Φ
•
. TakΩe dlq lgboho
k ∈ N postroen¥ funktor¥ Φk = …
• •
ΦΦΦ
� �� ��
k
y Φ – k = …
•
ΦΦΦ
� �� ��
k
takye, çto
d ( Φt ( π ) ) = ct ( d ( π ) ), t ∈ Z.
Neotrycatel\n¥j G-vektor x naz¥vaetsq rehulqrn¥m, esly ct ( x ) neotry-
catelen pry lgbom t ∈ Z, y synhulqrn¥m — v protyvnom sluçae. Lokal\no-
skalqrnoe predstavlenye π hrafa G synhulqrno (rehulqrno), esly π neraz-
loΩymo y koneçnomerno y d ( π ) — synhulqrn¥j (rehulqrn¥j) vektor. Obæekt
( π, f ) ∈ Ob Rep ( G, �′ ) synhulqren, esly synhulqrno π.
Hruppa W, poroΩdennaq otraΩenyqmy σgi
, naz¥vaetsq hruppoj Vejlq.
Vektor x ∈ VG naz¥vaetsq ( dejstvytel\n¥m) kornem, esly dlq nekotor¥x
a ∈ Gv y w ∈ W ymeem x = w a , hde a — prostoj koren\, t. e. a a( ) = 1 y
a a( ) = 0 pry g ≠ a.
Prostejßyj obæekt v katehoryy Rep ( G, �′ ) — πto para Πg f,( ) takaq,
çto dim Πg = g ; f g( ) = 0 y f a( ) > 0 pry a ∈ M ( g ).
Teorema 2 [1]. KaΩd¥j synhulqrn¥j obæekt katehoryy Rep ( G, �′ ) pred-
stavlqetsq v vyde Φ Πm g f,( ) , hde Πg f,( ) — prostejßyj obæekt ( m ≥ 0
pry g ∈ Gv
y m ≤ 0 pry g ∈ Gv
•
). Pry πtom kaΩdoe toçnoe synhulqrnoe
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 1
44 Y. K. REDÇUK
predstavlenye G sootvetstvuet (s toçnost\g do πkvyvalentnosty) odno-
mu synhulqrnomu obæektu Rep ( G, �′ ).
Nazovem xarakter f predstavlenyq standartn¥m, esly f = ct ( y° ) yly f =
= ct ( y• ), t ∈ Z. Predstavlenye ( π, f ) so standartn¥m xarakterom f naz¥vaetsq
standartn¥m predstavlenyem, a sootvetstvugwyj obæekt katehoryy Rep ( G,
�′ ) — standartn¥m obæektom.
Sledugwee utverΩdenye xoroßo yzvestno (sm., naprymer, [10]).
Lemma 2. Esly x — dejstvytel\n¥j koren\, to lybo x > 0, lybo ( – x ) > 0.
DokaΩem sledugwee predloΩenye.
PredloΩenye 6. Esly d — poloΩytel\n¥j dejstvytel\n¥j synhulqrn¥j
koren\ hrafa G, to najdetsq takoe t ∈ Z, çto d = c gt ( ) , g ∈ Gv .
Dokazatel\stvo. Pust\ d — ne prostoj koren\ (v protyvnom sluçae polo-
Ωym t = 0) y m — naymen\ßee po modulg celoe çyslo so svojstvom cm ( d ) < 0.
Pust\, dlq opredelennosty, m > 0. Tohda cm – 1 ( d ) > 0 (lemma 2). Otsgda po-
luçaem, çto cm – 1 ( d ) — prostoj koren\ (esly b¥ cm – 1 ( d ) ymel xotq b¥ dve po-
loΩytel\n¥e koordynat¥, to koordynat¥, sootvetstvugwye sosednym s nymy
verßynam, b¥ly b¥ nulev¥my, y, prymenyv otraΩenye v odnoj yz πtyx poloΩy-
tel\n¥x koordynat, poluçym protyvoreçye s lemmoj 2). Takym obrazom, t = 1 –
– m y predloΩenye dokazano.
Teorema 3. Pust\ G — dvudol\n¥j hraf s ind ( G ) ≥ 2, d — synhulqrn¥j
dejstvytel\n¥j koren\ v G. Tohda suwestvuet edynstvennoe standartnoe
predstavlenye π razmernosty d.
Dokazatel\stvo. Suwestvovanye. Poskol\ku d — synhulqrn¥j koren\,
sohlasno predloΩenyg 6 suwestvuet t ∈ Z takoe, çto d = c gt ( ) . Tohda, uçyt¥-
vaq teoremu 2 y predloΩenye 5, ubeΩdaemsq, çto pry t ≥ 0 Φ Πt g y, ( ), a pry t ≤
≤ 0 Φ Πt g y, •( ) budut ravn¥ ( π, y ), hde y — standartn¥j xarakter, dim π = d.
Edynstvennost\. Yz formul (9) sleduet, çto esly ( π, f ) — standartn¥j
obæekt katehoryy Rep ( G, �′ ), to Φ
( , )π f — standartn¥j obæekt, esly tol\ko
π ≠ Πg , hde g ∈ Gv
, y Φ
•
( , )π f — standartn¥j obæekt, esly tol\ko π ≠ Πg ,
hde g ∈ Gv
•
.
4. Yndeks¥ zvezdoçn¥x hrafov. Putem dlyn¥ l ∈ N na hrafe G naz¥-
vaetsq uporqdoçennaq posledovatel\nost\ verßyn g gi il1 1
, ,…( )+
takaq, çto
gik
∈ M gik+( )1
, k = 1, l . Verßyn¥ gi1
y gil+1
naz¥vagtsq naçalom y koncom pu-
ty sootvetstvenno. Verßyna g ∈ Gv hrafa G naz¥vaetsq toçkoj vetvlenyq,
esly M ( g ) ≥ 3. Hraf G naz¥vaetsq zvezdoçn¥m hrafom, esly G — derevo,
ymegwee ne bolee odnoj toçky vetvlenyq. Dlq zvezdoçnoho hrafa G
mnoΩestvo Gv moΩno predstavyt\ v vyde
Gv = B0 � B1 � B2 � … � Bs ,
hde Bi ∩ Bj = ∅, i, j = 0, s , B0 = { g0 }, pryçem g0 — toçka vetvlenyq v G (esly
ona suwestvuet) y g, h ∈ Bi dlq nekotoroho i, esly y tol\ko esly put\ myny-
mal\noj dlyn¥ s naçalom v g y koncom v h ne soderΩyt g0 . MnoΩestva Bi
naz¥vagtsq vetvqmy hrafa G.
NyΩe m¥ ukaΩem na neposredstvennug svqz\ razdelqgwyx funkcyj ρ r s
yndeksamy zvezdoçn¥x hrafov.
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 1
RAZDELQGWYE FUNKCYY, SPEKTRAL|NAQ TEORYQ HRAFOV … 45
DokaΩem snaçala sledugwug lemmu.
Lemma 3. Pust\ { vn } — çyslovaq posledovatel\nost\, zadannaq rekur-
rentno dlq fyksyrovannoho dejstvytel\noho r ≥ 1 : v0 = 0, v 0 = 1, v n + 2 =
= rvn + 1 – vn . Tohda ρr ( n ) =
r n
n
v
v +1
.
Dokazatel\stvo provedem yndukcyej po n. Ymeem ρr ( 0 ) =
r
v
v
0
1
= 0.
PredpoloΩym, çto ρr ( n ) =
r n
n
v
v +1
. Tohda po formule (6)
ρr ( n + 1 ) =
r
r r n n− / +v v 1
=
r
r
n
n n
v
v v
+
+ −
1
1
=
r n
n
v
v
+
+
1
2
,
çto y trebovalos\ dokazat\.
Teorema 4. Pust\ G v = B0 � B1 � … � Bs — razbyenye zvezdoçnoho hrafa
na vetvy, | Bi | = ni , i = 1, s . Tohda ρr ( n1 , n2 , … , ns ) = r, hde r = ( ind ( G ) )
2
.
Dokazatel\stvo. Pust\ B0 = { g0 }, B k = g gk
n
k
k1 , ,…{ } , k = 1, s , pryçem
verßyn¥ v vetvqx Bk zanumerovan¥ tak, çto M gk
1( ) = 1, gi
k ∈ M gi
k
+( )1 , i =
= 1 1, nk − , gnk
∈ M ( g0 ). Pust\ y — hlavn¥j sobstvenn¥j vektor hrafa G,
yi
k = y gi
k( ), y0 = y ( g0 ), k = 1, s , i = 1, nk . Tohda systema (7) prymet vyd
λ yk
1 = yk
2 ,
λ yk
2 = yk
1 + yk
3 ,
λ yk
3 = yk
2 + yk
4 , (10)
………………………
λ yn
k
k
= yn
k
k−1
+ y0 ,
λ y0 = yn
k
1
+ … + yn
k
k
, (11)
hde r = ind ( G ).
Yz uravnenyj (10) dlq proyzvol\noj vetvy Bk ymeem y0 =
vn
k
k
y+1 1 y yn
k
k
=
= vn
k
k
y1 , hde { vi } — posledovatel\nost\, zadannaq rekurrentno: v0 = 0, v1 = 1,
vi + 2 = λ vi + 1 – vi . Tohda yn
k
k
=
v
v
n
n
k
k
y
+1
0 dlq vsex k = 1, s . Podstavlqq πty soot-
noßenyq v uravnenye (11), poluçaem
λ y0 =
k
s
n
n
k
k
y
= +
∑
1 1
0
v
v
y, uçyt¥vaq, çto y0 ≠ 0 (predloΩenye 4) y λ = r , naxodym
r =
k
s
n
n
k
k= +
∑
1 1
v
v
.
Tohda sohlano lemme 3
r =
k
s
r kn
=
∑
1
ρ ( ) = ρr ( n1 , n2 , … , ns ),
çto y trebovalos\ dokazat\.
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 1
46 Y. K. REDÇUK
1. Redçuk Y. K., Rojter A. V. Synhulqrn¥e lokal\no-skalqrn¥e predstavlenyq kolçanov v
hyl\bertov¥x prostranstvax y razdelqgwye funkcyy // Ukr. mat. Ωurn. – 2004. – 56, # 6. –
S. 796 – 809.
2. Nazarova L. A., Rojter A. V. Norma otnoßenyq, razdelqgwye funkcyy y predstavlenyq
markyrovann¥x kolçanov // Tam Ωe. – 2002. – 54, # 6. – S. 18 – 54.
3. Vlasenko M. A., Mellyt A. S., Samojlenko G. S. Ob alhebrax, poroΩdenn¥x lynejno svq-
zann¥my obrazugwymy s zadann¥m spektrom // Funkcyon. analyz y eho pryl. – 2005. – 39,
v¥p. 3. – S. 14 – 27.
4. Redçuk Y. K. Koneçnomernost\ y rost alhebr, zadann¥x polylynejno svqzann¥my obrazug-
wymy // Tam Ωe. – 2005. – 57, # 10. – S. 1435 – 1440.
5. Kruhlqk S. A., Rojter A. V. Lokal\no-skalqrn¥e predstavlenyq hrafov v katehoryy hyl\-
bertov¥x prostranstv // Funkcyon. analyz y eho pryl. – 2005. – 39, v¥p. 2. – S. 13 – 30.
6. Kruhlqk S. A., Rabanovyç V. Y., Samojlenko G. S. O summax proektorov // Tam Ωe. – 2002. –
36, v¥p. 3. – S. 20 – 35.
7. Cvetkovic D., Doob M., Sachs H. Spectra of graphs. – New York: Acad. Press, 1979. – 368 p.
8. Cvetkovic D., Rowlinson P., Simic S. Eigenspaces of graphs. – Cambridge: Cambridge Univ. Press,
1997. – 258 p.
9. Smith J. H. Some properties of the spectrum of a graph // Proc. 1969 Calgary Conf. Combinatorial
Structures and their Appl. – 1970. – P. 403 – 406.
10. Kac V. G. Infinite root systems, representations of graphs and invariant theory, II // J. Algebra. –
1982. – 78. – P. 141 – 162.
Poluçeno 19.09.2005
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 1
|