Numer Lovásza

W teorii grafów liczba Lovásza grafu jest liczbą rzeczywistą , która jest górną granicą pojemności wykresu Shannona . Jest również znany jako funkcja theta Lovásza i jest powszechnie oznaczany przez , $theta,$ formy pisma greckiej litery aby pionowym theta używanym dla pojemności Shannona Ta ilość została po raz pierwszy wprowadzona przez László Lovásza w swoim artykule z 1979 r. On the Shannon Capacity of a Graph .

Dokładne przybliżenia liczbowe tej liczby można obliczyć w czasie wielomianowym za pomocą programowania półokreślonego i metody elipsoidy . Jest umieszczona pomiędzy liczbą chromatyczną a liczbą klik dowolnego wykresu i może być używana do obliczania tych liczb na wykresach, dla których są one równe, w tym na wykresach doskonałych .

Definicja

Niech będzie wykresem na $\$ . $Displaystyle G = (V, E)}$ Uporządkowany zestaw wektorów jednostkowych $U$$\ Displaystyle U = (u_ {i} \ mid i \ in V) \ podzbiór \ mathbb {R}$ ortonormalną reprezentacją G ${\ Displaystyle G}$ w ${\ Displaystyle \ mathbb {R} ^ {N}}$ , jeśli ${\ Displaystyle u_ {i}}$ i $\ Displaystyle u_ {j}}$ są ortogonalne, gdy wierzchołki ${ \ displaystyle i}$ i nie sąsiadują ze sobą w: $G$$displaystyle$ }

$${\ Displaystyle u_ {i} ^ {\ operatorname {T}} u_ {j} = {\ rozpocząć {przypadki} 1 i {\ tekst {jeśli}} i = j, \\ 0, & {\ tekst {jeśli }}ij\notin E.\end{przypadki}}}$$

Oczywiście każdy wykres dopuszcza reprezentację ortonormalną z $displaystyle$$\ mathbb {R} ^ {N}$ wierzchołki za pomocą różnych wektorów ze standardowej podstawy . $W zależności od$$wykresu$ może być możliwe przyjęcie znacznie mniejszej niż liczba .

Liczba Lovásza wykresu jest zdefiniowana w następujący sposób: $displaystyle \ vartheta$$}$

$${\ Displaystyle \ vartheta (G) = \ min _ {c, U} \ max _ {i \ w V} {\ frac {1}{(c^{\mathrm {T}}u_{i})^{2}}},}$$

gdzie jest $wektorem$ jednostkowym w $}}$$Displaystyle$ ^ { i jest ortonormalną reprezentacją $} styl wyświetlania \mathbb {R} ^{N}}$${\$ . Tutaj minimalizacja jest niejawnie wykonywana również w wymiarze , jednak bez utraty ogólności wystarczy wziąć pod uwagę $displaystyle$$N = n}$ . Intuicyjnie odpowiada to $minimalizacji$ półkąta obrotowego stożka zawierającego wszystkie wektory reprezentujące ortonormalną . Jeśli optymalnym kątem jest ${\ Displaystyle \ phi}$ , to ${\ Displaystyle \ vartheta (G) = 1 / \ cos ^ {2} \ phi}$ i ${\ Displaystyle c}$ odpowiada osi symetrii stożka.

Równoważne wyrażenia

Niech będzie wykresem na $\$ . $Displaystyle G = (V, E)}$ Niech obejmuje wszystkie $}$ macierze takie, że za ${\ Displaystyle a_ {ij} = 1$$j }$$ja$ { lub wierzchołki ${\ displaystyle i}$ i $sąsiadują$$oznaczają$ i niech największą wartość własną ZA $A$ } Następnie alternatywny sposób obliczenia liczby Lovásza z ${\ displaystyle G}$ następujący: sol

$${\ Displaystyle \ vartheta (G) = \ min _ {A} \ lambda _ {\ max} (A).}$$

