ICS Lunch and Seminar Series: Bas Westerbaan on 10/13

Bas Westerbaan

Where and When: POST318B (ICSpace) Thursday October 13, 12:00pm

Title: In search for the smallest Kochen-Specker system


At the heart of the famous Conway-Kochen Free Will Theorem and Kochen and Specker’s argument against non-contextual hidden variable theories is the existence of a Kochen-Specker (KS) system: a finite set of points on the sphere that is not “010-colorable”.  The first KS-system was found in 1975 consisting of 117 points.  In 1991 Penrose and Peres independently found a system of 33 points.  Around 1995 John Conway took the lead with his 31 point system.  To this day, Conway’s system is the smallest known Kochen-Specker system.  In public lectures Conway encouraged the search for a smaller system.

In 2009 Arends, Ouaknine and Wampler from Oxford have shown that a Kochen-Specker system must have at least 18 points.  They did this by reducing the problem to the existence of graphs with a topological embeddability and non-colorability property.  The bottleneck in their search proved to be enumerating the sheer number of graphs on more than 17 vertices and deciding embeddability.

Continuing their effort, we reduced the class of graphs to consider and found a more practical algorithm to decide embeddabiltiy.  This allowed us to show that a Kochen-Specker system must have at least 22 points.

There is a lot of room for improvement; e.g. if the enumeration of graphs can be effectively restricted to those graphs in which every point is part of a triangle, the upper bound may be pushed to 24 and the smallest KS-system might be found. So, if you have a knack for algorithms, please join and give this problem a shot!


Sander Uijlen and Bas Westerbaan. “A Kochen-Specker system has at least 22 vectors.” New Generation Computing 34.1-2 (2016): 3-23.


Bas Westerbaan is Ph.D-student at Radboud Universiteit Nijmegen (the Netherlands).