Maximal Non-Kochen-Specker Sets and a Lower Bound on the Size of Kochen-Specker Sets

A Kochen-Specker (KS) set is a finite collection of vectors on the two-sphere containing no antipodal pairs for which it is impossible to assign 0s and 1s such that no two orthogonal vectors are assigned 1 and exactly one vector in every triplet of mutually orthogonal vectors is assigned 1. The existence of KS sets lies at the heart of Kochen and Specker's argument against non-contextual hidden variable theories and the Conway-Kochen free will theorem. Identifying small KS sets can simplify these arguments and may contribute to the understanding of the role played by contextuality in quantum protocols. In this paper we derive a weak lower bound of 10 vectors for the size of any KS set by studying the opposite notion of large non-KS sets and using a probability argument that is independent of the graph structure of KS sets. We also point out an interesting connection with a generalisation of the moving sofa problem around a right-angled hallway on the two-sphere.