The Kochen-Specker theorem is a fundamental result in quantum foundations that has spawned massive interest since its inception. We show that within every Kochen-Specker graph, there exist interesting subgraphs which we term $01$-gadgets, that capture the essential contradiction necessary to prove the Kochen-Specker theorem, i.e,. every Kochen-Specker graph contains a $01$-gadget and from every $01$-gadget one can construct a proof of the Kochen-Specker theorem. Moreover, we show that the $01$-gadgets form a fundamental primitive that can be used to formulate state-independent and state-dependent statistical Kochen-Specker arguments as well as to give simple constructive proofs of an ``extended'' Kochen-Specker theorem first considered by Pitowsky in .
 A. A. Abbott, C. S. Calude and K. Svozil. A variant of the Kochen-Specker theorem localising value indefiniteness. Journal of Mathematical Physics 56, 102201 (2015).
 A. A. Abbott, C. S. Calude, J. Conder and K. Svozil. Strong Kochen-Specker theorem and incomputability of quantum randomness. Phys. Rev. A 86(6), 062109 (2012).
 A. A. Klyachko, M. A. Can, S. Binicoglu and A. S. Shumovsky. Simple Test for Hidden Variables in Spin-1 Systems. Phys. Rev. Lett. 101, 020403 (2008).
 A. Cabello, S. Severini and A. Winter. Graph-Theoretic Approach to Quantum Correlations. Phys. Rev. Lett. 112, 040401 (2014).
 A. Cabello, S. Severini and A. Winter. (Non-)Contextuality of Physical Theories as an Axiom Mittag-Leffler-2010fall Report No. 8 (2010). https://arxiv.org/abs/1010.2163.
 A. A. Abbott, C. S. Calude and K. Svozil. A quantum random number generator certified by value indefiniteness. Mathematical Structures in Computer Science Vol. 24, Issue 3 (Developments of the Concepts of Randomness, Statistic and Probability), e240303 (2014).
 R. Ramanathan, F. G. S. L. Brandao, K. Horodecki, M. Horodecki, P. Horodecki and H. Wojewodka. Randomness Amplification under Minimal Fundamental Assumptions on the Devices. Phys. Rev. Lett. 117, 230501 (2016).
 F.G.S.L. Brandão, R. Ramanathan, A. Grudka, K. Horodecki, M. Horodecki, P. Horodecki, T. Szarek, and H. Wojewódka. Robust Device-Independent Randomness Amplification with Few Devices. Nat. Comm. 7, 11345 (2016).
 H. Wojewódka, F. G. S. L. Brandão, A. Grudka, M. Horodecki, K. Horodecki, P. Horodecki, M. Pawĺowski, R. Ramanathan. Amplifying the Randomness of Weak Sources Correlated with Devices. IEEE Trans. on Inf. Theory. Vol. 63, No. 11, pp. 7592-7611 (2017).
 F. Arends. A lower bound on the size of the smallest Kochen-Specker vector system. Master’s thesis, Oxford University (2009).
 F. Arends, J. Ouaknine, and C. W. Wampler. On Searching for Small Kochen-Specker Vector Systems. In: Kolman P., Kratochvíl J. (eds) Graph-Theoretic Concepts in Computer Science. WG 2011. Lecture Notes in Computer Science, vol 6986. Springer, Berlin, Heidelberg (2011).
 A. Cabello, J. Estebaranz and G. García-Alcaine. Bell-Kochen-Specker Theorem: A Proof with 18 vectors. Phys. Lett. A Vol. 212, Issue 4, 183 (1996).
 C. Held. The Kochen-Specker Theorem. The Stanford Encyclopedia of Philosophy (Fall 2016 Edition), Edward N. Zalta (ed.), (2016).
 A. Cabello. Experimentally Testable State-Independent Quantum Contextuality. Phys. Rev. Lett. 101, 210401 (2008).
 E. Hrushovski and I. Pitowsky. Generalizations of Kochen and Specker's theorem and the effectiveness of Gleason's theorem. Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics Vol. 35, Issue 2, 177-194 (2004).
 S. Yu and C. H. Oh. State-Independent Proof of Kochen-Specker Theorem with 13 Rays. Phys. Rev. Lett. 108, 030402 (2012).
 T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second Edition. The MIT Press (2001).
 L. Lovasz, M. Saks, A. Schrijver. Orthogonal representation and connectivity of graphs. Linear Algebra and its applications, 4, 114-115, 439 (1987).
 A Cabello and G Garcia-Alcaine. A hidden-variables versus quantum mechanics experiment. Journal of Phys. A: Math. and General, 28, No. 13 (1995).
 P. Badzia̧g, I. Bengtsson, A. Cabello, and I. Pitowsky. Universality of State-Independent Violation of Correlation Inequalities for Noncontextual Theories. Phys. Rev. Lett. 103, 050401 (2009).
 A. Cabello, J. R. Portillo, A. Solís, and K. Svozil. Minimal true-implies-false and true-implies-true sets of propositions in noncontextual hidden-variable theories. Phys. Rev. A 98, 012106 (2018).
 Karl Svozil, "Extensions of Hardy-type true-implies-false gadgets to classically obtain indistinguishability", Physical Review A 103 2, 022204 (2021).
 Václav Voráček and Mirko Navara, "Generalised Kochen–Specker Theorem in Three Dimensions", Foundations of Physics 51 3, 67 (2021).
 Ravishankar Ramanathan, Yuan Liu, and Paweł Horodecki, "Large violations in Kochen Specker contextuality and their applications", New Journal of Physics 24 3, 033035 (2022).
 Adán Cabello, "Converting Contextuality into Nonlocality", Physical Review Letters 127 7, 070401 (2021).
 Mohammad H. Shekarriz and Karl Svozil, "Noncontextual coloring of orthogonality hypergraphs", Journal of Mathematical Physics 63 3, 032104 (2022).
 Karl Svozil, "What Is so Special about Quantum Clicks?", Entropy 22 6, 602 (2020).
 Ravishankar Ramanathan, Michał Horodecki, Hammad Anwer, Stefano Pironio, Karol Horodecki, Marcus Grünfeld, Sadiq Muhammad, Mohamed Bourennane, and Paweł Horodecki, "Practical No-Signalling proof Randomness Amplification using Hardy paradoxes and its experimental implementation", arXiv:1810.11648.
 Karl Svozil, "Varieties of contextuality based on probability and structural nonembeddability", arXiv:2103.06110.
 Karl Svozil, "Classical predictions for intertwined quantum observables are contingent and thus inconclusive", arXiv:1808.00813.
The above citations are from Crossref's cited-by service (last updated successfully 2022-10-06 00:31:35) and SAO/NASA ADS (last updated successfully 2022-10-06 00:31:36). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.