Independent Deuber sets in graphs on the natural numbers
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.
- scientific article; zbMATH DE number 2188406
- Independent arithmetic progressions in clique-free graphs on the natural numbers
- scientific article; zbMATH DE number 15063
- Some remarks on the theory of graphs
- Image partition regularity near zero
- Graphs on affine and linear spaces and Deuber sets
- scientific article; zbMATH DE number 1075579
- Two remarks on Ramsey's theorem
- Open Problems in Partition Regularity
- Rado Partition Theorem for Random Subsets of Integers
- scientific article; zbMATH DE number 5145371 (Why is no real title available?)
- scientific article; zbMATH DE number 16107 (Why is no real title available?)
- scientific article; zbMATH DE number 46958 (Why is no real title available?)
- scientific article; zbMATH DE number 3522189 (Why is no real title available?)
- scientific article; zbMATH DE number 2188406 (Why is no real title available?)
- Independent arithmetic progressions in clique-free graphs on the natural numbers
- Independent finite sums for \(K_ m\)-free graphs
- Independent finite sums in graphs defined on the natural numbers
- On a metric generalization of Ramsey's theorem
- On sets of integers containing k elements in arithmetic progression
- Partitionen und lineare Gleichungssysteme
- Quantitative theorems for regular systems of equations
- Regularity and Positional Games
- Studien zur Kombinatorik
- Independent finite sums for \(K_ m\)-free graphs
- An infinitary extension of the Graham–Rothschild Parameter Sets Theorem
- Graphs on affine and linear spaces and Deuber sets
- scientific article; zbMATH DE number 2188406 (Why is no real title available?)
- Independent sums of arithmetic progressions in K_m-free graphs.
- Independent arithmetic progressions in clique-free graphs on the natural numbers
This page was built for publication: Independent Deuber sets in graphs on the natural numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1406743)
