Independent finite sums in graphs defined on the natural numbers (Q1381867): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Independent finite sums for \(K_ m\)-free graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4189416 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Idempotents in compact semigroups and Ramsey theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ramsey's theorem with sums or unions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A canonical partition relation for finite subsets of \(\omega\) / rank | |||
Normal rank |
Revision as of 11:55, 28 May 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