Independent finite sums in graphs defined on the natural numbers (Q1381867): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(97)00064-2 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2069012352 / rank | |||
Normal rank |
Latest revision as of 09:44, 30 July 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