Poniższa metoda jest podwójna w stosunku do poprzedniej. Niech obejmuje wszystkie symetryczne dodatnie $\ Displaystyle b_ {ij} = 0}$ macierze takie, że $jot$ { $wierzchołki$ ja $i}$${\ displaystyle j}$ sąsiadują ze sobą i są takie, że ślad (suma wpisów ukośnych) ${\ displaystyle B}$ to ${\ Displaystyle \ operatorname {Tr} (B) = 1}$ . Niech będzie macierzą jedynek $razy n$$}$ . Następnie

$${\ Displaystyle \ vartheta (G) = \ max _ {B} \ operatorname {Tr} (BJ).}$$

Tutaj ${\ Displaystyle \ operatorname {Tr} (BJ)}$ jest tylko sumą wszystkich wpisów ${\ displaystyle \ operatorname {Tr} (BJ)}$ .

Liczbę Lovásza można obliczyć również za pomocą wykresu dopełniacza ${\ displaystyle {\ bar {G}}}$ . Niech ${\ Displaystyle d}$ będzie wektorem jednostkowym i będzie ortonormalną reprezentacją $)}$$Displaystyle U = (u_ {i} \$ . Następnie

$${\ Displaystyle \ vartheta (G) = \ max _ {d, U} \ suma _ {i \ in V} (d ^ {\ operatorname {T}} u_ {i}) ^ {2}.}$$

Wartość dla dobrze znanych wykresów

Liczbę Lovásza obliczono dla następujących wykresów:

Wykres	Numer Lovásza
Kompletny wykres	${\ Displaystyle \ vartheta (K_ {n}) = 1}$
Pusty wykres	${\ Displaystyle \ vartheta ({\ bar {K}} _ {n}) = n}$
Wykres pięciokąta	${\ Displaystyle \ vartheta (C_ {5}) = {\ sqrt {5}}}$
Wykresy cykli	${\ Displaystyle \ vartheta (C_ {n}) = {\ rozpocząć {przypadki }{\frac {n\cos(\pi /n)}{1+\cos(\pi /n)}}&{\text{for nieparzysty }}n,\\{\frac {n}{2} }&{\text{nawet }}n\end{przypadków}}}$
wykres Petersena	${\ Displaystyle \ vartheta (KG_ {5,2}) = 4}$
wykresy Knesera	${\ Displaystyle \ vartheta (KG_ {n, k}) = {\ binom {n-1} {k-1}}}$
Kompletne grafy wieloczęściowe	${\ Displaystyle \ vartheta (K_ {n_ {1}, \ kropki, n_ {k}}) = \ max _ {1 \ równoważnik i\równik k}n_{i}}$

Nieruchomości

Jeśli ${\ Displaystyle G \ boxtimes H}$ oznacza silny iloczyn wykresów wykresów i ${\$$displaystyle H }$ , to sol ⊠

$${\ Displaystyle \ vartheta (G \ boxtimes H) = \ vartheta (G) \ vartheta (H).}$$

Jeśli jest dopełnieniem ${\ displaystyle {\ bar {G}}}$ , to sol ${\ displaystyle G}$

$${\ Displaystyle \ vartheta (G) \ vartheta ({\ bar {G}}) \ geq n,}$$

z równością, jeśli jest przechodnia przez wierzchołek . sol $\ displaystyle G}$

Lovász „twierdzenie o kanapce”

„ Twierdzenie o kanapce ” Lovásza stwierdza, że ​​​​liczba Lovásza zawsze leży między dwiema innymi liczbami, które są NP-zupełne do obliczenia. Dokładniej,

$${\ Displaystyle \ omega (G) \ równoważnik \ vartheta ({\ bar {G}}) \ równoważnik \ chi (G)}$$

