Independent Deuber sets in graphs on the natural numbers
type: Item
instance of: scholarly article
title: Independent Deuber sets in graphs on the natural numbers
zbMATH Open document ID: 1028.05114
DOI: 10.1016/S0097-3165(03)00100-6
author: Hans Jürgen Prömel
author: Vojtěch Rödl
author: David S. Gunderson
author: Imre Leader
published in: Journal of Combinatorial Theory. Series A
publication date: 2003-09-07T00:00:00Z
review text: If \(A\) is a finite matrix with entries in \(\mathbb N\) (the positive integers), a system \(A\mathbf x\mathbf=\mathbf 0\) of linear equations is partition regular over \({\mathbb N}\) if, for every partition of \(\mathbb N\) into finitely many classes, there exists a solution completely contained in one class. For \(m\in{\mathbb N}\cup\{0\}\), \(p, c,x_1,\dots,x_m\in{\mathbb N}\), \(c\leq p\), any union \[ \bigcup\limits_{j=0}^m\left\{cx_j+\sum\limits_{i=j+1}^m\lambda_ix_i: \lambda_i\in\{0,\pm 1,\pm 2,\dots,\pm p\}\right\} \] in \({\mathbb N}\) is an \((m,p,c)\)-set or Deuber set. From the authors' abstract: ``We show that, for any \(k,m,p,c\), if \(G\) is a \(K_k\)-free graph on \({\mathbb N}\), then there is an independent set of vertices in \(G\) that contains an \((m,p,c)\)-set. Hence, if \(G\) is a \(K_k\)-free graph on \({\mathbb N}\) \dots{} one can solve any partition regular system of equations in an independent set. This is a common generalization of partition regularity theorems of \textit{R. Rado} [Studien zur Kombinatorik, Math. Z. 36, 424-480 (1933; Zbl 0006.14603)]\dots and \textit{W. Deuber} [Partionen und lineare Gleichungssysteme, Math. Z. 133, 109-123 (1973; Zbl 0254.05011)]\dots and of Ramsey's theorem itself.'' They provide a new proof of Theorem 5.1 (proved by the present authors in [Independent arithmetic progressions in clique-free graphs on the natural numbers, J. Comb. Theory, Ser. A 93, 1-17 (2001; Zbl 0977.05137)]): Fix \(k\) and \(\ell\). If \(G\) is a \(K_k\)-free graph on \({\mathbb N}\), then there exists an \(\ell\)-term arithmetic progression which spans an independent set in \(G\), noting that ``since an early draft of this paper, J. Solymosi [personal communication] has independently observed a similar proof of Theorem 5.1''.
Mathematics Subject Classification ID: 05D10
Mathematics Subject Classification ID: 11B75
Mathematics Subject Classification ID: 11B25
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 1975837
zbMATH Keywords: Ramsey theory
zbMATH Keywords: independent sets
zbMATH Keywords: partition regular equations
reviewed by: William G. Brown
MaRDI profile type: Publication
cites work: Partitionen und lineare Gleichungssysteme
cites work: Independent finite sums for \(K_ m\)-free graphs
cites work: On a metric generalization of Ramsey's theorem
cites work: Quantitative theorems for regular systems of equations
cites work: Q3997075
cites work: Q5461506
cites work: Independent arithmetic progressions in clique-free graphs on the natural numbers
cites work: Regularity and Positional Games
cites work: Q3433937
cites work: Q4100665
cites work: Independent finite sums in graphs defined on the natural numbers
cites work: Q3972755
cites work: Studien zur Kombinatorik
cites work: On sets of integers containing k elements in arithmetic progression
full work available at URL: s0097-3165(03)00100-6
OpenAlex ID: W2027965373
Recommended article: Q5461506
Recommended article: Independent arithmetic progressions in clique-free graphs on the natural numbers
Recommended article: Q3977405
Recommended article: Some remarks on the theory of graphs
Recommended article: Image partition regularity near zero
Recommended article: Graphs on affine and linear spaces and Deuber sets
Recommended article: Q4359495
Recommended article: Two remarks on Ramsey's theorem
Recommended article: Open Problems in Partition Regularity
Recommended article: Rado Partition Theorem for Random Subsets of Integers
description: scientific article; zbMATH DE number 1975837