Independent finite sums for \(K_ m\)-free graphs (Q1356037)

From MaRDI portal
Revision as of 14:02, 27 May 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Independent finite sums for \(K_ m\)-free graphs
scientific article

    Statements

    Independent finite sums for \(K_ m\)-free graphs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    14 September 1997
    0 references
    N. Hindman proved in 1974 the following result (see J. Comb. Theory, Ser. A 17, 1-11 (1974; Zbl 0285.05012)): Let \(r\) be a natural number and \(A_1,...,A_r\) be a partition of all natural numbers \(\mathbb{N}\). Then there exist \(i \in \{1,...,r\}\) and a sequence \(\langle x_n \rangle_{n=1} ^\infty\) such that every finite sum from the sequence belongs to \(A_i\). This paper studies analogous questions. It answers a problem of A. Hajnal: Let \(G\) be a triangle-free graph on \(\mathbb{N}\). Does there always exist a sequence in \(\mathbb{N}\) such that the set of all finite sums forms an independent vertex set? The answer is negative. However the paper also contains positive results on analogous questions. For example, if for some \(m \in \mathbb{N}\) the graph \(G\) contains no complete bipartite graph \(K_{m,m}\) then the answer for the previous problem is affirmative.
    0 references
    0 references
    Hindman theorem
    0 references
    finite sums
    0 references
    independent sets in graphs
    0 references
    cancellative semigroups
    0 references
    \(\beta S\) semigroup
    0 references
    0 references