gdzie ${\ Displaystyle \ omega (G)}$ jest liczbą kliki (wielkość największej $kliki$ ) i jest liczbą chromatyczną $)}$ { \ Displaystyle \ chi ( liczba (najmniejsza liczba kolorów potrzebnych do $pokolorowania$ wierzchołków tak , aby żadne dwa $sąsiednie wierzchołki$ otrzymały tego samego koloru)

Wartość można sformułować jako program półokreślony $i$ przybliżyć liczbowo metodą elipsoidy ograniczonym wielomianem G . W przypadku wykresów doskonałych liczba chromatyczna i liczba klik są równe, a zatem obie są równe . ${\ Displaystyle \ vartheta ({\ bar {G}})}$ . Obliczając przybliżenie ${\ Displaystyle \ vartheta ({\ bar {G}})}$ a następnie zaokrąglając do najbliższej wartości całkowitej, liczbę chromatyczną i liczbę klik tych wykresów można obliczyć w czasie wielomianowym.

Stosunek do pojemności Shannona

Pojemność Shannona wykresu jest zdefiniowana w następujący sposób: ${\ displaystyle G}$

$${\ Displaystyle \ Theta (G) = \ sup _ {k} {\ sqrt [{k}] {\ alpha (G^{k})}}=\lim _{k\rightarrow \infty }{\sqrt[{k}]{\alpha (G^{k})}},}$$

gdzie $)}$$Displaystyle$$G ^ {k}}$$G$ jest liczbą niezależności wykresu (rozmiar największego niezależnego zestawu ) i \ jest silnym iloczynem wykresu z samym sobą $k}$$displaystyle$ razy. Oczywiście, ${\ Displaystyle \ Theta (G) \ geq \ alfa (G)}$ . Jednak liczba Lovásza zapewnia górną granicę pojemności wykresu Shannona, stąd

$${\ Displaystyle \ alfa (G) \ równoważnik \ Theta (G) \ równoważnik \ vartheta (G).}$$

Wykres pięciokąta

$przykład ,$ niech kanału będzie pięciokątem . Od oryginalnej pracy Shannona (1956) określenie wartości było problemem otwartym. ${\ Displaystyle \ Theta (C_ {5})}$ . Po raz pierwszy Lovász (1979) ustalił, że ${\ Displaystyle \ Theta (C_ {5}) = {\ sqrt {5}}}$ .

Oczywiście, ${\ Displaystyle \ Theta (C_ {5}) \ geq \ alfa (C_ {5}) = 2}$ . Jednak ${\ Displaystyle \ alpha (C_ {5} ^ {2}) \ geq 5}$ , ponieważ „11”, „23”, „35”, „54”, „42” to pięć wzajemnie nie dających się pomylić komunikatów (tworzących niezależny zbiór pięciu wierzchołków w silnym kwadracie ${\ displaystyle C_ {5}}$ ), więc ${\ Displaystyle \ Theta (C_ {5}) \ geq {\ sqrt {5}}}$ .

Aby pokazać, że ta granica jest ścisła, niech będzie następującą ortonormalną reprezentacją pięciokąta: ${\ Displaystyle U = (u_ {1}, \ kropki, u_ {5})}$

$${\ Displaystyle u_ {k} = {\ rozpocząć {pmatrix} \ cos {\ theta} \\\ sin {\ theta} \ cos {\ varphi _ {k}} \\\ sin {\ theta} \ sin {\ varphi _{k}}\end{pmatrix}},\quad \cos {\theta }={\frac {1}{\sqrt[{4}]{5}}},\quad \varphi _{k} ={\frac {2\pi k}{5}}}$$

i niech do $\ Displaystyle c = (1,0,0)}$ . Korzystając z tego wyboru we wstępnej definicji liczby Lovásza, otrzymujemy ${\ Displaystyle \ vartheta (C_ {5}) \ leq {\ sqrt {5}}}$ . Stąd ${\ Displaystyle \ Theta (C_ {5}) = {\ sqrt {5}}}$ .

Istnieją jednak wykresy, dla których liczba Lovásza i pojemność Shannona różnią się, więc ogólnie liczba Lovásza nie może być używana do obliczenia dokładnych pojemności Shannona.

Fizyka kwantowa

