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

2017/04/12 by Kitty Meeks, Meeks, Kitty, Andrew Treglown +1 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #math.CO

paper · pdf · doi:10.48550/arxiv.1704.03758

27 pages

arxiv created 2017/04/12 · arxiv updated 2017/04/13

Abstract

Given a linear equation L, a set A of integers is L-free if A 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.

Cited by

• The complexity of solution-free sets of integers

Related

• The complexity of solution-free sets of integers
• On solution-free sets of integers
• On solution-free sets of integers II
• Counting subsets of integers free of arithmetic configurations
• The Cameron-Erdos Conjecture