Independent finite sums in graphs defined on the natural numbers (Q1381867): Difference between revisions

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.