Enumerating solution-free sets in the integers

Andrew Treglown, Robert Hancock

Research output: Contribution to journalArticlepeer-review

144 Downloads (Pure)

Abstract

Given a linear equation L, a set A ⊆ [n] is L-free if A does not contain any ‘non-trivial’ solutions to L. In this paper we consider the following three general questions:
(i) What is the size of the largest L-free subset of [n]?
(ii) How many L-free subsets of [n] are there?
(iii) How many maximal L-free subsets of [n] are there?
We completely resolve (i) in the case when L is the equation px + qy = z for fixed p, q ∈ N where p ≥ 2. Further, up to a multiplicative constant, we answer (ii) for a wide class of such equations L, thereby refining a special case of a result of Green [15]. We also give various bounds on the number of maximal L-free subsets of [n] for three-variable homogeneous linear equations L. For this, we make use of container and removal lemmas of Green [15].
Original languageEnglish
Pages (from-to)21-30
JournalElectronic Notes in Discrete Mathematics
Volume56
DOIs
Publication statusPublished - 1 Dec 2016

Keywords

  • Container method
  • independent sets
  • solution-free sets

Fingerprint

Dive into the research topics of 'Enumerating solution-free sets in the integers'. Together they form a unique fingerprint.

Cite this