Erdős Problem #197 — Two-set permutations avoiding monotone progressions
Write and . Is there a partition such that each part has a bijection or , respectively, for which no three terms in increasing order of position form a monotone three-term arithmetic progression? Explicitly, for each , there must be no and with such that
Thus each part is countably infinite as a consequence of having such a bijective sequence; this is not an additional partition hypothesis. The sequence has order type , rather than being an arbitrary linear ordering of the set. Erdős Problem #197 Structural rigidity in the Erdős–Graham two-set permutation problem (2026 preprint)
Background
The question grows out of a sharp difference between finite and infinite permutations. Davis, Entringer, Graham, and Simmons showed that every permutation of of order type contains an increasing three-term arithmetic progression, so the whole set cannot be ordered to avoid even the increasing case. They also constructed a partition into three sets, each of which can be ordered to avoid both increasing and decreasing three-term progressions, and asked whether two sets suffice. Erdős and Graham later repeated the question, calling it “a very annoying question.” Structural rigidity in the Erdős–Graham two-set permutation problem (2026 preprint)
The indexing condition is essential: an order indexed by all integers, or a general linear order, is not a bijective sequence indexed by . Results about those different kinds of order therefore do not directly answer this partition question. Structural rigidity in the Erdős–Graham two-set permutation problem (2026 preprint) Density bounds for permutations avoiding monotone arithmetic progressions (2026 preprint)
References
Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28 (1980).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.