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

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • University of Glasgow

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.

Details

Original languageEnglish
Pages (from-to)219-238
JournalDiscrete Applied Mathematics
Volume243
Early online date26 Mar 2018
Publication statusPublished - 10 Jul 2018

Keywords

  • (Parameterised) complexity, Solution-free sets