Lovász number
In graph theory, the Lovász number of a graph is a real number that is an upper bound on the Shannon capacity of the graph. It is also known as Lovász theta function and is commonly denoted by , using a script form of the Greek letter theta to contrast with the upright theta used for Shannon capacity. This quantity was first introduced by László Lovász in his 1979 paper On the Shannon Capacity of a Graph.[1]
Accurate numerical approximations to this number can be computed in polynomial time by semidefinite programming and the ellipsoid method. It is sandwiched between the chromatic number and clique number of any graph, and can be used to compute these numbers on graphs for which they are equal, including perfect graphs.
Definition
Let be a graph on vertices. An ordered set of unit vectors is called an orthonormal representation of in , if and are orthogonal whenever vertices and are not adjacent in :
The Lovász number of graph is defined as follows:
Equivalent expressions
Let be a graph on vertices. Let range over all symmetric matrices such that whenever or vertices and are not adjacent, and let denote the largest eigenvalue of . Then an alternative way of computing the Lovász number of is as follows:[5]
The following method is dual to the previous one. Let range over all symmetric positive semidefinite matrices such that whenever vertices and are adjacent, and such that the trace (sum of diagonal entries) of is . Let be the matrix of ones. Then[6]
The Lovász number can be computed also in terms of the complement graph . Let be a unit vector and be an orthonormal representation of . Then[7]
Value for well-known graphs
The Lovász number has been computed for the following graphs:[8]
Graph | Lovász number |
---|---|
Complete graph | |
Empty graph | |
Pentagon graph | |
Cycle graphs | |
Petersen graph | |
Kneser graphs | |
Complete multipartite graphs |
Properties
If denotes the strong graph product of graphs and , then[9]
If is the complement of , then[10]
Lovász "sandwich theorem"
The Lovász "sandwich theorem" states that the Lovász number always lies between two other numbers that are NP-complete to compute.[11] More precisely,
The value of can be formulated as a semidefinite program and numerically approximated by the ellipsoid method in time bounded by a polynomial in the number of vertices of G.[12] For perfect graphs, the chromatic number and clique number are equal, and therefore are both equal to . By computing an approximation of and then rounding to the nearest integer value, the chromatic number and clique number of these graphs can be computed in polynomial time.
Relation to Shannon capacity
The Shannon capacity of graph is defined as follows:
For example, let the confusability graph of the channel be , a pentagon. Since the original paper of Shannon (1956) it was an open problem to determine the value of . It was first established by Lovász (1979) that .
Clearly, . However, , since "11", "23", "35", "54", "42" are five mutually non-confusable messages (forming a five-vertex independent set in the strong square of ), thus .
To show that this bound is tight, let be the following orthonormal representation of the pentagon:
However, there exist graphs for which the Lovász number and Shannon capacity differ, so the Lovász number cannot in general be used to compute exact Shannon capacities.[14]
Quantum physics
The Lovász number has been generalized for "non-commutative graphs" in the context of quantum communication.[15] The Lovasz number also arises in quantum contextuality[16] in an attempt to explain the power of quantum computers.[17]
See also
- Tardos function, a monotone approximation to the Lovász number of the complement graph that can be computed in polynomial time and has been used to prove lower bounds in circuit complexity
Notes
- ^ Lovász (1979).
- ^ A representation of vertices by standard basis vectors will not be faithful, meaning that adjacent vertices are represented by non-orthogonal vectors, unless the graph is edgeless. A faithful representation in is also possible by associating each vertex to a basis vector as before, but mapping each vertex to the sum of basis vectors associated with its closed neighbourhood.
- ^ If then one can always achieve a smaller objective value by restricting to the subspace spanned by vectors ; this subspace is at most -dimensional.
- ^ Lovász (1995–2001), Proposition 5.1, p. 28.
- ^ Lovász (1979), Theorem 3.
- ^ Lovász (1979), Theorem 4.
- ^ Lovász (1979), Theorem 5.
- ^ Riddle (2003).
- ^ Lovász (1979), Lemma 2 and Theorem 7.
- ^ Lovász (1979), Corollary 2 and Theorem 8.
- ^ Knuth (1994).
- ^ Grötschel, Lovász & Schrijver (1981); Todd & Cheung (2012).
- ^ Lovász (1979), Theorem 1.
- ^ Haemers (1979).
- ^ Duan, Severini & Winter (2013).
- ^ Cabello, Severini & Winter (2014).
- ^ Howard et al. (2014).
References
- Cabello, Adán; Severini, Simone; Winter, Andreas (January 27, 2014), "Graph-theoretic approach to quantum correlations", Physical Review Letters, 112 (4): 040401, arXiv:1401.7081, doi:10.1103/PhysRevLett.112.040401, PMID 24580419, 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:10.1109/TIT.2012.2221677, S2CID 4690143
- Grötschel, Martin; Lovász, László; Schrijver, Alexander (1981), "The ellipsoid method and its consequences in combinatorial optimization" (PDF), Combinatorica, 1 (2): 169–197, doi:10.1007/BF02579273, S2CID 43787103, archived from the original (PDF) on 2011-07-18
- Grötschel, Martin; Lovász, László; Schrijver, Alexander (1988), "Chapter 9.3. Orthonormal Representations", Geometric Algorithms and Combinatorial Optimization (2 ed.), Springer, p. 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, archived from the original on 2012-03-05
- Howard, Mark; Wallman, Joel; Veitch, Victor; Emerson, Joseph (19 June 2014), "Contextuality supplies the 'magic' for quantum computation", Nature, 510 (7505): 351–5, arXiv:1401.4174, Bibcode:2014Natur.510..351H, doi:10.1038/nature13460, 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), "Chapter 3.2: Chromatic number, cliques, and perfect graphs", An Algorithmic Theory of Numbers, Graphs and Convexity, Society for Industrial and Applied Mathematics, p. 75, ISBN 978-0-89871-203-2
- Lovász, László (1995–2001), Semidefinite programs and combinatorial optimization (lecture notes)
- Riddle, Marcia Ling (2003), Sandwich Theorem and Calculation of the Theta Function for Several Graphs (M.S. thesis), Brigham Young University, hdl:1877/etd181
- Shannon, Claude (1956), "The zero error capacity of a noisy channel", IRE Transactions on Information Theory, 2 (3): 8–19, doi:10.1109/TIT.1956.1056798
- Todd, Mike; Cheung, Sin-Shuen (February 21, 2012), "Lecture 9: SDP formulations of the Lovász theta function", Lecture Notes for OR6327, Semidefinite Programming (PDF), Cornell University