On the complexity of finding and counting solution-free sets of integers

Andrew Treglown, Kitty Meeks

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
153 Downloads (Pure)

Abstract

Given a linear equation L, a set of A integers is L-free if does not contain any ‘non-trivial’ solutions to L. This notion incorporates many central topics in combinatorial number theory such as sum-free and progression-free sets. In this paper we initiate the study of (parameterised) complexity questions involving L-free sets of integers. The main questions we consider involve deciding whether a finite set of integers A has an L-free subset of a given size, and counting all such L-free subsets. We also raise a number of open problems.
Original languageEnglish
Pages (from-to)219-238
JournalDiscrete Applied Mathematics
Volume243
Early online date26 Mar 2018
DOIs
Publication statusPublished - 10 Jul 2018

Keywords

  • (Parameterised) complexity
  • Solution-free sets

Fingerprint

Dive into the research topics of 'On the complexity of finding and counting solution-free sets of integers'. Together they form a unique fingerprint.

Cite this