On the application of permutation groups to some combinatorial problems
We show that some properties of permutation groups can be applied to the construction of combinatorial objects with given properties.
Збережено в:
| Дата: | 2008 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська Англійська |
| Опубліковано: |
Institute of Mathematics, NAS of Ukraine
2008
|
| Онлайн доступ: | https://umj.imath.kiev.ua/index.php/umj/article/view/3270 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Репозитарії
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860509328332554240 |
|---|---|
| author | Hlukhov, O. D. Глухов, О. Д. |
| author_facet | Hlukhov, O. D. Глухов, О. Д. |
| author_sort | Hlukhov, O. D. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2020-03-18T19:49:31Z |
| description | We show that some properties of permutation groups can be applied to the construction of combinatorial objects with given properties. |
| first_indexed | 2026-03-24T02:39:21Z |
| format | Article |
| fulltext |
K O R O T K I P O V I D O M L E N N Q
UDK 517.1:519.1
O. D. Hluxov (Nac. aviac. un-t, Ky]v)
PRO ZASTOSUVANNQ HRUP PERESTANOVOK
U DEQKYX KOMBINATORNYX ZADAÇAX
We show how certain properties of permutation groups can be applied to the construction of
combinatorical objects with given properties.
Pokazano, kak nekotor¥e svojstva hrupp perestanovok moΩno prymenyt\ k konstruyrovanyg
kombynatorn¥x obæektov s zadann¥my svojstvamy.
1. Postanovka zadaçi. Nexaj hrupa G di[ na mnoΩyni U, a B = { u : u ∈ U ,
P ( u ) } — mnoΩyna elementiv mnoΩyny U, qki magt\ pevnu vlastyvist\ P. Vy-
nyka[ pytannq: çy isnu[ take peretvorennq g ∈ G , wo dlq bud\-qkoho u ∈ U
prynajmni odyn z elementiv u abo g ( u ) ma[ vlastyvist\ P ? Vyqvlq[t\sq, wo
take peretvorennq zavΩdy isnu[, qkwo, napryklad, hrupa G [ tranzytyvnog [1]
i vykonano umovu U B\ 2 = U . Xoça ce tverdΩennq neskladno dovesty (a ta-
koΩ uzahal\nyty na vypadok ne obov’qzkovo tranzytyvnyx hrup), odnak vono ma[
nyzku naslidkiv, wo dozvolqgt\, zokrema, vstanovlgvaty isnuvannq deqkyx kom-
binatornyx ob’[ktiv iz zadanymy vlastyvostqmy.
2. Osnovna teorema i ]] uzahal\nennq. Dovedemo spoçatku nastupne tverd-
Ωennq.
Lema01. Qkwo hrupa G di[ na mnoΩyni U tranzytyvno, U = n i A ,
B ⊂ U , A = k , B = r , A ∩ B = ∅ , to znajdet\sq g ∈ G take, wo
g A B( ) ∩ > rk / n .
Dovedennq. Nexaj v umovax lemy G = m , { }( )g ai j — prqmokutna ( )m n× -
matrycq, i = 1 1( )n , j = 1 1( )m , i, krim toho, s — seredn[, a t — maksymal\ne
çyslo elementiv mnoΩyny B u rqdkax g Ai( ) , i = 1 1( )n . Lehko pidraxuvaty, wo
v koΩnim stovpci matryci mistyt\sq mr / n elementiv z B i tomu v matryci zust-
riçagt\sq elementy mnoΩyny B mrk / n raziv, a otΩe, s = rk / n . Odnak u rqd-
ku, wo vidpovida[ odynyci hrupy, za umovog nema[ elementiv z B i tomu t > s ,
zvidsy i vyplyva[ tverdΩennq lemy.
Lema02. Qkwo hrupa G di[ na mnoΩyni U tranzytyvno i A ⊂ U , U =
= n, A = k, to ma[ misce nerivnist\
g G g A A∈ ≠ ∅: ( ) ∩ ≤ mk
2
/ n ,
pryçomu dlq k ≥ 2 vykonu[t\sq nerivnist\
g G g A A∈ ≠ ∅: ( ) ∩ < mk
2
/ n .
Dovedennq povnistg analohiçne dovedenng lemy81 dlq vypadku B = U \ A .
Teorema01. Qkwo hrupa G di[ na mnoΩyni U tranzytyvno, A ⊂ U i vy-
konu[t\sq nerivnist\ A 2 ≤ U , to isnu[ g ∈ G take, wo g ( A ) ∩ A = ∅ .
© O. D. HLUXOV, 2008
1568 ISSN 1027-3190. Ukr. mat. Ωurn., 2008, t. 60, # 11
PRO ZASTOSUVANNQ HRUP PERESTANOVOK … 1569
Dovedennq bezposeredn\o vyplyva[ z lemy81, qkwo poklasty B = U \ A , r =
= n – k, k = n .
Vykorystovugçy indukcig, moΩna dovesty nastupne uzahal\nennq teoremy81.
Teorema02. Qkwo hrupa G di[ na mnoΩyni U tranzytyvno i vykonu[t\sq ne-
rivnist\ A k k2 2 1/( )− ≤ U , to znajdet\sq taka mnoΩyna { }gi i
k
=0 elementiv
hrupy G, de g0 — odynycq hrupy G, wo g Aii
k
( )= 0∩ = ∅ .
Z teoremy82 vyplyva[, wo qkwo G — tranzytyvna hrupa peretvoren\ na mno-
Ωyni z n elementiv i çyslo elementiv ci[] mnoΩyny, qki ne magt\ vlastyvosti
P, ne bil\ße niΩ n k1 1 2− / , to isnugt\ k takyx peretvoren\ g g Gk1, ,… ∈ , wo
dlq bud\-qkoho elementa x zadano] mnoΩyny prynajmni odyn z elementiv x ,
g x g xk1( ), , ( )… ma[ zaznaçenu vlastyvist\.
Nastupna teorema [ uzahal\nennqm teoremy81 na vypadok ne obov’qzkovo
tranzytyvno] hrupy.
Teorema03. Qkwo hrupa G di[ na mnoΩyni U, U = Uii
p
=∑ 1
, U i — G -orbi-
ta, i = 1 1( ) p , i dlq deqko] pidmnoΩyny A ⊂ U vykonano umovu
A U Ui i
i
p
∩ 2
1=
∑ < 1,
to najdet\sq g ∈ G take, wo g ( A ) ∩ A = ∅ .
Dovedennq. Nexaj umovy teoremy vykonano i G = m . Poznaçymo Ai =
= A ∩ Ui , ti = A Ui i
2 , i = 1 1( ) p . Vykorystovugçy lemu82, lehko pokazaty,
wo dlq vsix i = 1 1( ) p vykonu[t\sq nerivnist\ g g A Ai i: ( ) ∩ ≠ ∅ ≤ m ti . Tomu
ma[ misce nerivnist\
g g A A: ( ) ∩ ≠ ∅ ≤ mti
i
p
=
∑
1
< m ,
zvidky odrazu vyplyva[ tverdΩennq teoremy.
3. Pryklad i zastosuvannq. Pryklad01. Nastupnyj pryklad pokazu[, wo
ocinka k = n u teoremi81 [ dosqΩnog. Nexaj hrupa Z16 lyßkiv po modu-
lg8816 di[ na mnoΩyni svo]x elementiv pryrodnym çynom, tobto x ( y ) = x + y, de
x, y Z∈ 16. Todi k = 4, a dlq mnoΩyny A = { 0, 1, 4, 9, 11 } z885 elementiv umo-
va lemy vΩe ne vykonu[t\sq, oskil\ky lehko pereviryty, wo dlq bud\-qkoho
g Z∈ 16 g ( A ) ∩ A ≠ ∅ .
Pryklad02. PokaΩemo, wo dlq dovil\noho n ocinku, otrymanu v teoremi81,
ne moΩna istotno pokrawyty. Dijsno, nexaj G — reberna hrupa avtomorfizmiv
povnoho p -verßynnoho hrafa [2], U — mnoΩyna joho reber, U = n , n =
= p p( ) /− 1 2 , Ai — mnoΩyna reber, wo incydentni verßyni i c\oho hrafa,
Ai = k = p – 1. Zrozumilo, wo xoça k blyz\ke do 2n , odnak dlq bud\-qkoho
g ∈ G g ( Ai ) = Aj i Ai ∩ Aj ≠ ∅, i, j = 1 1( ) p .
Pryklad03 (naslidok teoremy81). Qkwo H n — verßynno-symetryçnyj hraf
na n verßynax, a Fk — joho k -verßynnyj pidhraf i k ≤ n , to v hrafi Hn
znajdet\sq prynajmni we odyn izomorfnyj Fk pidhraf, qkyj ne ma[ z nym
spil\nyx verßyn.
Cikavi rezul\taty moΩna otrymaty, qkwo rozhlqnuty v qkosti mnoΩyny U
ISSN 1027-3190. Ukr. mat. Ωurn., 2008, t. 60, # 11
1570 O. D. HLUXOV
mnoΩynu X r( )
usix r -pidmnoΩyn deqko] mnoΩyny X , a v qkosti hrupy G sy-
metryçnu hrupu Sn , n = X , qka di[ tranzytyvno na mnoΩyni X r( )
takym çy-
nom: qkwo g Sn∈ , A X r∈ ( ) , to g ( A ) = { }( ) :g a a A∈ .
Dali nam znadobyt\sq nastupne tverdΩennq pro binomial\ni koefici[nty.
Lema03. Qkwo n, m ≥ 2, 0 < α < 1, k = [ α m ] , to spravdΩugt\sq ocinky
C n
n
2 ≥ 3
4 2
22
n
n , Cm
k ≤ ( )/em k k , Cm
k ≤ 2α∗m ,
de α∗ = α αlog ( )/2 e , zokrema, qkwo α ≤ 0,1, to α∗ < 0,48.
Zadaça pro peremißuvannq. Rozhlqnemo ( 0,1 ) -poslidovnist\ a1 , a2 , … , a2n ,
qka sklada[t\sq z odnakovoho çysla nuliv i odynyc\ (taki poslidovnosti budemo
nazyvaty zbalansovanymy). Variaci[g poslidovnosti budemo nazyvaty velyçynu,
zadanu takym çynom:
var { a1 , a2 , … , a2n } = 1
2 1
1
2 1
n
a ai i
i
n
+
=
−
−∑ .
Poslidovnist\ budemo nazyvaty maloperemißanog, qkwo ]] variaciq ne bil\ßa
niΩ 0,1. PokaΩemo, wo dlq dosyt\ velykyx n isnu[ „universal\na perestanov-
ka, wo peremiwu[“ g , tobto taka, wo zadovol\nq[ umovu: dlq bud\-qko] zba-
lansovano] maloperemißano] poslidovnosti a1 , a2 , … , a2n poslidovnist\ ag( )1 ,
ag( )2 , … , ag n( )2 uΩe ne bude maloperemißanog. Vidpovidno do teoremy81 dlq
c\oho dosyt\ ocinyty çyslo p zbalansovanyx poslidovnostej z variaci[g ne
bil\ßog niΩ 0,1 i pereviryty, wo vykonu[t\sq nerivnist\ p
2 ≤ q, de q = C n
n
2
— çyslo vsix zbalansovanyx ( 0,1 ) -poslidovnostej. Postavyvßy u vidpovidnist\
poslidovnosti z variaci[g ne bil\ßog niΩ 0,1 poslidovnist\ poçatkiv ]] sehmen-
tiv, koΩen z qkyx sklada[t\sq z nuliv abo odynyc\, i vykorystavßy lemu82 pry
m = 2n, α = 0,1, k = [ α m ] , otryma[mo spivvidnoßennq
p ≤ C n
i
i k
2
≤
∑ < 0 2 2, n C n
k ≤ 0 2 20 96, ,n n .
Tomu dlq dosyt\ velykyx n p
2 < p
2n
i, otΩe, p
2 ≤ q, wo j potribno bulo do-
vesty.
Zadaça pro kvazizbil\ßuvaçi. Rozhlqnemo teper odnu zadaçu z teori] hra-
fiv. Nexaj Hn — hraf na n verßynax iz mnoΩynamy Hn
0
verßyn i Hn
1
reber.
Valentnistg hrafa budemo nazyvaty najbil\ßu stepin\ joho verßyn. Budemo
takoΩ vykorystovuvaty poznaçennq
ρ( , )X Hn = ( ) : ( ) , ,xy xy H x X y Xn∈ ∈ ∉{ }1 , X Hn⊂ 0 .
Hraf H2n nazvemo kvazizbil\ßuvaçem, qkwo dlq bud\-qkoho X H n⊂ 2
0 ,
X = n , vykonu[t\sq nerivnist\ ρ( , )X Hn ≥ α n , de α > 0 — deqka konstan-
ta8[3]. ZauvaΩymo, wo taki hrafy vykorystovugt\ v zadaçax zabezpeçennq Ωy-
vuçosti i diahnozospromoΩnosti skladnyx texniçnyx system [4]. PokaΩemo, qk,
vykorystovugçy otrymani rezul\taty, moΩna dovesty isnuvannq kvazizbil\ßuva-
çiv H2n valentnosti 4 dlq bud\-qkyx dosyt\ velykyx n . Nexaj Z2n — hraf,
wo [ prostym cyklom porqdku 2 n , Z n2
0 = { 1, 2, … , 2n } , g Z n( )2 — hraf, wo
oderΩu[t\sq iz hrafa Z2n perestanovkog g mnoΩyny joho verßyn, pryçomu
qkwo v hrafi Z2n [ rebro ( i, j ) , to v hrafi g Z n( )2 [ rebro ( )( ), ( )g i g j . Vy-
ISSN 1027-3190. Ukr. mat. Ωurn., 2008, t. 60, # 11
PRO ZASTOSUVANNQ HRUP PERESTANOVOK … 1571
bravßy zhidno z teoremog81 potribnu perestanovku g , pobudu[mo kvazizbil\ßu-
vaç H2n takym çynom: H2n = Z g Zn n2 2∪ ( ). Cg konstrukcig budemo nazyvaty
„sklejkog dvox hrafiv za dopomohog perestanovky”. Dovedennq isnuvannq ne-
obxidno] perestanovky g zvodyt\sq teper do pidraxunku çysla
p = X X Z X n X Z nn n: , , ( , )⊂ = <{ }2
0
2ρ α
pry α = 0, 1 i perevirky nerivnosti p
2 ≤ q, de q = C n
n
2 i, takym çynom, prak-
tyçno povtorg[ mirkuvannq z zadaçi pro peremißuvannq.
Tut vynyka[ pytannq pro velyçynu konstanty α pry obmeΩenni valentnosti
kvazizbil\ßuvaça H2n . Zastosuvavßy zamist\ teoremy81 teoremu82 i skle]vßy za-
mist\ dvox cykliv k cykliv dlq deqkoho fiksovanoho k , pokaΩemo, wo moΩna
vzqty α = 0,327. Dijsno, zhidno z lemog83 ma[mo nerivnist\ p ≤ 2 2 2α αn n∗
.
Lehko pereviryty, wo qkwo α = 0,327, to α∗ < 1 i, vzqvßy k > 1 2 1/ ( )− ∗α ,
dlq dosyt\ velykyx n otryma[mo nerivnist\ p k k2 2 1/( )− < q , q = C n
n
2 . Takym
çynom, zhidno z teoremog82 dlq dosyt\ velykyx n isnugt\ kvazizbil\ßuvaçi H2n
obmeΩeno] valentnosti z konstantog α = 0,327 (wopravda, valentnist\ hrafa
pry takij konstanti dorivng[ 1104 ) .
Zadaça pro zbil\ßuvaçi. Vykorystovugçy teoremu83, moΩna dovesty isnu-
vannq hrafiv, wo [ zbil\ßuvaçamy [5] valentnosti884, analohiçno tomu, qk za do-
pomohog teoremy81 bulo dovedeno isnuvannq kvazizbil\ßuvaçiv. Nahada[mo, wo
hraf Hn nazyva[t\sq zbil\ßuvaçem, qkwo dlq bud\-qkoho X Hn⊂ 0 , X n≤ / 2
vykonu[t\sq nerivnist\ ρ( , )X Hn ≥ α X , de α > 0 — deqka konstanta.
Dijsno, poklademo Zn
0 = { 1, 2, … , n } , U = X X Z X nn: , /⊂ ≤{ }0 2 , A =
= X X U: ,∈{ ρ α( , )X Z Xn < } i nexaj na mnoΩyni U di[ symetryçna hrupa G =
= Sn tak, qk opysano vywe; U Up1, ,… — ]] orbity, p = [ ]/n 2 . Todi pry 1 ≤ k ≤
≤ n / 2 vykonugt\sq nastupni spivvidnoßennq:
A Uk∩ 2 < Cn
j
j k≤
∑
α
2
< α α α2 2 2k en k k( )/ , Uk = Cn
k ≥ ( )/n k k .
Elementarni ocinky pokazugt\, wo dlq dosyt\ velykyx n i dosyt\ malyx α
vykonu[t\sq nerivnist\ A U Uk k∩ 2 < 2 / n . Teper dlq dovedennq isnuvannq
zbil\ßuvaçiv dosyt\ zastosuvaty teoremu83 i konstrukcig „sklejky dvox hrafiv
za dopomohog perestanovky”.
1. Xoll M. Teoryq hrupp. – M.: Yzd-vo ynostr. lyt., 1962.
2. Xarary F. Teoryq hrafov. – M.: Myr, 1973. – 337 s.
3. Alon N. Eigenvalues and expanders // Combinatorica. – 1986. – 6, # 2. – P. 83 – 96.
4. Hluxov A. D. Dyahnozosposobnost\, svqznostnaq funkcyq y spektr hrafa // ∏lektron. mo-
delyrovanye. – 1995. – # 2. – S.892 – 94.
5. Hluxov O. D. DoslidΩennq isnuvannq deqkyx kombinatornyx ob’[ktiv metodamy teori] hrup
perestanovok // Tezy dop. 1-ho Ukr. mat. konhresu. – Ky]v, 2001. – 2001. – S.862 – 63.
OderΩano 19.10.06
ISSN 1027-3190. Ukr. mat. Ωurn., 2008, t. 60, # 11
|
| id | umjimathkievua-article-3270 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | Ukrainian English |
| last_indexed | 2026-03-24T02:39:21Z |
| publishDate | 2008 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/20/a0aca0dafaa6aee1d119246034117f20.pdf |
| spelling | umjimathkievua-article-32702020-03-18T19:49:31Z On the application of permutation groups to some combinatorial problems Про застосування груп перестановок у деяких комбінаторних задачах Hlukhov, O. D. Глухов, О. Д. We show that some properties of permutation groups can be applied to the construction of combinatorial objects with given properties. Показано, как некоторые свойства групп перестановок можно применить к конструированию комбинаторных объектов с заданными свойствами. Institute of Mathematics, NAS of Ukraine 2008-11-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/3270 Ukrains’kyi Matematychnyi Zhurnal; Vol. 60 No. 11 (2008); 1568–1571 Український математичний журнал; Том 60 № 11 (2008); 1568–1571 1027-3190 uk en https://umj.imath.kiev.ua/index.php/umj/article/view/3270/3286 https://umj.imath.kiev.ua/index.php/umj/article/view/3270/3287 Copyright (c) 2008 Hlukhov O. D. |
| spellingShingle | Hlukhov, O. D. Глухов, О. Д. On the application of permutation groups to some combinatorial problems |
| title | On the application of permutation groups to some combinatorial problems |
| title_alt | Про застосування груп перестановок у деяких комбінаторних задачах |
| title_full | On the application of permutation groups to some combinatorial problems |
| title_fullStr | On the application of permutation groups to some combinatorial problems |
| title_full_unstemmed | On the application of permutation groups to some combinatorial problems |
| title_short | On the application of permutation groups to some combinatorial problems |
| title_sort | on the application of permutation groups to some combinatorial problems |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/3270 |
| work_keys_str_mv | AT hlukhovod ontheapplicationofpermutationgroupstosomecombinatorialproblems AT gluhovod ontheapplicationofpermutationgroupstosomecombinatorialproblems AT hlukhovod prozastosuvannâgrupperestanovokudeâkihkombínatornihzadačah AT gluhovod prozastosuvannâgrupperestanovokudeâkihkombínatornihzadačah |