Colin de Verdière grafigi o'zgarmasdir - Colin de Verdière graph invariant

Kolin de Verdierning o'zgarmasligi grafik parametrdir ${ displaystyle mu (G)}$ har qanday kishi uchun grafik G, tomonidan kiritilgan Iv Kolin de Verdier 1990 yilda. Ikkinchisining maksimal ko'pligini o'rganish sabab bo'ldi o'ziga xos qiymat albatta Shredinger operatorlari.^[1]

Ta'rif

Ruxsat bering ${ displaystyle G = (V, E)}$ bo'lishi a halqasiz oddiy grafik. Umumiylikni yo'qotmasdan taxmin qiling ${ displaystyle V = {1, dots, n }}$ . Keyin ${ displaystyle mu (G)}$ eng kattasi korank har qanday nosimmetrik matritsa ${ displaystyle M = (M_ {i, j}) in mathbb {R} ^ {(n)}}$ shu kabi:

(M1) hamma uchun ${ displaystyle i, j}$ bilan ${ displaystyle i neq j}$ : ${ displaystyle M_ {i, j} <0}$ agar ${ displaystyle {i, j } in E}$ va ${ displaystyle M_ {i, j} = 0}$ agar ${ displaystyle {i, j } notin E}$ ;
(M2) M aynan bitta salbiy xususiy qiymatga ega, ko'plik 1;
(M3) nolga teng bo'lmagan matritsa yo'q ${ displaystyle X = (X_ {i, j}) in mathbb {R} ^ {(n)}}$ shu kabi ${ displaystyle MX = 0}$ va shunday ${ displaystyle X_ {i, j} = 0}$ agar bo'lsa ${ displaystyle i = j}$ yoki ${ displaystyle M_ {i, j} neq 0}$ tutmoq.^[1]^[2]

Ma'lum bo'lgan grafik oilalarning xarakteristikasi

Colin de Verdière invariantlari bo'yicha bir nechta taniqli grafikalar oilalarini tavsiflash mumkin:

m ≤ 0 agar va faqat agar G bor qirralar yo'q;^[1]^[2]
m ≤ 1 agar va faqat agar G a chiziqli o'rmon (yo'llarning birlashishi);^[1]^[3]
m ≤ 2 agar va faqat agar G bu tashqi plan;^[1]^[2]
m ≤ 3 agar va faqat agar G bu planar;^[1]^[2]
m ≤ 4 agar va faqat agar G bu havolasiz joylashtiriladigan grafik^[1]^[4]

Xuddi shu grafikalar oilalari Kolin de Verdier grafigining o'zgarmasligi va uning tuzilishi o'rtasidagi bog'liqlikda ham namoyon bo'ladi. komplekt grafigi:

Agar an qo'shimchasi bo'lsa n-vertex grafigi chiziqli o'rmon, keyin m ≥ n − 3;^[1]^[5]
Agar an qo'shimchasi bo'lsa n-vertex grafasi tashqi tekislik, keyin m ≥ n − 4;^[1]^[5]
Agar an qo'shimchasi bo'lsa n-vertex grafasi tekis, keyin m ≥ n − 5.^[1]^[5]

Voyaga etmaganlarning grafigi

A voyaga etmagan grafasi - bu undan qirralarning qisqarishi va qirralarning va tepaliklarning yo'q qilinishi natijasida hosil bo'lgan yana bir grafik. Kolin de Verdière o'zgarmasligi kichik-monoton, ya'ni grafikaning kichik qismini olish uning o'zgarmasligini kamaytirishi yoki o'zgarishsiz qoldirishi mumkin:

Agar H ning voyaga etmaganidir G keyin

{ displaystyle mu (H) leq mu (G)}

.^[2]

Tomonidan Robertson-Seymur teoremasi, har bir kishi uchun k cheklangan to'plam mavjud H eng ko'p invariant bo'lgan grafikalar k har qanday a'zosi bo'lmagan grafikalar bilan bir xil H voyaga etmagan sifatida. Kolin de Verdier (1990) ushbu to'plamlarning ro'yxati taqiqlangan voyaga etmaganlar uchun k ≤ 3; uchun k = 4 taqiqlangan voyaga etmaganlar to'plami tarkibidagi etti grafikadan iborat Petersen oilasi, ning ikkita xarakteristikasi tufayli havolasiz joylashtiriladigan grafikalar $ m-4 $ va hech qanday Petersen oilasi kichik bo'lmagan grafikalar kabi.^[4] Uchun k = 5 taqiqlangan voyaga etmaganlar to'plamiga Heawood oilasining 78 grafigi kiradi va endi yo'q deb taxmin qilinadi.^[6]

Xromatik raqam

Kolin de Verdier (1990) Kolin de Verdière m ning o'zgarmas har qanday grafigi bo'lishi mumkin deb taxmin qilmoqda rangli eng ko'pi m + 1 rang bilan. Masalan, chiziqli o'rmonlar o'zgarmas 1 ga ega va bo'lishi mumkin 2 rangli; The tashqi planli grafikalar o'zgarmas ikkitasiga ega va 3 rangli bo'lishi mumkin; The planar grafikalar o'zgarmas 3 ga ega va (tomonidan to'rtta rang teoremasi ) 4 rangli bo'lishi mumkin.

