Lovász nummer

I grafteori är Lovász -talet för en graf ett reellt tal som är en övre gräns för grafens Shannon-kapacitet . Den är också känd som Lovász theta-funktion och betecknas vanligen med ${\displaystyle \vartheta (G)} ,$ som använder en skriftform av den grekiska bokstaven theta för att kontrastera med den upprättstående theta som används för Shannon-kapacitet. Denna kvantitet introducerades först av László Lovász i hans 1979 papper On the Shannon Capacity of a Graph .

Noggranna numeriska approximationer till detta tal kan beräknas i polynomtid genom semidefinite programmering och ellipsoidmetoden . Den är inklämd mellan det kromatiska numret och klicknumret för vilken graf som helst och kan användas för att beräkna dessa siffror på grafer där de är lika, inklusive perfekta grafer .

Definition

Låt $G=(V,E)$ vara en graf på $n$ hörn. En ordnad uppsättning av $n$ enhetsvektorer $U=(u_{i}\mid i\in V)\subset \mathbb {R} ^ {N}$ kallas en ortonormal representation av $G$ i $\mathbb {R} ^{N}$ , om $u_{i}$ och $u_{j}$ är ortogonala närhelst hörn $i$ och $j$ inte är angränsande i $G$ :

$$u_{i}^{\mathrm {T} }u_{j}={\begin{cases}1,&{\text{if }}i=j,\\0,&{\text{if }}ij\notin E.\end{cases}}$$

Uppenbarligen tillåter varje graf en ortonormal representation med $N=n$ : representerar bara hörn med distinkta vektorer från standardbasen för $\mathbb {R} ^{N}$ . Beroende på grafen kan det vara möjligt att ta $N$ betydligt mindre än antalet hörn $n$ .

Lovász -talet $\vartheta$ i graf $G$ definieras enligt följande:

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

där $c$ är en enhetsvektor i $\mathbb {R} ^{N}$ och $U$ är en ortonormal representation av $G$ i ${\ displaystyle \mathbb {R} ^{N}}$ . Här utförs minimering implicit även över dimensionen $N$ , men utan förlust av generalitet räcker det att beakta $N=n$ . Intuitivt motsvarar detta att minimera halvvinkeln för en rotationskon som innehåller alla representerande vektorer för en ortonormal representation av $G$ . Om den optimala vinkeln är $\phi$ , då $\vartheta (G)=1/\cos ^{2}\phi$ och $c$ motsvarar konens symmetriaxel.

Motsvarande uttryck

Låt $G=(V,E)$ vara en graf på $n$ hörn. Låt $A$ sträcka sig över alla $n\times n$ symmetriska matriser så att $a_{ij}=1$ när $i=j$ eller hörn $i$ och $j$ ligger inte intill varandra, och låt $\lambda _{\max }(A)$ beteckna det största egenvärdet för $A$ . Sedan är ett alternativt sätt att beräkna Lovász-talet för $G$ som följer:

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

Följande metod är dubbel mot den föregående. Låt $B$ sträcka sig över alla $n\times n$ symmetriska positiva semidefinita matriser så att $b_{ij}=0$ närhelst hörn $i$ och $j$ är intilliggande och så att spåret (summan av diagonala poster) för $B$ är $\operatorname {Tr} (B)=1$ . Låt $J$ vara $n\times n$ matrisen av ettor . Sedan

$$\vartheta (G)=\max _{B}\operatörsnamn {Tr} (BJ).$$

Här är $\operatorname {Tr} (BJ)$ bara summan av alla poster av $B$ .

Lovász-talet kan även beräknas i termer av komplementgrafen ${\bar {G}}$ . Låt $d$ vara en enhetsvektor och $U=(u_{i}\mid i\in V)$ vara en ortonormal representation av ${\bar {G}}$ . Sedan

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

Värde för välkända grafer

Lovász-talet har beräknats för följande grafer:

