Back to Search
Start Over
On the complexity of finding and counting solution-free sets of integers.
- Source :
-
Discrete Applied Mathematics . Jul2018, Vol. 243, p219-238. 20p. - Publication Year :
- 2018
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *INTEGERS
*LINEAR equations
*COMBINATORIAL number theory
*SET theory
*MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 243
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 129713662
- Full Text :
- https://doi.org/10.1016/j.dam.2018.02.008