SUPERSET: A (super)natural variant of the card game SET

Abstract: We consider SUPERSET, a lesser-known but interesting variant of the famous card game SET. Here, players look for SUPERSETs instead of SETs, that is, the symmetric difference of two SETs that intersect in exactly one card. In this paper, we pose questions that have been previously posed for SET and provide answers to them; we also show relations between SET and SUPERSET.

For the regular deck of cards, which can be identified with F_3^4, we give an elegant proof for the fact that the maximum number of cards that can be on the table without having a SUPERSET is 9, solving an open question (McMahon et al., 2016). For the deck corresponding to F_3^d, we show that this number is Omega(1.442^d) and O(1.733^d). We also compute probabilities of the presence of a superset in a collection of cards drawn uniformly at random. Finally, we consider the computational complexity of deciding wether a multi-value version of SET or SUPERSET is contained in a given set of cards, and show an FPT-reduction from the problem for SET to that for SUPERSET, implying W[1]-hardness of the problem for SUPERSET.

Posted on May 14, 2018 in ACGO, Seminars