Basic exclusivity graphs in quantum correlations

Basic exclusivity graphs in quantum correlations Ad´an Cabello,1,* Lars Eirik Danielsen,2 Antonio J. L´opez-Tarrida,1 and Jos´e R. Portillo3 1Departamento de F´ısica Aplicada II, Universidad de Sevilla, E-41012 Sevilla, Spain 2Department of Informatics, University of Bergen, P.O. Box 7803, N-5020 Bergen, Norway 3Departamento de Matem´atica Aplicada I, Universidad de Sevilla, E-41012 Sevilla, Spain A fundamental problem is to understand why quantum theory only violates some noncontextuality (NC) inequalities and identify the physical principles that prevent higher-than-quantum violations. We prove that quantum theory only violates those NC inequalities whose exclusivity graphs contain, as induced subgraphs, odd cycles of length five or more, and/or their complements. In addition, we show that odd cycles are the exclusivity graphs of a well-known family of NC inequalities and that there is also a family of NC inequalities whose exclusivity graphs are the complements of odd cycles. We characterize the maximum noncontextual and quantum values of these inequalities, and provide evidence supporting the conjecture that the maximum quantum violation of these inequalities is exactly singled out by the exclusivity principle. I. INTRODUCTION Quantum contextuality, namely, the fact that the quantum correlations between the results of compatible measurements cannot be reproduced with noncontextual hidden variable (NCHV) theories [1–3] is behind a wide spectrum of applications of quantum theory (QT) to communication and computation [4–9]. Quantum contextual correlations are experimentally detected through the violation of inequalities satisfied by NCHV models, called noncontextuality (NC) inequalities [10–13]. A fundamental problem is to understand why QT only violates some NC inequalities and identify the physical principles that prevent higher-than-quantum violations of these inequalities [14–17]. In this paper we investigate this problem. In Sec. II we introduce a tool that we will use throughout the paper, namely, the exclusivity graph. In Sec. III, we present a necessary condition for the existence of quantum contextual correlations: We prove that QT violates only those NC inequalities whose exclusivity graphs contain, as induced subgraphs, odd cycles on five or more vertices and/or their complements. In Sec. IV, we show that a lower bound of the dimension (i.e., of the number of perfectly distinguishable states) of the quantum system that is used to violate an NC inequality can be obtained by identifying induced subgraphs in the exclusivity graph of the NC inequality. The result in Sec. III suggests that NC inequalities whose exclusivity graph is either an odd cycle or its complement are especially important for understanding the way QT violates NC inequalities. In Sec. V, we show that each of these types of exclusivity graphs is connected to a family of NC inequalities and provide the quantum states and measurements leading to the maximum quantum violation. Finally, in Sec. VI we present some results that suggest that the exclusivity principle, namely, that the sum of the probabilities of a set of pairwise exclusive events cannot exceed 1, explains the maximum quantum violation of all the NC inequalities discussed in Sec. V. *[email protected] II. THE EXCLUSIVITY GRAPH OF AN NC INEQUALITY Two different graphs can be associated to any given NC inequality. On one hand, the graph in which vertices represent the observables measured in the NC inequality and adjacent vertices represent those which are compatible [18]. This graph is the so-called compatibility graph. For example, consider the Clauser-Horne-Shimony-Holt (CHSH) inequality [20], β=A0B0+A0B1+A1B0−A1B1 NCHV ⩽2,(1) where AiBjdenotes the mean value of the product of the results of measuring the observables Aiand Bj, each of them with possible results either −1 or 1, and NCHV ⩽2 indicates that 2 is the maximum value for βfor NCHV theories. In this inequality there are four observables: A0,B0,A1, and B1. All possible pairs of them are compatible except for the pairs (A0,A1) and (B0,B1). Therefore, the compatibility graph is the one depicted in Fig. 1(a). On the other hand, by taking into account that ±AiBj=2[P(1,±1|i,j)+P(−1,∓1|i,j)] −1,(2) where P(a,b |i,j) is the probability of the event “the result a has been obtained when measuring Aiand the result bhas been obtained when measuring Bj,” inequality (1) can be written as S=β 2+2 =P(1,1|0,0) +P(−1,−1|0,0) +P(1,1|0,1) +P(−1,−1|0,1) +P(1,1|1,0) +P(−1,−1|1,0) +P(1,−1|1,1) +P(−1,1|1,1) NCHV ⩽3,(3) where the left-hand side is now a convex sum of probabilities of events. A new graph can be associated to the set of events, one in which the vertices represent the events and adjacent vertices represent events that cannot occur simultaneously (i.e., exclusive events). This is the so-called exclusivity graph [19]. For example, the exclusivity graph for the CHSH inequality (3) is depicted in Fig. 1(b). The interest of the exclusivity graph Gis that the maximum value of Sfor NCHV theories is exactly given by the A0 A1 B0 B 1 1,1|0,0 -1,-1|0,0 1,1|0,1 1,-1|1,1 -1,1|1,1 1,1|1,0 -1,-1|1,0 -1,-1|0,1 (b)(a) FIG. 1. (a) The compatibility graph of the CHSH experiment. (b) The exclusivity graph of the CHSH inequality (3). independence number of the graph α(G)(whichisthe maximum number of pairwise nonadjacent vertices in G), while the maximum value in QT is upper bounded (and frequently exactly given) by the Lov´ asz number of the graph ϑ(G)[19]. The important point is that any experiment producing quantum contextual correlations can be associated to an exclusivity graph Gfor which α(G)<ϑ(G). Hereafter, we will refer to a graph with this property as a quantum contextual graph (QCG), and to a graph for which α(G)=ϑ(G)asa quantum noncontextual graph (QNCG). A subgraph Hof a graph Gis said to be induced if, for any pair of vertices iand jof H,ij is an edge of Hif and only if ij is an edge of G. For example, a graph Ghas an induced pentagon if it is possible to remove from Gall but five vertices (and their corresponding edges) so that we end up with a pentagon with no additional edges. III. BASIC EXCLUSIVITY GRAPHS Result 1. The exclusivity graph of any NC inequality violated by QT contains, as induced subgraphs, odd cycles on five or more vertices and/or their complements. This result is based on two fundamental results in graph theory. The strong perfect graph theorem and the (weak) perfect graph theorem. Perfect graphs were introduced [21] in connection to the problem of the zero-error capacity of a noisy channel [22]: Shannon observed that ω(G∗n)=ω(G)n for graphs such that ω(G)=χ(G), which made the problem of characterizing the Shannon capacity of such graphs more tractable [G∗nis the disjunctive product of ncopies of G,ω(G) is the clique number, and χ(G) is the chromatic number of G; in general, ω(G)⩽χ(G)]. Berge defined perfect graphs as those graphs Gfor which ω(H)=χ(H) for each induced subgraph H⊆G. Berge observed that all odd cycles Cn with n⩾5 (known in graph theory as “odd holes”) and their complements ¯ Cn(known as “odd antiholes”) satisfy ω(G)<χ(G). From this result, Berge conjectured that a graph Gis perfect if and only if Ghas no odd hole or odd antihole as induced subgraph (strong perfect graph conjecture). This conjecture has been recently proven, and it is now known as the strong perfect graph theorem [23]. The simplest odd holes and antiholes are illustrated in Fig. 2. The perfect graph conjecture (due also to Berge), which was later proved by Lov´ asz [24] and is now known as the (weak) perfect graph theorem, states that if Gis a perfect graph, then its complement ¯ Gis also a perfect graph. 16 11 5 10 49 3 8 2 7 12 3 4 5 67 8 9 10 11 6 1 5 9 83 7 2 1 2 3 4 56 7 8 9 4 1 4 7 36 2 5 1 2 3 45 6 7 1 3 52 1 2 34 5 C5C7C9C11 C5C7C9C11 ____ 4 FIG. 2. Cjdenote the odd cycles on jvertices and ¯ Cjtheir complements. The figure depicts the cases j=5,7,9,11. Notice that C5and ¯ C5are isomorphic. Theorem 1.LetGbe the exclusivity graph of an NC inequality. If Gis a perfect graph, then Gis a QNCG and, as a consequence, the NC inequality is not violated by QT. Proof.IfGis perfect, then ω(G)=χ(G). On the other hand, according to the sandwich theorem [25], ω(G)⩽ ϑ(¯ G)⩽χ(G) for any graph G. Hence, Gperfect implies ω(G)=ϑ(¯ G)=χ(G). Given that ω(G)=α(¯ G), we obtain α(¯ G)=ϑ(¯ G), i.e., if Gis a perfect graph, then ¯ Gis a QNCG. Applying now the (weak) perfect graph theorem, if Gis perfect, then ¯ Gis also perfect. Therefore, repeating the previous argument the other way around we conclude that Gis a QNCG as well: α(G)=ϑ(G). This finishes the proof.  Corollary 1.IfGis a QCG, i.e., if Gis the exclusivity graph of an NC inequality violated by QT, then Gis not perfect. Consequently, by the strong perfect graph theorem, Gmust contain odd holes and/or odd antiholes as induced subgraphs. This proves Result 1. Observation 1. An NC inequality not violated by QT may contain an NC inequality violated by QT. This means that, even if the exclusivity graph of the initial NC inequality is not a QCG, the exclusivity graph of the initial NC inequality may have an induced subgraph that is a QCG. Observation 2. No odd cycle or complement of an odd cycle has an odd cycle or a complement of an odd cycle as an induced subgraph. This suggests that odd cycles and their complements could be used as a basis for a decomposition of any exclusivity graph. Observation 3. The basic exclusivity graphs necessary for quantum contextuality are the same basic graphs necessary for graph nonperfectness. Proof. A graph Gis called almost perfect [26,27] if there exists at least one vertex v∈V(G) such that the graph G−vobtained by deleting v(and its incident edges) is perfect. Trivially, every perfect graph is almost perfect. There are many nonperfect graphs which are almost perfect. The interesting point is that there are nonperfect graphs for which the deletion of any vertex gives rise to a perfect graph: A graph Gis minimal (or minimally) imperfect if it is not perfect but every induced subgraph H⊂Gis perfect [i.e., ω(G)<χ(G)butω(H)=χ(H),∀H⊂G,Hinduced]. Note that, as a consequence of the strong perfect graph theorem, any nonperfect graph is either an odd hole or an odd antihole, or must contain such odd holes and/or odd antiholes as induced subgraphs. Hence, the only minimal imperfect graphs are the odd holes and odd antiholes. Moreover, given that every induced subgraph H ⊂ Gm of a minimal imperfect graph Gm is perfect, then the deletion of an arbitrary vertex v ∈ V (Gm) produces an induced subgraph of Gm which is a perfect graph [28]. Therefore, minimal imperfect graphs are not only almost perfect but the only almost-perfect graphs for which almost perfectness does not depend on the vertex choice. That is why odd holes and antiholes are the necessary basic graphs for nonperfectness: Starting from an arbitrary nonperfect graph, and deleting vertex by vertex trying to preserve nonperfectness in the subsequent resulting induced subgraphs, eventually leads to a minimal imperfect graph. Since minimal imperfect graphs are also QCGs and all QCGs are nonperfect (Corollary 1), then minimal imperfect graphs are the simplest ones giving rise to quantum contextuality.  IV. BASIC EXCLUSIVITY GRAPHS AND THE DIMENSION OF THE QUANTUM SYSTEM A distinguishing feature of the complements of the odd cycles is that their presence as induced subgraphs in an exclusivity graph Gprovides valuable information about the minimum dimension that a quantum system must have in order to generate events reproducing all the relationships of exclusivity described by G. While any of the relationships of exclusivity in an odd cycle can be reproduced using a quantum three-dimensional system, this is impossible for the relationships of exclusivity described by the complement of an odd cycle with n⩾7 vertices. Result 2. If an exclusivity graph corresponding to an NC inequality has as an induced subgraph a complement of an odd cycle on n⩾5 vertices, then the quantum dimension of the systems whose events reproduce these exclusivity relationships is, at least, 2n/3. Proof. A (faithful) orthonormal representation (OR) of G is an assignment of unit vectors {|vj}n j=1to the vertices of G such that orthogonal vectors are assigned to the vertices (iff) if they are adjacent. Vectors {|vj}n j=1represent the states of the system after the corresponding events; vectors are orthogonal if (iff) events are exclusive. Let Gbe an exclusivity graph containing an odd antihole ¯ Cn as induced subgraph. To obtain a lower bound of the dimension dof the quantum system producing events whose exclusivity relationships are described exactly by G, we can study the constraints imposed by the presence of ¯ Cn. Note that for any two different vertices u,v ∈¯ Cn,N(u)= N(v), where N(i) denotes the neighborhood of vertex i(see Fig. 2). This implies that a faithful OR of Gmust assign different vectors to uand v. As a consequence, we can lower bound dby identifying subgraphs in ¯ Cnwhich are geometrically impossible in a space of lower dimension, assuming that distinct vertices are assigned distinct vectors. For example, the simplest impossible graph in d=1 consists of two nonadjacent vertices in ¯ Cn;ind=2, three vertices, one of them adjacent to the other two. From these two impossible graphs, one can recursively construct impossible graphs in any dby adding two vertices adjacent to all vertices of an impossible graph in d−2. For example, if ¯ Cn contains a square, then d>3. In brief, the graph Fobtained by deleting d/2disjoint edges from a d-vertex complete graph Kdis an impossible subgraph in dimension d−1of ¯ Cn. To lower bound d, we must consider three cases: (C1) If n=3m,m ∈N, take the subgraph Finduced in ¯ Cnby vertices {1,2,4,5,...,3i+1,3i+2,...,3(m−1) + 1,3(m−1) +2}(see Fig. 2). Fis isomorphic to K2mminus mdisjoint edges and is, therefore, an impossible graph in d=2m−1. Hence, ¯ Cnis not faithfully representable in d= 2m−1=2n 3−1=2n/3−1. The same holds true for G⊇ ¯ Cn.(C2)Ifn=3m+1,m ∈N, take the subgraph Finduced in ¯ Cnby vertices {1,2,4,5,...,3i+1,3i+2,...,3(m−1) + 1,3(m−1) +2}.Fis isomorphic to K2mminus mdisjoint edges and is, therefore, an impossible graph in d=2m−1. Hence, ¯ Cnis not faithfully representable in d=2m−1= 2n−1 3−1=2n/3−1. The same holds true for G⊇¯ Cn. (C3) If n=3m+2,m ∈N, take the subgraph Finduced in ¯ Cnby vertices {1,2,4,5,...,3i+1,3i+2,...,3(m−1) + 1,3(m−1) +2,3m+1}.Fis isomorphic to K2m+1minus mdisjoint edges and, therefore, it is an impossible graph in d=2m. Hence, ¯ Cnis not faithfully representable in d=2m= 2(n−2) 3=2n/3−1. The same holds true for G⊇¯ Cn. V. NC INEQUALITIES REPRESENTED BY BASIC EXCLUSIVITY GRAPHS Result 3. For any cycle Cnwith nodd ⩾5, there is an NC inequality such that S(Cn)NCHV ⩽α(Cn) Q ⩽ϑ(Cn),(4) where S(Cn) is a sum of probabilities of events matching the relationships of exclusivity represented by Cn, Q ⩽ϑ(Cn) indicates that its maximum value in QT is exactly ϑ(Cn), and α(Cn)=n−1 2,(5a) ϑ(Cn)=ncos π n 1+cos π n(5b) are, respectively, the independence number and the Lov´ asz number of Cn. Proof. By explicit construction. For any nodd ⩾5, the events in the following sum of probabilities of events: S(Cn)= n  i=1 P1,0|i,i +n 2,(6) where the sum in each event is taken modulo n, and numerating the vertices of Cnas in Fig. 2, have exactly the relationships of exclusivity represented by Cn. The fact that the maximum value of S(Cn) for NCHV theories is α(Cn) is proven in [19]. The fact that ϑ(Cn)is not only an upper bound of the maximum quantum value, but a value that QT actually reaches can be seen by preparing the system in the quantum state ψ|=(1,0,0) (7) and measuring the observables represented by j=|vjvj|,(8) where vj|=cos φ,sin φcos 2πj n,sin φsin 2πj n,(9) with j=1,...,n, cos2φ=ϑ(Cn) n. The vectors (9) constitute a Lov´ asz-optimum OR of Cn. An OR is Lov´ asz optimum if there is a unit vector |ψ, called handle, such that n j=1|vj|ψ|2=ϑ(G). In our case, the handle is given by Eq. (7). Result 4. For any complement of a cycle ¯ Cnwith nodd ⩾5, there is an NC inequality such that S(¯ Cn)NCHV ⩽α(¯ Cn) Q ⩽ϑ(¯ Cn),(10) where α(¯ Cn)=2,(11a) ϑ(¯ Cn)=1+cos π n cos π n.(11b) Proof.Forn=5, the proof of Result 3 is valid, since C5 and ¯ C5are isomorphic. For any nodd ⩾7, the events in the following sum of probabilities of events: S(¯ Cn)= n  i=1 P(1,0,...,0|i,i +2,...,i+n−3),(12) where the sum in each event is taken modulo n, and numerating the vertices of ¯ Cnas in Fig. 2, have all the relationships of exclusivity represented by ¯ Cn. The fact that the maximum value of S(¯ Cn) for NCHV theories is α(¯ Cn) is proven in [19]. The fact that ϑ(¯ Cn)is not only an upper bound of the maximum quantum value, but a value that QT actually reaches can be seen by preparing the system in the quantum state ψ|=(1,0,...,0) (13) and measuring the observables represented by j=|vjvj|,(14) where the kth component of vj|, denoted as vj,k, with 0 ⩽ j⩽n−1 and 0 ⩽k⩽n−3, is given by vj,0=ϑ(¯ Cn) n,(15a) vj,2m−1=Tj,m cos (Rj,m),(15b) vj,2m=Tj,m sin (Rj,m),(15c) where m=1,2,...,n−3 2and Tj,m =(−1)j(m+1)    2cos π n+(−1)m+1cos (m+1)π n ncos π n, (16a) Rj,m =j(m+1)π n.(16b)  The vectors defined by Eqs. (15) and (16) constitute a Lov´ asz-optimum OR of ¯ Cnwith handle given by Eq. (13). Note that, for every NC inequality presented in this section, the compatibility graph of the observables is isomorphic to the exclusivity graph of the events. This follows from the fact that every observable in these NC inequalities is of the form (8) and every event is of the type 1,0,...,0|i,j, . . . ,z. VI. THE EXCLUSIVITY PRINCIPLE EXPLAINS THE QUANTUM VIOLATION OF THE NC INEQUALITIES REPRESENTED BY BASIC EXCLUSIVITY GRAPHS It has been recently proved that the principle that the sum of probabilities of a set of pairwise exclusive events cannot be higher than 1 [1,17,19,29–33], which we will hereafter call the exclusivity (E) principle, exactly singles out the maximum quantum value for the NC inequality associated to C5[17]. The principle of local orthogonality [31] may be seen as the E principle restricted to Bell scenarios [32]. Note, however, that while for a given graph G, there is always an NC inequality for which QT reaches ϑ(G)[19], this is not true if “NC inequality” is replaced by “Bell inequality” [34]. A natural question, especially important in the light of Result 1, is whether the E principle may single out the maximum quantum value for the NC inequalities associated to Cnand ¯ Cnfor nodd ⩾7 presented in Sec. V. Observation 4. “[T]he evidence that the Shannon capacity of odd cycles is extremely close to the value of the Lov´ asz theta function” [35] strongly suggests that the E principle singles out the maximum quantum value for the NC inequalities (10). This implies that the E principle also singles out the maximum quantum value for the NC inequalities (4). In any case, it is very unlikely that any actual experiment would allow us to distinguish nature’s maximum violation (assumed to be given by QT) from the maximum value allowed by the E principle. Proof. Reference [19] shows that, for a given exclusivity graph G, the maximum value satisfying the E principle (applied only to one copy of G) for the sum S(G)of probabilities of events whose relationships of exclusivity are represented by Gis given by the fractional packing number of G,α∗(G,), which is equal to max i∈V(G)wi, where the maximum is taken over all 0 ⩽wi⩽1 and for all cliques (subsets of pairwise linked vertices) Cj∈, under the restriction i∈Cjwi⩽1[22,36]. When is the set of all cliques of G, then α∗(G,) is also called the Rosenfeld number p(G)[37]. As shown in [17], for vertex transitive graphs (such us, e.g., Cnand ¯ Cn), the maximum value of S(G) satisfying the E principle applied to ncopies is given by n √p(G∗n), where Gis the exclusivity graph of the NC inequality. Recall that the maximum quantum value is given by ϑ(G). For C5,p(C5)=5 2and √p(C5∗C5)=ϑ(C5)=√5, which proves that the E principle applied to two copies of C5 singles out the maximum quantum value of S(¯ C5). The whole process can be summarized in the following expression: S(¯ C5)NCHV ⩽2 Q,E2 ⩽√5E1 ⩽5 2,(17) where NCHV ⩽2 indicates that the maximum value for NCHV theories is 2, Q,E2 ⩽√5 indicates that the maximum value for QT and for theories satisfying the E principle applied to two copies of C5is √5, and E1 ⩽5 2indicates that the maximum value for theories satisfying the E principle applied to one copy of C5is 5 2. For C7, with n=1,2,3, n p(C∗n 7)=7 2. Since p(C7)=7 2, this means that, for C7, the E principle applied to two or three copies of C7does not tell us more than the E principle applied to one copy. However, the E principle applied to four copies of C7leads us to a value closer to the maximum quantum one. This follows from [38], where it is proven that 4 pC∗4 7⩽7 4 √17 ≈3.4474.(18) The situation is similar for Cnwith nodd ⩾9: the value singled out by the E principle seems to converge to the maximum quantum one as more copies of Cnare taken into account, but there is no clear evidence that this actually happens. However, note that odd cycles are sparser than their complements. As a result, when the E principle is applied to multiple copies of complements of odd cycles, the resulting value approaches the maximum quantum one much faster. Consider, for example, ¯ C7.From[39], we obtain that p(¯ C7)=7 3>p¯ C∗2 7=7 √10 >3 p¯ C∗3 7=7 3 √33.(19) Therefore, S(¯ C7)NCHV ⩽2 Q ⩽2.1099 E3 ⩽2.1824 E2 ⩽2.2136 E1 ⩽2.3333. (20) For four copies of ¯ C7, only bounds of ω(¯ C∗4 7) are known [40], but it is clear that the value is even closer to the maximum quantum one after considering the fourth copy, since 7 4 √115 ≈2.1376 ⩽4 p¯ C∗4 7⩽7 4 √108 ≈2.1714.(21) For five copies, the best bounds known [40] are also compatible with a value even closer to the maximum quantum one. The point is that there is strong evidence [35] that the Shannon capacity of odd cycles, (Cn), is extremely close to their Lov´ asz number, ϑ(Cn). This is important since lim m→∞ m p¯ C∗m n=n limm→∞ m ω¯ C∗m n=n (Cn)(22) (this holds because Cnand ¯ Cnare vertex transitive), which, if (Cn)=ϑ(Cn), would be equal to ϑ(¯ Cn), which is exactly the maximum quantum value for ¯ Cn. If the E principle singles out the maximum quantum value of inequalities (10), then it also singles out the maximum quantum value of inequalities (4). To see it, consider one experiment testing the inequality (10) for a given n, and a completely independent experiment testing the inequality (4) for the same n. Notice that the exclusivity graph of the events defined by taking one event of the first inequality and the corresponding event of the second inequality is the complete graph on nvertices, since the exclusivity graphs of the two inequalities are complementary. Therefore, the E principle imposes that the sum of the probabilities of the nevents constructed this way cannot exceed 1. Take into account that each of these probabilities is the product of the probability of the event in the first inequality times the probability of the corresponding event in the second inequality, since the corresponding experiments are independent. Assume now that the E principle predicts that the maximum of the first inequality is ϑ(¯ Cn) and that the maximum value of the first inequality is reached when all the probabilities are equal. Assuming that the maximum value of the second inequality is also reached when all the probabilities are equal, and recalling that ϑ(Cn)ϑ(¯ Cn)=n, we are led to the conclusion that the maximum value allowed by the E principle for the second inequality cannot be higher than ϑ(Cn), which is precisely the maximum value in QT.  VII. CONCLUSIONS Here we have proven that QT only violates a particular kind of NC inequalities: those whose exclusivity graph contains some basic subgraphs, odd cycles with five or more vertices and their complements (Result 1). We have also shown that the presence of some of these subgraphs provides a lower bound to the minimum dimension that a quantum system must have to make the corresponding NC inequality experimentally testable (Result 2). In addition, we have shown that there is a family of NC inequalities violated by QT whose exclusivity graphs are precisely odd cycles (Result 3). This result is not new [18,19,41]. The interesting result is that we have shown that there is another family of NC inequalities violated by QT whose exclusivity graphs are the complements of odd cycles (Result 4). We have described how to reach the maximum quantum value for each member of this family. Finally, we have shown evidences that suggest that the maximum quantum violation of the inequalities in Results 3 and 4 are singled out by the E principle. This adds new examples to the list of inequalities whose maximum quantum value is singled out by this principle [17]. The fact that the exclusivity graphs of these NC inequalities are present in the exclusivity graph of any NC inequality violated by QT (Result 1) suggests that the E principle may be fundamental for quantum correlations. ACKNOWLEDGMENTS We thank Costantino Budroni for useful comments. This work was supported by Project No. FIS2011-29400 (MINECO, Spain). APPENDIX: BASIC EXCLUSIVITY GRAPHS INSIDE THE EXCLUSIVITY GRAPHS OF SOME NC INEQUALITIES Table Ishows the number of induced basic exclusivity graphs inside some NC inequalities and Kochen-Specker (KS) proofs. The absence of induced odd antiholes may explain why the NC inequalities associated to the exclusivity graphs of type (ii) were not pointed out before. To our knowledge, the first time a type (ii) graph with n⩾7 was identified as a QCG is in [42]. TABLE I. Number of induced basic exclusivity graphs in some NC inequalities and KS proofs. The column “Graph” gives the standard name in graph theory, “Vertices” indicates its number of vertices, “Dimension” indicates the minimum dimension of the quantum system needed to define events with the corresponding exclusivity relationships. NC inequality/KS proof Graph Vertices Dimension C5C7¯ C7C9¯ C9 KCBS [11]C55310000 CHSH [20]Ci8(1,4) 8 4 8 0 0 0 0 S3[8,43]104100000 KCBS-twin [44]J(5,2) 10 6 12 0 0 0 0 Mermin [45] Complement of Shrikhande 16 8 96 0 0 0 0 KS-18 [46,47] 18 4 144 108 0 12 0 YO [48] and its tight version [49] 22 3 288 384 0 0 0 KS-24 [50] 24 4 576 576 0 192 0 KS-31 [51] 31 3 70 184 0 248 0 KS-33 [50] 33 3 72 84 0 128 0 [1] E. P. Specker, Dialectica 14, 239 (1960). [2]J.S.Bell,Rev. Mod. Phys. 38, 447 (1966). [3] S. Kochen and E. P. Specker, J. Math. Mech. 17, 59 (1967). [4] A. K. Ekert, Phys. Rev. Lett. 67, 661 (1991). [5] R. W. Spekkens, D. H. Buzacott, A. J. Keehn, B. Toner, and G. J. Pryde, Phys.Rev.Lett.102, 010401 (2009). [6] J.AndersandD.E.Browne,Phys.Rev.Lett.102, 050502 (2009). [7] H. Buhrman, R. Cleve, S. Massar, and R. de Wolf, Rev. Mod. Phys. 82, 665 (2010). [8] E. Nagali, V. D’Ambrosio, F. Sciarrino, and A. Cabello, Phys. Rev. Lett. 108, 090501 (2012). [9] A. Cabello, V. D’Ambrosio, E. Nagali, and F. Sciarrino, Phys. Rev. A 84, 030302(R) (2011). [10] A. Cabello, S. Filipp, H. Rauch, and Y. Hasegawa, Phys. Rev. Lett. 100, 130404 (2008). [11] A. A. Klyachko, M. A. Can, S. Binicio˘ glu, and A. S. Shumovsky, Phys. Rev. Lett. 101, 020403 (2008). [12] A. Cabello, Phys. Rev. Lett. 101, 210401 (2008). [13] P. Badzi ˛ag, I. Bengtsson, A. Cabello, and I. Pitowsky, Phys. Rev. Lett. 103, 050401 (2009). [14] M. Pawłowski, T. Paterek, D. Kaszlikowski, V. Scarani, A. Winter, and M. ˙ Zukowski, Nature (London) 461, 1101 (2009). [15] M. Navascu´ es and H. Wunderlich, Proc. R. Soc. A 466, 881 (2009). [16] J. Oppenheim and S. Wehner, Science 330, 1072 (2010). [17] A. Cabello, Phys. Rev. Lett. 110, 060402 (2013). [18] M. Ara´ ujo, M. T. Quintino, C. Budroni, M. Terra Cunha, and A. Cabello, Phys. Rev. A 88, 022118 (2013). [19] A. Cabello, S. Severini, and A. Winter, arXiv:1010.2163. [20] J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, Phys. Rev. Lett. 23, 880 (1969). [21] C. Berge, F¨ arbungen von Graphen, deren s¨ amtliche bzw. deren ungerade Kreise starr sind, Wiss. Zeitschrift der Martin-Luther Universit¨ at Halle-Wittenberg 10, 114 (1961). [22] C. E. Shannon, IRE Trans. Inform. Theory 2, 8 (1956). [23] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, Ann. Math. 164, 51 (2006). [24] L. Lov´ asz, Discr. Math. 2, 253 (1972). [25] D. E. Knuth, Electr. J. Comb. 1, A1 (1994). [26] M. W. Padberg, Math. Programming 6, 180 (1974). [27] M. W. Padberg, Linear Algebra Appl. 15, 69 (1976). [28] M. Preissmann and A. Seb¨ o, in Perfect Graphs, edited by B. A. Reed and J. L. Ram´ ırez-Alfons´ ın (Wiley, Chichester, 2001), p. 185. [29] R. Wright, in Mathematical Foundations of Quantum Mechanics, edited by A. R. Marlow (Academic, San Diego, 1978), p. 255. [30] E. P. Specker, http://vimeo.com/52923835. [31] T. Fritz, A. B. Sainz, R. Augusiak, J. Bohr Brask, R. Chaves, A. Leverrier, and A. Ac´ ın, Nature Communications 4, 2263 (2013). [32] J. Henson, arXiv:1210.5978. [33] A. Cabello, arXiv:1212.1756. [34] M. Sadiq, P. Badzi ˛ag, M. Bourennane, and A. Cabello, Phys. Rev. A 87, 012128 (2013). [35] B. Codenotti, I. Gerace, and G. Resta, Ars Comb. 66, 243 (2003). [36] E. R. Scheinerman and D. H. Ullman, Fractional Graph Theory (John Wiley & Sons, New York, 1997). [37] M. Rosenfeld, Proc. Am. Math. Soc. 18, 315 (1967). [38] T. Bohman and R. Holzman, IEEE Trans. Inf. Theor 49, 721 (2003). [39] A. Vesel and J. ˇ Zerovnik, Discrete Math. 12, 333 (1998). [40] A. Vesel and J. ˇ Zerovnik, Inf. Process. Lett. 81, 277 (2002). [41] Y.-C. Liang, R. W. Spekkens, and H. M. Wiseman, Phys. Rep. 506, 1 (2011). [42] A. Cabello, L. E. Danielsen, A. J. L´ opez-Tarrida, and J. R. Portillo, http://www.ii.uib.no/˜larsed/quantum_graphs/. [43] E. Amselem, L. E. Danielsen, A. J. L´ opez-Tarrida, J. R. Portillo, M. Bourennane, and A. Cabello, Phys.Rev.Lett.108, 200405 (2012). [44] A. Cabello, Phys. Rev A 87, 010104(R) (2013). [45] N. D. Mermin, Phys. Rev. Lett. 65, 1838 (1990). [46] A. Cabello, J. M. Estebaranz, and G. Garc´ ıa-Alcaine, Phys. Lett. A212, 183 (1996). [47] V. D’Ambrosio, I. Herbauts, E. Amselem, E. Nagali, M. Bourennane, F. Sciarrino, and A. Cabello, Phys. Rev. X 3, 011012 (2013). [48] S. Yu and C. H. Oh, Phys.Rev.Lett.108, 030402 (2012). [49] M. Kleinmann, C. Budroni, J.- ˚ A. Larsson, O. G¨ uhne, and A. Cabello, Phys. Rev. Lett. 109, 250402 (2012). [50] A. Peres, J. Phys. A 24, L175 (1991). [51] A. Peres, Quantum Theory: Concepts and Methods (Kluwer, Dordrecht, 1995).