Structural rigidity in the Erdős-Graham two-set permutation problem
Abstract
Call a permutation of a set of positive integers admissible if it contains no increasing or decreasing three-term arithmetic progression in position order. Davis, Entringer, Graham, and Simmons proved that the positive integers are not admissibly permutable, partitioned them into three admissibly permutable sets, and asked whether two sets suffice. We study the canonical dyadic candidate S_A, the union of the blocks (2^{k-1}, 2^k] over even k >= 2. We establish several structural restrictions on admissible permutations, including an orbit obstruction, an asymmetric balance law, and the impossibility of placing all sufficiently large dyadic blocks as contiguous runs. For the main result, we reduce admissibility of S_A to feasibility of an order gadget on (M, 2M]: the order must avoid monotone three-term progressions and satisfy fifteen precedence constraints induced by the values 15 and 16. We then prove that a three-constraint core of this gadget is inconsistent for every M congruent to 0 mod 8, using zigzag propagation on arithmetic-progression ladders, a transfer lock, and mirror-flood induction. Since every relevant dyadic scale lies in this residue class, S_A admits no admissible permutation. Thus the canonical dyadic partition does not solve the two-set problem, which remains open. Independent SAT encodings and certificate checks provide auxiliary verification of the human-readable proof.
Related
- The Burr-Erdős-Graham-Sós conjecture for the seven-cycle
- Square products of factorials and a conjecture of Erdős and Graham
- An Erdős-Szekeres-Type Result on Permutation Patterns
- Anti-concentration and Graham's rearrangement problem in finite abelian groups
- Linear dependencies, polynomial factors in the Duke–Erdős forbidden sunflower problem – CORRIGENDUM
BibTeX
@misc{kasel2026structural,
title = {{Structural rigidity in the Erdős-Graham two-set permutation problem}},
author = {William Kasel},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.02939},
eprint = {2609.02939},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.02939},
}
RIS
TY - UNPB
TI - Structural rigidity in the Erdős-Graham two-set permutation problem
AU - William Kasel
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.02939
UR - https://arxiv.org/abs/2609.02939
AB - Call a permutation of a set of positive integers admissible if it contains no increasing or decreasing three-term arithmetic progression in position order. Davis, Entringer, Graham, and Simmons proved that the positive integers are not admissibly permutable, partitioned them into three admissibly permutable sets, and asked whether two sets suffice. We study the canonical dyadic candidate S_A, the union of the blocks (2^{k-1}, 2^k] over even k >= 2. We establish several structural restrictions on admissible permutations, including an orbit obstruction, an asymmetric balance law, and the impossibility of placing all sufficiently large dyadic blocks as contiguous runs. For the main result, we reduce admissibility of S_A to feasibility of an order gadget on (M, 2M]: the order must avoid monotone three-term progressions and satisfy fifteen precedence constraints induced by the values 15 and 16. We then prove that a three-constraint core of this gadget is inconsistent for every M congruent to 0 mod 8, using zigzag propagation on arithmetic-progression ladders, a transfer lock, and mirror-flood induction. Since every relevant dyadic scale lies in this residue class, S_A admits no admissible permutation. Thus the canonical dyadic partition does not solve the two-set problem, which remains open. Independent SAT encodings and certificate checks provide auxiliary verification of the human-readable proof.
ER -