Kolin de Verdière eng ko'p to'rttasi o'zgarmas bo'lgan grafikalar uchun taxmin to'g'ri bo'lib qoladi; bular havolasiz joylashtiriladigan grafikalar va ularning xromatik sonining ko'pi bilan beshta ekanligi bu isbotning natijasidir Nil Robertson, Pol Seymur va Robin Tomas (1993 ) ning Xadviger gumoni uchun K₆- kichik grafikalar.

Boshqa xususiyatlar

Agar grafik mavjud bo'lsa o'tish raqami ${ displaystyle k}$ , unda Kolin de Verdière eng ko'p o'zgarmasdir ${ displaystyle k + 3}$ . Masalan, ikkalasi Kuratovskiy grafikalar ${ displaystyle K_ {5}}$ va ${ displaystyle K_ {3,3}}$ ikkalasi ham bitta o'tish joyi bilan chizilgan bo'lishi mumkin va Kolin de Verdier eng ko'p to'rttasida o'zgarmas bo'ladi.^[2]

Ta'sir

Kolin de Verdière o'zgarmasligi grafaga tegishli bo'lgan bitta matritsa o'rniga grafaga mos keladigan maxsus matritsalar sinfidan aniqlanadi. Xuddi shu chiziqlar bo'yicha boshqa grafik parametrlari aniqlanadi va o'rganiladi, masalan grafikning minimal darajasi, grafikning minimal yarim darajali darajasi va grafikning minimal burilish darajasi.

Izohlar

^ ^a ^b ^v ^d ^e ^f ^g ^h ^men ^j van der Xolst, Lovash va Shriver (1999).
^ ^a ^b ^v ^d ^e ^f Kolin de Verdier (1990).
^ Kolin de Verdier (1990) bu holatni aniq aytmaydi, lekin uning ushbu grafiklarni no bilan grafikalar sifatida tavsiflashidan kelib chiqadi uchburchak grafigi yoki tirnoq voyaga etmagan.
^ ^a ^b Lovashz va Shriver (1998).
^ ^a ^b ^v Kotlov, Lovashz va Vempala (1997).
^ Xayn van der Xolst (2006). "To'rt o'lchovdagi grafikalar va to'siqlar" (PDF). Kombinatoriya nazariyasi jurnali, B seriyasi. 96 (3): 388–404. doi:10.1016 / j.jctb.2005.09.004.

Adabiyotlar

Kolin de Verdier, Iv (1990), "Sur un nouvel invariant des graphes et un critère de planarité", Kombinatoriya nazariyasi jurnali, B seriyasi, 50 (1): 11–21, doi:10.1016 / 0095-8956 (90) 90093-F. Nil Kalkin tomonidan tarjima qilingan Kolin de Verdier, Iv (1993), "Yangi grafig o'zgarmas va planarlik mezonida", yilda Robertson, Nil; Seymur, Pol (tahr.), Grafika tuzilishi nazariyasi: Proc. AMS – IMS – SIAM Kichik grafikalar bo'yicha qo'shma yozgi tadqiqot konferentsiyasi, Zamonaviy matematika, 147, Amerika matematik jamiyati, 137–147 betlar.
van der Xolst, Xayn; Lovash, Laslo; Shrijver, Aleksandr (1999), "Colin de Verdière grafik parametri", Grafika nazariyasi va kombinatorial biologiya (Balatonlelle, 1996), Bolyai Soc. Matematika. Stud., 7, Budapesht: Xanos Bolyay matematikasi. Soc., 29-85 betlar.
Kotlov, Endryu; Lovash, Laslo; Vempala, Santosh (1997), "Kolin de Verdiere soni va grafaning shar tasvirlari", Kombinatorika, 17 (4): 483–521, doi:10.1007 / BF01195002
Lovash, Laslo; Shrijver, Aleksandr (1998), "Antipodal bog'lanishlar uchun Borsuk teoremasi va bog'lanmagan grafiklarning spektral tavsifi", Amerika matematik jamiyati materiallari, 126 (5): 1275–1285, doi:10.1090 / S0002-9939-98-04244-0.
Robertson, Nil; Seymur, Pol; Tomas, Robin (1993), "Hadvigerning K uchun gumoni₆- bepul grafikalar " (PDF), Kombinatorika, 13: 279–361, doi:10.1007 / BF01202354.

[hls99-1] v ^d ^e ^f ^g ^h ^men ^j van der Xolst, Lovash va Shriver (1999).

[cdv90-2] v ^d ^e ^f Kolin de Verdier (1990).

[3] Kolin de Verdier (1990) bu holatni aniq aytmaydi, lekin uning ushbu grafiklarni no bilan grafikalar sifatida tavsiflashidan kelib chiqadi uchburchak grafigi yoki tirnoq voyaga etmagan.

[ls98-4] Lovashz va Shriver (1998).

[klv97-5] v Kotlov, Lovashz va Vempala (1997).

[6] Xayn van der Xolst (2006). "To'rt o'lchovdagi grafikalar va to'siqlar" (PDF). Kombinatoriya nazariyasi jurnali, B seriyasi. 96 (3): 388–404. doi:10.1016 / j.jctb.2005.09.004.

[1]

[2]

[3]

[4]

[5]

[6]