Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. Let the nonnegative integers be partitioned into sets A1,…,AkA_1,\ldots,A_k. Then there are an ii and a set X={xn:n≥1}⊆AiX=\{x_n:n\ge1\}\subseteq A_i such that every sum xi1+⋯+xinx_{i_1}+\cdots+x_{i_n} with i1<⋯<ini_1<\cdots<i_n lies in AiA_i; this is Theorem 1 of Baumgartner (p. 384). The printed statement says neither that XX is infinite nor that the xnx_n are distinct, and read literally it is met by X={0}X=\{0\}; it is read here with the xnx_n distinct and positive, so XX infinite, which the derivation from Theorem 2 below supplies. With k=2k=2, and with 00 placed in either class, it is then the statement of Problem 532 over the positive integers, with nothing to remove from XX. Baumgartner proves the equivalent finite-unions form, Theorem 2 (in any finite partition of the finite nonempty sets of nonnegative integers, some cell contains an infinite pairwise disjoint family all of whose finite unions lie in that cell), through four lemmas on sets that are large for a disjoint collection, and derives Theorem 1 from it by sending a finite set {i1,…,in}\{i_1,\ldots,i_n\} to 2i1+⋯+2in2^{i_1}+\cdots+2^{i_n}, a map that is injective and positive on nonempty sets, so the images of the infinite disjoint family are distinct positive integers. The theorem is Hindman's, recorded on Hindman's claim page; this page records the second refereed proof.

Acceptance. Refereed: J. E. Baumgartner, A short proof of Hindman's theorem, J. Combin. Theory Ser. A 17 (1974), no. 3, 384--386, published November 1974 (Crossref record accessed). The record gives no day, so the day in the page name is a placeholder for November 1974. Erdős's surveys of 1975, 1977 and 1980 name the note as the simplification of Hindman's proof; the site labels the problem PROVED (LEAN) and credits Hindman.

Read depth. Theorems 1 and 2 and the definitions were checked; the statements of Lemmas 1--4 were read, and no proof step was checked. Nothing here is independent review.

Depends on. Nothing in this wiki; the result is the note's own theorem.