Graf	Lovász nummer
Komplett graf	$\vartheta (K_{n})=1$
Tom graf	$\vartheta ({\bar {K}}_{n})=n$
Pentagon graf	$\vartheta (C_{5})={\sqrt {5}}$
Cykeldiagram	$\vartheta (C_{n})={\begin{cases }{\frac {n\cos(\pi /n)}{1+\cos(\pi /n)}}&{\text{för udda }}n,\\{\frac {n}{2} }&{\text{för jämna }}n\end{case}}$
Petersen graf	$\vartheta (KG_{5,2})=4$
Kneser-grafer	$\vartheta (KG_{n,k})={\binom {n-1}{k-1}}$
Komplettera flerdelade grafer	$\vartheta (K_{n_{1},\dots,n_{k}})=\max _{1\leq i\leq k}n_{i}$

Egenskaper

Om $G\boxtimes H$ anger den starka grafprodukten av graferna $G$ och $H$ , då

$$\vartheta (G\boxtimes H)=\vartheta (G)\vartheta (H).$$

Om ${\bar {G}}$ är komplementet till $G$ , då

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

med likhet om $G$ är vertextransitiv .

Lovász "smörgåssats"

Lovász "sandwichsats" säger att Lovász-talet alltid ligger mellan två andra tal som är NP-kompletta att beräkna. Mer exakt,

$$\omega (G)\leq \vartheta ({\bar {G}})\leq \chi (G),$$

där $\omega (G)$ är klicktalet för $G$ (storleken på den största klicken ) och $\chi (G)$ är den kromatiska antal $G$ (det minsta antalet färger som behövs för att färga topparna i $G}$ displaystyle så att inga två närliggande hörn får samma färg).

Värdet på $\vartheta (G)$ kan formuleras som ett semidefinitivt program och numeriskt approximeras med ellipsoidmetoden i tid som begränsas av ett polynom i antalet hörn av G . För perfekta grafer är det kromatiska talet och klicknumret lika, och därför är båda lika med $\vartheta ({\bar {G}})$ . Genom att beräkna en approximation av $\vartheta ({\bar {G}})$ och sedan avrunda till närmaste heltal, kan det kromatiska talet och klicktalet för dessa grafer beräknas i polynomtid.

Relation till Shannon kapacitet

Shannon -kapaciteten för graf $G$ definieras enligt följande:

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

där $\alpha (G)$ är oberoendetalet för grafen $G$ (storleken på en största oberoende uppsättning av $G$ ) och $G^ {k}$ är den starka grafprodukten av $G$ med sig själv $k$ gånger. Tydligen är $\Theta (G)\geq \alpha (G)$ . Emellertid ger Lovász-talet en övre gräns för Shannon-kapaciteten av grafen, därför

$$\alpha (G)\leq \Theta (G)\leq \vartheta (G).$$

Pentagon graf

Låt till exempel förväxlingsgrafen för kanalen vara ${\displaystyle C_{5}} ,$ en femhörning . Sedan originalet av Shannon (1956) var det ett öppet problem att bestämma värdet på $\Theta (C_{5})$ . Det fastställdes först av Lovász (1979) att $\Theta (C_{5})={\sqrt {5}}$ .

Tydligen är $\Theta (C_{5})\geq \alpha (C_{5})=2$ . Men $\alpha (C_{5}^{2})\geq 5$ , sedan "11", "23", "35", "54", "42" är fem ömsesidigt icke-förväxlande meddelanden (som bildar en fem-hörn oberoende uppsättning i den starka kvadraten av $C_{5}$ ), alltså $\Theta (C_{5} )\geq {\sqrt {5}}$ .

För att visa att denna gräns är snäv, låt $U=(u_{1},\dots ,u_{5})$ vara följande ortonormala representation av femhörningen:

$$u_{k}={\begin{k}={\begin{k} 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 }}$$

