Independent Deuber sets in graphs on the natural numbers (Q1406743)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Independent Deuber sets in graphs on the natural numbers |
scientific article |
Statements
Independent Deuber sets in graphs on the natural numbers (English)
0 references
7 September 2003
0 references
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''.
0 references
Ramsey theory
0 references
independent sets
0 references
partition regular equations
0 references