Separating functions, spectral theory of graphs, and locally scalar representations in Hilbert spaces
We consider the connection of the separating functions $ρ_r$ with locally scalar representations of graphs and with spectral theory of graphs.
Gespeichert in:
| Datum: | 2006 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch Englisch |
| Veröffentlicht: |
Institute of Mathematics, NAS of Ukraine
2006
|
| Online Zugang: | https://umj.imath.kiev.ua/index.php/umj/article/view/3433 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860509524070236160 |
|---|---|
| author | Redchuk, I. K. Редчук, И. К. Редчук, И. К. |
| author_facet | Redchuk, I. K. Редчук, И. К. Редчук, И. К. |
| author_sort | Redchuk, I. K. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2020-03-18T19:54:30Z |
| description | We consider the connection of the separating functions $ρ_r$ with locally scalar representations of graphs and with spectral theory of graphs. |
| first_indexed | 2026-03-24T02:42:28Z |
| format | Article |
| 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
|
| id | umjimathkievua-article-3433 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | rus English |
| last_indexed | 2026-03-24T02:42:28Z |
| publishDate | 2006 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/2b/788cc39a4704346af22fa221bdb2072b.pdf |
| spelling | umjimathkievua-article-34332020-03-18T19:54:30Z Separating functions, spectral theory of graphs, and locally scalar representations in Hilbert spaces Разделяющие функции, спектральная теория графов и локально-скалярные представления в гильбертовых пространствах Redchuk, I. K. Редчук, И. К. Редчук, И. К. We consider the connection of the separating functions $ρ_r$ with locally scalar representations of graphs and with spectral theory of graphs. Розглядається зв'язок відокремлюючих функцій $\rho_r$ з локально-скалярними зображеннями графів та зі спектральною теорією графів. Institute of Mathematics, NAS of Ukraine 2006-01-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/3433 Ukrains’kyi Matematychnyi Zhurnal; Vol. 58 No. 1 (2006); 36–46 Український математичний журнал; Том 58 № 1 (2006); 36–46 1027-3190 rus en https://umj.imath.kiev.ua/index.php/umj/article/view/3433/3606 https://umj.imath.kiev.ua/index.php/umj/article/view/3433/3607 Copyright (c) 2006 Redchuk I. K. |
| spellingShingle | Redchuk, I. K. Редчук, И. К. Редчук, И. К. Separating functions, spectral theory of graphs, and locally scalar representations in Hilbert spaces |
| title | Separating functions, spectral theory of graphs, and locally scalar representations in Hilbert spaces |
| title_alt | Разделяющие функции, спектральная теория графов и локально-скалярные представления в гильбертовых пространствах |
| title_full | Separating functions, spectral theory of graphs, and locally scalar representations in Hilbert spaces |
| title_fullStr | Separating functions, spectral theory of graphs, and locally scalar representations in Hilbert spaces |
| title_full_unstemmed | Separating functions, spectral theory of graphs, and locally scalar representations in Hilbert spaces |
| title_short | Separating functions, spectral theory of graphs, and locally scalar representations in Hilbert spaces |
| title_sort | separating functions, spectral theory of graphs, and locally scalar representations in hilbert spaces |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/3433 |
| work_keys_str_mv | AT redchukik separatingfunctionsspectraltheoryofgraphsandlocallyscalarrepresentationsinhilbertspaces AT redčukik separatingfunctionsspectraltheoryofgraphsandlocallyscalarrepresentationsinhilbertspaces AT redčukik separatingfunctionsspectraltheoryofgraphsandlocallyscalarrepresentationsinhilbertspaces AT redchukik razdelâûŝiefunkciispektralʹnaâteoriâgrafovilokalʹnoskalârnyepredstavleniâvgilʹbertovyhprostranstvah AT redčukik razdelâûŝiefunkciispektralʹnaâteoriâgrafovilokalʹnoskalârnyepredstavleniâvgilʹbertovyhprostranstvah AT redčukik razdelâûŝiefunkciispektralʹnaâteoriâgrafovilokalʹnoskalârnyepredstavleniâvgilʹbertovyhprostranstvah |