och låt $c=(1,0,0)$ . Genom att använda detta val i den initiala definitionen av Lovász-tal får vi $\vartheta (C_{5})\leq {\sqrt {5}}$ . Därför är $\Theta (C_{5})={\sqrt {5}}$ .

Det finns dock grafer för vilka Lovász-talet och Shannon-kapaciteten skiljer sig åt, så Lovász-talet kan i allmänhet inte användas för att beräkna exakta Shannon-kapaciteter.

Kvantfysik

Lovász-talet har generaliserats för "icke-kommutativa grafer" i samband med kvantkommunikation . Lovasz-talet uppstår också i kvantkontextualitet i ett försök att förklara kraften hos kvantdatorer .

Se även

• Tardos-funktion , en monoton approximation till Lovász-talet för komplementgrafen som kan beräknas i polynomtid och har använts för att bevisa lägre gränser i kretskomplexitet

Anteckningar

• Cabello, Adán; Severini, Simone ; Winter, Andreas (27 januari 2014), "Graph-theoretic approach to quantum correlations" , Physical Review Letters , 112 ( 4 ): 040401, arXiv : 1401.7081 , doi : 10.1103/PhysRevLett 1.401.40.401.401.401.401 . , S2CID 34998358   
•   Duan, Runyao; Severini, Simone ; Winter, Andreas (2013), "Zero-error communication via quantum channels, non-commutative graphs and a quantum Lovász ϑ function", IEEE Transactions on Information Theory , 59 (2): 1164–1174, arXiv : 1002.2514 , doi 1.10 /TIT.2012.2221677 , S2CID 4690143
•   Grötschel, Martin ; Lovász, László ; Schrijver, Alexander (1981), "Ellipsoidmetoden och dess konsekvenser vid kombinatorisk optimering" ( PDF) , Combinatorica , 1 (2): 169–197, doi : 10.1007/BF02579273 , S2CID 43787103 från den, ( original PDF) 2011-07-18
•   Grötschel, Martin ; Lovász, László ; Schrijver, Alexander (1988), "Kapitel 9.3. Ortonormala representationer", Geometric Algorithms and Combinatorial Optimization (2 uppl.), Springer, sid. 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 från , original 2012-03-05
•    Howard, Mark; Wallman, Joel; Veitch, Victor; the 'magic' for quantum computation", Nature , 510 ( 7505): 351–5, arXiv : 1401.4174 , Bibcode : 2014Natur.510..05i : 110..35i:110..35i , PMID 24919152 , S2CID 4463585
• Knuth, Donald E. (1994), "The sandwich theorem", Electronic Journal of Combinatorics , 1 : A1, arXiv : math/9312214 , doi : 10.37236/1193
• Lovász, László (1979), "On the Shannon capacity of a graph", IEEE Transactions on Information Theory , IT-25 (1): 1–7, doi : 10.1109/tit.1979.1055985
•   Lovász, László (1986), "Kapitel 3.2: Kromatiska tal, klick och perfekta grafer", An Algorithmic Theory of Numbers, Graphs and Convexity , Society for Industrial and Applied Mathematics , sid. 75 , ISBN 978-0-89871-203-2
• Lovász, László (1995–2001), Semidefinita program och kombinatorisk optimering ( föreläsningsanteckningar)
• Riddle, Marcia Ling (2003), Sandwich Theorem and Calculation of theta Function for Several Graphs (MS-avhandling), Brigham Young University, hdl : 1877/etd181
• Shannon, Claude (1956), "The zero error capacite of a noisy channel", IRE Transactions on Information Theory , 2 (3): 8–19, doi : 10.1109/TIT.1956.1056798
• Todd, Mike; Cheung, Sin-Shuen (21 februari 2012), "Föreläsning 9: SDP-formuleringar av Lovász theta-funktionen", Lecture Notes for OR6327, Semidefinite Programming (PDF) , Cornell University

externa länkar

• Eric W. Weisstein , Lovász Number ( Sandwich Theorem ) på MathWorld .