Independent finite sums in graphs defined on the natural numbers (Q1381867): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q190038 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Kathrin Klamroth / rank | |||
Normal rank |
Revision as of 19:41, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Independent finite sums in graphs defined on the natural numbers |
scientific article |
Statements
Independent finite sums in graphs defined on the natural numbers (English)
0 references
24 June 1998
0 references
Let \(G\) be a graph whose vertices are defined on the natural numbers and assume that \(G\) does not contain a complete graph with \(k\geq 3\) vertices. A 1995 conjecture of Paul Erdős is proven, namely that there exists a (not necessarily finite) subset \(A\) of the natural numbers such that the set of vertices corresponding to a finite sum of at most \(l\) elements in \(A\), \(l\geq 2\) form an independent set in \(G\). The developed approach is based on Ramsey type results for finite sums of Milliken and Taylor. It can also be applied to prove a variation of the above-mentioned conjecture for graphs \(G\) not containing a complete balanced bipartite graph on \(2k\) vertices.
0 references
Ramsey theory
0 references
independent finite sums
0 references