Liczba Lovásza została uogólniona dla „nieprzemiennych grafów” w kontekście komunikacji kwantowej . Liczba Lovasza pojawia się również w kontekście kwantowym , próbując wyjaśnić moc komputerów kwantowych .

Zobacz też

• Funkcja Tardosa , monotoniczne przybliżenie liczby Lovásza na wykresie dopełniacza , które można obliczyć w czasie wielomianowym i zostało użyte do udowodnienia dolnych granic złożoności obwodu

Notatki

•    Cabello, Adán; Severini, Simone ; Winter , Andreas ( 27 stycznia 2014 ) 4998358 _ _ _ _ _ _ _ _ _ _ _ _
•   Duan, Runyao; Severini, Simone ; Winter, Andreas (2013), „Komunikacja o zerowym błędzie za pośrednictwem kanałów kwantowych, wykresy nieprzemienne i funkcja kwantowa Lovász ϑ”, IEEE Transactions on Information Theory , 59 (2): 1164–1174, arXiv : 1002,2514 , doi : 10,1109 /TIT.2012.2221677 , S2CID 4690143
•   Grotschel, Martin ; Lovász, László ; Schrijver, Alexander (1981), „Metoda elipsoidalna i jej konsekwencje w optymalizacji kombinatorycznej” (PDF) , Combinatorica , 1 (2): 169–197, doi : 10.1007/BF02579273 , S2CID 43787103 , zarchiwizowane z oryginału (PDF) na 2011-07-18
•   Grotschel, Martin ; Lovász, László ; Schrijver, Alexander (1988), „Rozdział 9.3. Reprezentacje ortonormalne”, algorytmy geometryczne i optymalizacja kombinatoryczna (wyd. 2), Springer, s. 285, ISBN 978-0-387-13624-0
• Haemers, Willem H. (1979), „On Some Problems of Lovász Concerning the Shannon Capacity of a Graph” , IEEE Transactions on Information Theory , 25 (2): 231–232, doi : 10.1109/tit.1979.1056027 , zarchiwizowane z oryginał w dniu 2012-03-05
•    Howard, Mark; Wallman, Joel; Veitch, Victor; Emerson, Joseph (19 czerwca 2014), „Kontekstualność dostarcza„ magii ”do obliczeń kwantowych” , Nature , 510 (7505): 351–5, arXiv : 1401,4174 , Bibcode : 2014Natur.510..351H , doi : 10.1038/nature13460 , PMID 24919152 , S2CID 4463585
• Knuth, Donald E. (1994), „Twierdzenie o kanapce”, Electronic Journal of Combinatorics , 1 : A1, arXiv : math/9312214 , doi : 10,37236/1193
• Lovász, László (1979), „O pojemności wykresu Shannona”, IEEE Transactions on Information Theory , IT-25 (1): 1–7, doi : 10.1109 / tit.1979.1055985
•   Lovász, László (1986), „Rozdział 3.2: Liczba chromatyczna, kliki i grafy doskonałe”, Algorytmiczna teoria liczb, wykresów i wypukłości , Towarzystwo Matematyki Przemysłowej i Stosowanej , s. 75 , ISBN 978-0-89871-203-2
• Lovász, László (1995–2001), Programy półokreślone i optymalizacja kombinatoryczna (notatki z wykładów)
• Zagadka, Marcia Ling (2003), Sandwich Theorem and Calculation of Theta Function for Kilka Graphs (praca magisterska), Brigham Young University, hdl : 1877/etd181
• Shannon, Claude (1956), „Zerowa pojemność błędu hałaśliwego kanału”, IRE Transactions on Information Theory , 2 (3): 8–19, doi : 10.1109 / TIT.1956.1056798
• Todd, Mike; Cheung, Sin-Shuen (21 lutego 2012), „Wykład 9: sformułowania SDP funkcji Lovász theta” , Notatki do wykładu dla OR6327 , Programowanie semidefinite (PDF) , Cornell University

Linki zewnętrzne

• Eric W. Weisstein , Lovász Number ( twierdzenie kanapkowe ) w MathWorld .