1 Search Results for "Botler, F�bio"


Document
SUPERSET: A (Super)Natural Variant of the Card Game SET

Authors: Fábio Botler, Andrés Cristi, Ruben Hoeksma, Kevin Schewior, and Andreas Tönnis

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)


Abstract
We consider Superset, a lesser-known yet 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 Set deck, which can be identified with F^3_4, we give a proof for the fact that the maximum number of cards that can be on the table without having a Superset is 9. This solves an open question posed by McMahon et al. in 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 whether 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.

Cite as

Fábio Botler, Andrés Cristi, Ruben Hoeksma, Kevin Schewior, and Andreas Tönnis. SUPERSET: A (Super)Natural Variant of the Card Game SET. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{botler_et_al:LIPIcs.FUN.2018.12,
  author =	{Botler, F\'{a}bio and Cristi, Andr\'{e}s and Hoeksma, Ruben and Schewior, Kevin and T\"{o}nnis, Andreas},
  title =	{{SUPERSET: A (Super)Natural Variant of the Card Game SET}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.12},
  URN =		{urn:nbn:de:0030-drops-88035},
  doi =		{10.4230/LIPIcs.FUN.2018.12},
  annote =	{Keywords: SET, SUPERSET, card game, cap set, affine geometry, computational complexity}
}
  • Refine by Author
  • 1 Botler, Fábio
  • 1 Cristi, Andrés
  • 1 Hoeksma, Ruben
  • 1 Schewior, Kevin
  • 1 Tönnis, Andreas

  • Refine by Classification
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Theory of computation → Fixed parameter tractability
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 SET
  • 1 SUPERSET
  • 1 affine geometry
  • 1 cap set
  • 1 card game
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail