Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
This page is Plasma AI's editable proof sketch for the first unresolved instance of Problem 592,
It is the case in the problem page's notation and in Schipperus's journal paper. A result here would not settle the other sums of three indecomposable ordinals. The page follows the successor-tree interface, which proposes the route through a three-game construction: from a winning Architect strategy, build three trees whose three pairs are outputs of correct plays. For the explicit successor game used here, the finite-height source interface reconstructs the dichotomy, its finite-cover refinement, and the normalized Builder implication. The local arguments are author-recorded, tier 0, and unreviewed.
The main conclusion is a reduction. Theorem 5 and Propositions 6 and 7 build the three plays, one node at a time and for strategies that read numerical history, in three classes of winning strategies: all outputs outside, and all outputs inside with the first tree's top split at its first or at its last pair of selected leaves. By Corollary 2 the only remaining case is that of middle strategies, treated in its own section with a structural lemma and a fixed-shape template. These arguments hold at every finite height.
An earlier bounded conclusion is a precise obstruction to one proposed mechanism: requiring every selected leaf of the first tree to be selected in both of its games. A fixed, game-local winning strategy defeats that requirement, independently of all numerical choices. The same strategy admits the different explicit schedule below. Thus the obstruction concerns the synchronization requirement, not the three-game conclusion or the partition relation.
A three-element stack records which tree may move next. It is useful for both the obstruction and the construction, but it does not erase numerical histories from an adaptive strategy. The finite probes cover prescribed selection shapes and a separately defined adversary with access to all three games. Neither probe settles the general height-three problem.
Conventions
is the set of trees of Definitions 6--8 with root label . Every internal node is a successor node, and each branch has labels . Children are indexed from as in Definition 9(4): a node with children has children. For a partition , , where is the set of indices of the children in . The game prose after Definition 17 and in Definition 18(1) instead counts children; the print has this discrepancy on pp. 1200 and 1203. This page uses the zero-based successor game of the interface: a maximum gives children , with child unselected. A one-based version instead uses children . The constructions below work in either consistent convention: adding one to every numerical label and child index takes the zero-based game to the one-based game, with identical full child lists and conjugated strategies. The printed mixed convention is not silently asserted to be a literal game definition. This translation identifies two coherent game definitions; it does not by itself prove the source theorems for either repair. The separate reconstruction supplies the needed dichotomy and normalized Builder implication for this convention at finite height, at author standing.
Write , , for the three trees in the order of their first leaves. In each pair the tree with the earlier first leaf moves first in that pair's game. Its root's numbers come first, so it has fewer root children and is the smaller tree. In tree , a leaf is marked for if it is a selected leaf of : a cell end of against . A leaf marked for both other trees is a double; a leaf marked for one is a single naming that tree. Reading a tree's leaves in order gives its mark word.
The games are those of Definitions 15--19 on printed pp. 1203--1204, read at statement depth. The positive labels are the partial sums of , so by Definition 19(1) the Architect moves at every internal node. Only these compulsory finite-height prescriptions are used here; no limit-ladder instruction is transplanted to a successor node. Write for the prescribed number of selected children. This is the source's , not the cardinality of . A root may have , in which case its selection shape is empty. A nonroot node is selected when its index was selected at its parent.
Prescriptions at finite height
Lemma 1. Let be a winning Architect strategy on an infinite . In every legal play against whose Builder moves are sufficiently large in :
- at an internal node outside the selected set, prescribes one element, so no child is selected;
- at a selected nonroot internal node, prescribes at least two elements, so at least one child is selected;
- the play is correct. Given (1) and (2), this holds exactly when the second tree has as many selected leaves as the first tree (outside) or one fewer (inside). A root with no selected child is allowed and has no selected leaf below it.
Proof. The Builder can always continue a legal play with sufficiently large moves, and wins every such continuation. A larger set at an unselected node makes in every continuation. A singleton at a selected nonroot node leaves no selected leaf below it, so its parent's label records a child outside . There is no such parent obstruction at a root. For (3), the play builds a run of the first tree up to its next selected leaf, then a run of the second, and so on. Each selected leaf is a cell maximum exactly when the other tree still has a leaf to build after it. With and selected leaves, the and runs alternate from the first tree exactly when . By (1) and (2), the selected nodes are then the upward closure of the cell maxima, so every label equals .
By the reconstructed finite-cover refinement, one may assume that every output of is inside, or that every output is outside. The searches below treat both types.
The stack criterion
In a pair's game, the tree being built holds the turn. Take three trees with selected sets for both of each tree's games. Run the following process on the unfinished trees. A tree may build its next node only when it holds the turn in both of its games. The turn in a game passes at that game's marked leaves and when a tree finishes, exactly as in Definition 18. Record who holds each game's turn as a tournament on the unfinished trees. The process deadlocks when the tournament is a 3-cycle: then no tree may move.
When the tournament is transitive, it is a linear order: the stack. The top tree builds until it reaches a marked leaf or its last leaf. With stack :
- a single naming swaps the top two, giving ;
- a double sends to the bottom, giving ;
- a single naming deadlocks, since then holds the turn over , over , and over ;
- the last leaf removes .
The process starts with stack .
Lemma 2 (local realization and the cycle obstruction). At a transitive prefix, both games containing the top tree are ready for that tree's next node. Their actual numerical histories and prescriptions are therefore available. Any ordered merge of their two prescribed child lists can be realized with a shared maximum and sufficiently large choices in . Three complete legal plays sharing their trees cannot produce a cyclic turn state.
Proof. Suppose the requested selected-child counts are and . An ordered merge is a word in , with occurrences of or and occurrences of or . Choose one fresh element of for each letter, in increasing order, and then one larger element . All these elements exceed every number already chosen and both games' current thresholds. The first label contains the positions and ; the second contains the positions and . Thus their sizes are and their maxima coincide. At a leaf choose a single common element above the same bounds. No past choice is enlarged or relabeled.
For the obstruction, give a node its leaf label or, at an internal node, the common maximum as its key. Within a game every key strictly increases in play order. At a cyclic state, the next nodes of the three trees would have keys . This is impossible.
All children at positions must actually be built. Children absent from both selected lists have unselected subtrees, filled in tree order using singleton labels and the same fresh-number rule. A child selected in only one game still has the same full subtree in both games. The other game's labels there are singletons. Since the height is finite and every chosen maximum is finite, this recursion builds a finite tree. The number of unselected nodes can be arbitrarily large; none is discarded from either numerical history.
Fixed-shape realization. For fixed selection shapes, erase only the children selected in neither game. The remaining ordered union at each node is an ordered merge as above. Conversely, every such finite merged tree can be padded by the preceding rule. If its stack run completes with the correct pairwise cell endpoints, this gives three shared full trees for every infinite and every finite, history-dependent threshold rule. The last child of each internal node is unselected, so every tree has a nonempty final cell after all its selected leaves. Inserted unmarked leaves do not change which event ends a nonfinal cell. The induced partitions therefore recover exactly the prescribed selected trees and labels. Increasing labels give Definitions 11 and 13, including disjoint Full sets within each pair and the placement of the second root after the first cell. This proves the fixed-shape compression and expansion used by the finite probes; it is not a finite basis for unrestricted strategies.
For an adaptive , the analogous construction must read both prescriptions afresh at each actual position, including positions reached after building unselected subtrees. If a rule for the arrangements and actual numbers avoids a cycle throughout, it completes three legal plays; winningness then gives correctness and color . Lemma 2 guarantees local availability of the requests, not a rule that avoids every future cycle. Changing the numbers or the number of unselected children may change all later prescriptions. A schedule computed for static shapes does not control that dependence.
Lemma 3 (endgame). Once one tree has finished, the process cannot deadlock. The first tree to finish is in the outside type and in the inside type.
Proof. Suppose a remaining tree marks a leaf for the finished tree. Then that game's play has a selected leaf that is not a cell maximum. That play is legal, which contradicts Lemma 1(3). So the remaining two trees mark only each other, and swaps never deadlock. In each pair, the first tree's last run is last in the inside type and the second tree's is last in the outside type.
So only the stretch before the first finish can fail. Every mark involving the first finisher must be emitted in that stretch.
Outside strategies: the spine construction
For outside strategies the forward-dependence problem disappears. The argument below works at every finite height in the coherent successor game, so it uses nothing special about .
For a tree, call the smaller of its two partners its left partner and the larger its right partner. Thus has left partner and right partner ; has and ; has and .
Theorem 5 (outside strategies). Let be a winning Architect strategy on an infinite for the coherent successor game at a finite height , and suppose every output of is outside. For every finite threshold rule there are three complete correct plays against , one for each pair, that share their trees and use only sufficiently large moves. Each prescription is used at the position where makes it; no later prescription is needed in advance.
Construction. Each tree is built along a spine: a path from its root to a leaf whose nodes are all selected in both of the tree's games. When a spine node is built, both games prescribe their counts (left game) and (right game). The Builder lists the selected children of as follows: children selected only in the left game; the next spine node, which is the last child selected in the left game and the first selected in the right game; then children selected only in the right game; then padding ending in an unselected last child. The spine ends at a leaf, which is a double. Every other selected child roots a subtree selected in one game only. It is built with that game's prescriptions, padded as in Lemma 2, and all of its marks are singles naming that game's partner.
If the common first move of is , every first tree has no marks; then no tree has marks and the three trees are simply built in order. Otherwise every spine count is at least : at a nonroot node by Lemma 1(2), and at a root because an outside output has as many marks in its second tree as in its first. So every mark word has the form
where the double is the last mark for the left partner and the first mark for the right partner. The selection trees themselves are not restricted: the spine identifies the rightmost path of the left game's selection tree with the leftmost path of the right game's.
Schedule and proof. Write for the three doubles. The stack process runs in five stages.
- From , and alternate in their game until builds . Before that, both emit left singles, which name each other.
- The stack is , and builds to , giving .
- and alternate in their game until builds . Here emits left singles naming , and emits right singles naming .
- The stack is , and has no mark left: it finishes.
- and alternate with right singles until finishes, and then finishes.
Every claim about the next mark follows from the alternation of an outside play, which guarantees in every legal continuation. In the game of and , the marks alternate . The double is , since has no later mark for . Exactly one mark of for remains after it, and is the last such mark, so it is the next mark of ; no mark of for precedes . In the game of and , is the first mark of , so the alternation continues with 's left singles and 's right singles. It ends with 's last mark for , which is . At that point has emitted all its marks, and the remaining marks of and name each other. In the game of and , and are the first marks of the two trees, and stage 5 is the rest of that alternation.
In each pair the global construction order restricted to the two trees is that pair's play order: a tree builds only while it holds the turn in both of its games, and the third tree's moves belong to neither game of the pair. The finishing order is the outside order of Lemma 3, and every last cell follows the partner's last mark. Choosing every new element of above all earlier numbers and all three games' current thresholds makes every move sufficiently large. The padding argument of Lemma 2 makes each pair good and recovers the prescribed labels. Hence the three plays are complete, legal and correct, and all three outputs have color .
Consequence. Use the source interface S proved on the companion page and the equal-block normalization. In the Architect case, the finite-cover refinement gives an infinite subset on which the Architect wins with all outputs inside or with all outputs outside. In the outside case Theorem 5 gives a color- triangle. Thus the positive relation is reduced to the inside case of G. The reduction is the same at every finite height. In particular, at any finite height, a coloring without a color- triangle has no infinite set on which the Architect wins with all outputs outside. Such colorings exist at height by Schipperus's Theorem 33, and all three printed negative patterns are indeed of inside type: their first trees have one more cell than their second trees.
For inside strategies the same spine construction deadlocks. With the same words, emits before emits , since is now the last mark of for . After the stack is . If starts with singles naming it deadlocks at once. If is built with left partner instead, the game of and ends with 's double while still owes its last single naming , and the stack then deadlocks. The inside case therefore needs a different idea.
Inside strategies: two classes with online templates
Two further classes of inside strategies have online constructions. In a selection tree with at least two leaves, the top split is the highest node with at least two selected children. Call an inside output top-first if the first two selected leaves of its first tree have their lowest common ancestor at that tree's top split, and top-last if its last two selected leaves do. Otherwise call it middle. A first tree with one selected leaf counts as top-first. Under the level reading recorded on the pattern-level page, top-first means and top-last means , where is the word of levels of consecutive selected leaves.
Before its first mark, a first tree can keep its two games' histories identical by giving each node the same label in both games. Then prescribes the same counts in both, and the two games reach their top split at the same node.
Proposition 6 (top-first). If every output of is inside and top-first, the conclusion of Theorem 5 holds.
Proof. Build with identical labels in its two games down to the common top split . Below in the first child both games have count , since the first selected leaf is alone in that child of a top-first output. At , list the first child, then the children selected only for , then those selected only for . Thus the mark word of is . Build and along mirror spines: at each spine node, the children selected only for the right partner come first, then the spine child, then the children selected only for the left partner. Their words are and , and the double is the last mark for the right partner and the first for the left one. The stack process runs as follows. emits , giving . Then and alternate until emits and emits , giving . Next and alternate until emits its last single naming , and finishes. Finally and alternate, finishes, and then finishes. Each step is forced by the inside alternation of the relevant game, exactly as in the proof of Theorem 5. If has a single mark for , inside alternation forces a single mark for as well, and the run reduces to emitting while and play out their game.
Proposition 7 (top-last). If every output of is inside and top-last, the conclusion of Theorem 5 holds.
Proof. Build with identical labels down to the common top split . At , list the children selected only for , then a child selected in both games, then the children selected only for , then a child selected in both games. Here is the second-to-last child selected for and the first selected for , and is the last for both. Below , build the subtree of along an outside spine with left partner . In the subtree of the game with has count everywhere, because the last selected leaf of a top-last first tree is alone in the last child of its top split. Build 's subtree along the rightmost path of the game with , with the children selected only for on its left. The mark word of is , where is the first mark for and the last mark for both partners. Build and along outside spines, with words and . The run is as follows. and alternate until emits , and then emits , giving . Next and alternate until emits , giving . Then emits , giving . Finally and alternate until emits its last single, and , and finish in that order. Every step is forced by the inside alternations. If the game of and has a single mark of , then has no mark for , and is a single naming .
Reduction. The finite-cover refinement applies to the finite cover of all pairs by the outside pairs, the inside top-first pairs, the inside top-last pairs, the inside middle pairs, and the remaining pairs, which are not good or have equal block types. In the Architect case some class carries a winning strategy, and only the last two classes are not covered. Correct plays output good pairs, and pairs of equal block type have color after normalization, so the remaining class carries no winning strategy. Theorem 5 and Propositions 6 and 7 therefore reduce G at height to middle strategies: winning strategies all of whose outputs are inside and middle. The reduction holds at every finite height.
At height a middle first tree has top split level or , and the first and last children of its top split each contain at least two selected leaves. Under the level reading, the printed patterns behave consistently with this reduction. The two-summand pattern of Theorem 31 is top-first; it has triangles, as Proposition 6 predicts, and excludes only six-cliques. The three-summand pattern of Theorem 32 and the triangle-free four-summand pattern of Theorem 33 are middle patterns.
The middle class
Middle strategies remain open. This section records what holds for them in the word formulation of the fixed-shape realization: each tree's mark word over three letters, with a separator level between consecutive letters, such that the two projections recover the two selection shapes. A projection keeps the letters for one partner, and the level between two kept letters is the largest separator level between them. Given the words, levels exist exactly when every stretch of each projection contains a separator whose two covering stretch levels are both at least its own level. Separators outside the other projection's span count as covered.
Lemma 8 (the second tree is not a spine). Fix an inside pair of shapes with middle. Thus the three trees carry , and respectively. No completing schedule gives a word of the form or .
Proof. Following the stack process from with such a word for forces the word of to be one of , , and . Write for the top split level of . In the first two forms, the span of 's projection for lies between the first two marks for ; in the last two it lies between the last two marks for . The projection for has shape , so its span needs a separator of level . The two bounding marks for have common ancestor below level , since is middle. Their stretch cannot contain such a separator. Thus no separator levels exist.
These two spine words cannot handle a fixed middle pair. The following template uses a different second-tree word, with singles of one kind on both sides of its double.
Proposition 9 (two children at the top split). Let the fixed shapes be an inside pair with middle, whose top split has exactly two children and . Let and let be the level word of . If or is at least the top level of , the pair has a triangle schedule.
Proof. Let , so . Take for the word
Here is the last leaf of for and the first leaf for , and is the first leaf of for and the last for . Merge along an outside spine and along a mirror spine. The run of singles naming then lies in the stretch from to for , which crosses the top split and has the top level, and the other runs lie outside the span of the other projection. So has separator levels for all shapes. There are two forms for and .
- If is at least the top level, take and the outside spine . The run: and alternate with singles each; emits and emits ; and alternate until emits ; emits ; and alternate until finishes; and alternate; and then finish.
- If is at least the top level, take and the mirror spine . The run: and alternate with singles each; emits ; and alternate until emits and emits ; and alternate until emits ; finishes; and alternate; and then finish.
In both forms the double of is the -th leaf of . Its run of singles naming contains every level of and lies in the stretch of after or before that leaf, of level or ; this is where the condition is used. The word of is a spine. Both runs were checked against the three inside alternations.
Theorem 32's pattern under the selection-shape reading is the case , , , , with the triangle recorded on the pattern-level page.
Proposition 10 (flat second shape). Let be middle, with exactly two children and at its top split, each a single block of leaves, and let have all its leaves in one block. Then the pair has a triangle schedule.
Proof. Take the words
where the bar marks the separator of the top level and every other separator has level . The two projections of split as at the bar. The marks of for split as at the bar, and its marks for all follow it. Both projections of lie in one block. The run: emits ; and alternate, with singles, until emits and emits ; and alternate until 's double hands the turn to ; and alternate until 's double hands it back. In the second block each double of or switches to the other partner, finishes after 's last single naming , and and then finish. The case , was replayed in full against the three inside alternations, and the general case follows the same counts.
The case is the hand-checked schedule
At height three the proposition covers the shapes with top level and those with top level whose two top children are single blocks.
Proposition 11 (first child a block). Let be an inside pair with middle, and suppose the first child of the top split of has all its selected leaves in one block. If for every , the pair has a triangle schedule:
Proof. At the top split of list , then the children selected only for , then those selected only for ; inside the block list , then the other leaves selected for , then those selected for . The run of singles naming after stays inside , where every level is , and the run naming crosses the top split inside the stretch of 's projection from the last leaf of , which has the top level. In the run of singles naming before lies in the last stretch of the projection for , which needs ; everything else lies outside the other projection's span. is a mirror spine. The run: emits ; and alternate, with singles, until emits ; emits its first single naming ; and alternate through the leaves of until emits ; and alternate until 's last single naming , and finishes; and alternate, and and then finish.
Its mirror image also holds. If the last child of the top split has all its selected leaves in one block and for every , the words
complete. Here alternates with until 's double switches it to , alternates with until 's double switches it back, and ends with its double; and then alternate until finishes.
Proposition 12 (two block children, peak at the boundary). Let be an inside pair with middle, with exactly two children at its top split, single blocks of leaves, and let be the top level of . If and for every , the words
complete. In , is the first leaf of both projections, and is the last leaf of the second block for and its first leaf for , so the second block is merged along a mirror spine. In the run of singles naming before lies in the stretch of top level of the projection for , and the singles naming after lie inside its second block. In the run of singles naming fills the stretch of the projection for at position , which is where is used. The run: emits ; and alternate, with singles, until emits ; and alternate until emits ; and alternate until emits ; emits ; and alternate until finishes; and alternate, and and then finish. For and , which Propositions 9 to 11 miss, the words are
replayed in full with separator levels , and .
For two top children that are single blocks, Propositions 9 to 12 and the mirror image of 11 leave open the second shapes that have a non-sibling pair among their first and among their last leaves, whose level at position is not their maximum, and, when , whose levels and are below the top level of . The pair with has five leaves in and is not covered by these templates. The retained census includes it, but its existence assertion is not an online construction. The other five-leaf pair , has the explicit schedule below.
For that latter pair, take
Their separator words are respectively , and . Projection gives in , in and in . The full marked-event order is
Every single names the second tree of the stack. Doubles rotate it; the finishing order is . This is a direct fixed-shape construction and uses no numerical search. Its prescriptions are fixed in advance, so it supplies no missing adaptive uniformity.
Proposition 11 is online in a class that Corollary 2 can select: all outputs inside and middle, with the first top child of the first tree a single block, its last two selected leaves siblings, and the first selected leaves of the second tree siblings. The block of is built before the second tree starts, so its count is known when builds the block that holds its first marks for . In that block is reached along a mirror spine, and is placed at the -th mark there.
Propositions 9 and 10 are not shown to be online. In each, a double of answers a double of , and its position among the marks of for depends on counts that are prescribed after the node of fixing that position is built: at the root of in Proposition 9, the double's place among the root's children depends on and on the counts of below the root, and at the block of in Proposition 10 it depends on the size of the block of . Theorem 5, Propositions 6 and 7 and Proposition 11 in its class avoid this: each double is the first or last mark of a game, or sits at a position fixed by counts that are already prescribed when the deciding node is built.
A structural observation organizes the open fixed-shape cases. If every level of is below the top level of , then each top-level stretch of the projection of for must contain a separator outside the span of 's marks for . So all marks of for lie in the region of a single child of the top split of : the leaves of the earlier children are singles naming before them, and those of the later children are singles naming after them. Inside that region the merge is a problem of height , between that child and , with boundary conditions set by the run. A proof of the fixed-shape middle case at height three could therefore go through a lemma on such height-two sub-schedules. At height four the corresponding sub-problem has height three and may contain middle shapes, which is consistent with the failure that Theorem 33 records.
Height two is a testbed for these cases. There the relation is known, by Darby's theorem and Schipperus's Theorem 28, but the reduction above leaves the same middle class, and the templates here do not cover it: the analogue of the open pairs is with two blocks of three leaves and with blocks of sizes . A construction of middle schedules at height two, fixed-shape and then online, would test whether the game method reaches the known case before it is pushed to height three.
The fixed-shape question decides the reach of the pattern method. If every inside middle pair at height three has a triangle schedule, then every coloring for which some fixed-shape strategy wins has a color- triangle, and a negative answer would need a coloring for which no fixed-shape strategy wins. If some middle pair has no schedule, its pattern coloring under the selection-shape reading is triangle-free, and a negative answer would follow from its unavoidability in every subset of full order type.
A game-local obstruction to synchronizing the first tree
Consider the proposed mechanism that keeps : every marked leaf of is a double. It allows arbitrary arrangements in and , arbitrary full child counts, and arbitrarily large numerical choices. It still fails for the following fixed strategy at height three.
Write for a selected internal node and for a selected leaf. Specify the two selection shapes
The first tree in each game has shape , and the second has shape . Thus the prescribed selected-child counts are
| role | root | selected depth-one node | selected depth-two nodes |
|---|---|---|---|
| first | |||
| second | each |
Every unselected internal node has count . The sizes given to the Builder are these counts plus one. This defines a single strategy on actual numerical histories: it reads the tree's role and its position in the selected tree, and ignores numerical labels and unselected nodes. It does not inspect either of the other games.
Every legal completion is correct and inside: there are three selected leaves in its first tree and two in its second, with a nonempty final cell in each. To witness the word winning, define an auxiliary coloring on all pairs in : it is precisely on pairs that are outputs of a legal complete play against , and otherwise. Equivalently, compute a pair's induced partitions and their labels and check whether they form such a play. Then wins every legal play, on every infinite , without a lower-threshold restriction. Every output has unequal root lengths, so this coloring is normalized. It has the triangle constructed below and is not proposed as a negative partition coloring.
Obstruction. No three correct complete plays against can share their output trees while every selected leaf of is common to its two games.
Proof. Suppose such plays exist. Let be the common selected leaves of , let be the selected leaves of relative to , and let be those of relative to . Correct inside alternation gives
Let be the selected leaves of relative to . We claim
If , the later leaf is after the second cell in the pair , so . The first leaf is after in , hence , a contradiction. If , then is in 's final cell relative to . Since is inside, all leaves precede that cell. But gives , and puts a nonempty final cell after . Thus , again a contradiction. This proves (2).
By shape , all three lie below one depth-two node of . By shape , and lie below different depth-two nodes of . Equal-depth subtrees have disjoint convex leaf sets. At least one therefore lies outside the entire subtree containing the , hence outside . This contradicts (2).
This is a symbolic obstruction for all numerical positions and all full trees, not a bounded search failure. Deleting the common initial unary level gives the same obstruction at height two, consistent with the fact that the published positive relation requires a more flexible schedule. The proof also applies for every when has leaves below one depth-two node and has leaves below distinct depth-two nodes. Replace (2) by ; its endpoint proof is unchanged, and at least one lies outside the subtree.
An explicit alternative for the same strategy
The obstruction is sharp with respect to the proposed synchronization: the following schedule works against . The mark words are
Here marks the leaf for both other trees. Specify the selected union trees as follows. All three roots have exactly one child in the union of their selected sets, and it is common to both games. In this depth-one node has one common selected child, whose selected leaf union is . In the depth-one node has two selected children: the first is selected only for and has one -marked leaf; the second is common and has leaf union . In the depth-one node has two common selected children, each with one double leaf. Projection onto either game's selections gives exactly in , in , and in . These are selected child lists; each full child list also includes all the padding required by its numerical maximum.
The complete event order, with the resulting stack, is
| event | stack afterward |
|---|---|
| start | |
| finishes | |
| finishes | |
| finishes | empty |
Apply Lemma 2's padding procedure to these selected unions in this event order. At each node take the maximum of both current thresholds and all earlier numbers, then choose the required fresh elements of . This constructs the same full child list in the two games of each tree and a common label on each leaf. Both requests are available before either label is committed. Their sizes remain those in the table because ignores the numbers. All unselected subtrees are built, with their moves present in both relevant histories. The three pair projections of the table have alternating cells with respectively three and two nonfinal endpoints, so the marked paths end at the actual cell maxima. Each game is correct, follows and meets its threshold at every move. Thus (3) works for every infinite and every finite threshold rule, although synchronizing does not.
The evidence retains these three selected union trees and the event table, checks both projections of each tree, and independently reconstructs the three leaf alternations. The proof above, rather than numerical sampling, establishes the obstruction and the arbitrarily large realization.
Keeping synchronized in (3) is specific to this example. For the next pair -- and --, exhaustive ordered merging finds a schedule, but none with all doubles. This is an exact finite obstruction for those fixed shapes, using the proved compression rule, and is checked by the evidence program. Thus the displayed schedule does not extend to that pair merely by lengthening its runs while keeping synchronized. No universal obstruction for synchronizing is inferred from a leaf-count bound.
Phases and run matching
Before the first finish, between doubles two trees play ping-pong with swaps while the third waits at the bottom. Suppose emits a single naming . Then must answer with a single naming or with a double. After the double the stack is , so 's next mark may not be a single naming . A phase therefore ends only when one side emits a double as the other side's run of singles runs out. More precisely, if the phase starts with top and second , the numbers of singles emitted before its ending double are equal when emits the double, and differ by one in favor of when emits it. These endpoint conditions, not unconditional equality of the two run lengths, must be matched.
A selected node can be rigid or flexible. A node selected in one game only is rigid: every marked leaf below it is a single naming the same tree. The number of those leaves is fixed by at the nodes below, each when it is built. A node selected in both games is flexible: the policy chooses how its two selected child lists interleave and which children they share. These are order-preserving matchings, counted by Delannoy numbers. At a flexible node of depth two, any word with the prescribed numbers of marks for each tree can be realized. When the prescriptions differ at a flexible node of depth zero or one, rigid children are unavoidable.
Calibration at height one. Here a tree's root is its only internal node. With , Lemma 1 forces every count. has marks for each of and , and has marks for . Each second tree's count is (outside) or (inside). For the outside type, all doubles gives the rotation , which completes. For the inside type, use the one-summand diagram on printed p. 1210: , , . Here is a double, is singles naming , and . Its run completes. For , use , , and an empty word for . For , only the outside case is possible: there are no marks and the trees finish in order . These statements concern the consistent successor game specified above; they do not reconstruct the source's limit-ordinal proof.
The printed pattern does not transplant. The inside diagram gives the word shape : one double, then all singles naming , then all naming . Suppose selects at least two children at 's root and at least two at the depth-one node above 's first marked leaf in the game . Then no arrangement gives that shape. That first leaf is a double, so its ancestors are selected in both games. The second -selected child of comes after , and its leaves carry a -mark. A second -selected child of comes after , and its leaves carry a -mark. Neither mark may be a second double, so a single naming precedes a single naming . The printed schedules separate the two games' splitting by ladder levels below limit nodes. At height three every node is a successor node at which the Architect prescribes, so that separation is not available. This rules out only that schedule. The fixed-shape search below meets the hypothesis with an inside pair whose first-tree shape has a root with two children: the first has two children, the second one, and each depth-two node has one leaf. It finds a schedule for that pair.
Computations
The computations are in the evidence folder, whose program states its ranges and limits.
Fixed-shape strategies. Let and be ordered trees of height whose leaves all have depth . Suppose selects the shape whenever it moves first in a game and whenever it moves second. It reads each count off the node's place in the selected tree and ignores the numbers. Provided has as many leaves as or one fewer, this is a winning strategy for the colouring that is exactly on its outputs. That colouring is normalized, since every output pair has unequal root counts. Then carries , carries and carries , and the policies are exactly the merged mark words. The search is therefore exhaustive for these strategies. It covers every pair with degrees at most and at most leaves: (), (, ) and (, ; 33,278 pairs). It finds a deadlock-free schedule for every pair, and an independent replay of the three games checks each schedule.
Proposition 4 (erasing numerical and unselected history). Suppose 's prescription depends only on its own game's history after erasing all numerical labels, full child positions and unselected nodes. The retained history records the two tree roles, the ordered selected nodes and their ordinal labels and counts. In particular, a prescription cannot count the erased filler moves. Then the first tree's selection tree is one fixed shape and the second tree's is one fixed shape , whatever the Builder does. So acts as the fixed-shape strategy for .
Proof. Within a game, the next selected node to be built is determined by the selection trees built so far, because play follows tree order and switches at selected leaves. Unselected nodes receive one-element prescriptions by Lemma 1 and add nothing to the selection structure. By induction, the game's whole selection structure is a function of alone. All three games start from the empty history, so they produce the same pair.
Call such a strategy number-blind here. The fixed-shape search covers every such strategy whose shapes lie in its range. A strategy outside this checked class may read numerical labels, positions or filler histories, or may have fixed shapes outside the range. Nothing in Proposition 4 makes an arbitrary strategy invariant under this erasure.
One example shows that selections shared between games are needed. Take the inside pair with the path -- (two leaves) and the path --. The schedule , followed by the finishes of , , , completes. Every schedule for this pair gives a double. Here means that emits a double, and that emits a single naming .
A finite adversary model with a coarse completion test. A separate probe lets an adversary see all three games and choose counts from to at every selected internal node, including the roots. Thus it excludes empty root selections. The Builder chooses an ordered merge after each pair of counts. The probe equates 's two root counts and 's first-tree root count, and equates 's counts while its initial selections have remained common. These are only some of the equalities that an actual strategy must respect.
The completion filter is deliberately weaker than correctness. A pending selected subtree contributes at least one eventual leaf. An unexpanded internal node is treated as allowing further growth without computing its -dependent upper bound. A pair is rejected if its two closed totals are wrong, or if a closed total is already smaller than the other side's required minimum. The probe does not prove that a surviving prefix extends to a correct play with the bound , much less to one game-local winning strategy. It awards an adversary win upon a cycle, and Builder survival when no admissible adversary move remains or a mark names a finished tree. Exhaustive evaluation of this precisely defined finite process gives:
| height | outside | inside | |
|---|---|---|---|
| 1 | 3 | Builder survives | Builder survives |
| 2 | 2 | Builder survives | Builder survives |
| 2 | 3 | Builder survives | adversary wins |
| 3 | 2 | Builder survives | adversary wins |
For a concrete locality issue, compare root merges and in , with counts . The two -selected positions and the maximum can be identical in both arrangements. Before the first -selected child is built, the histories of can therefore be identical. The global-state adversary is nevertheless permitted to give different counts there, whereas a real must give the same count. The model also omits all numerical and unselected-node histories.
The inside loss at height two, where Theorem 28 is published, is a warning against using this model to decide the source interface. No winning game-local strategy or valid source-game counterexample is extracted. In particular, the table does not establish that every universal schedule must exploit a particular locality argument: its coarse completion test is an additional discrepancy. The exact obstruction proved above for does not rely on this model.
The conditional bridge and the open gap
The held route has these links.
- Normalization (author-recorded). Equal-block pairs may be assumed to have colour . This is author-recorded on the interface page, using Theorem 27 at statement depth.
- Source interface S (author-recorded). The finite-height reconstruction proves the dichotomy and finite-cover refinement for the coherent zero-based game by well-founded fusion and Nash-Williams, the latter an external statement-depth premise. It constructs the full-type color- family in the universal-Builder case by fresh-label stages, coarsening, and a finite-height freedom argument. Normalization is an explicit hypothesis of this Builder implication. The proof includes complete numerical and filler histories and gives a separate finite threshold for each current history and prescription. It does not extend the source interface to limit nodes. The local scheduling constructions themselves do not require S.
- Local realization and fixed shapes. Lemmas 1--3 and Proposition 4 above are author-recorded. They give a finite model for a specified fixed-shape strategy, and a local extension rule for actual adaptive histories; they do not identify the two settings.
- Gap G. For every winning Architect strategy on an infinite at height three, and every prescribed finite lower-threshold rule, construct three complete correct plays sharing the same three trees. A sufficient construction chooses actual numerical moves and child merges at the available histories while avoiding a cycle. This is the interface's unresolved three-game step.
- Reduction of G (author-recorded). Theorem 5 and Propositions 6 and 7 construct the three plays, online and for actual histories, when all outputs are outside, inside top-first, or inside top-last. By Corollary 2 the remaining obligation is G-mid: the same construction for middle strategies.
Suppose a normalized colouring has no colour- triangle, and assume G. Apply the author-recorded source interface S. In the Architect case, G gives three legal plays with shared trees, and their three outputs have colour . This contradicts the assumption, so the Builder case holds. Together with the author-recorded normalization, this proves conditional on G, and the finite-cover reduction leaves G-mid as its open sufficient premise.
G splits into two parts along Proposition 4. Both parts are now proved outside the middle class, and both remain open inside it.
- G1 (fixed shapes). Every pair of height-three shapes , with having as many leaves as or one fewer, admits a deadlock-free schedule. This is a finite combinatorial statement about merging ordered trees. It is checked for degrees at most and at most leaves, and it is open in general. A proof would settle the number-blind class through Proposition 4 and the fixed-shape realization argument. The empty first-shape case is already handled by concatenating the three unmarked trees.
- G2 (actual histories). Strategies may read numerical labels, full child positions and all unselected-node moves. A new argument must handle their changing prescriptions without replacing them by counts chosen with knowledge of the other games. No canonization or uniform control of this dependence is proved here. A Ramsey reduction for two colors does not by itself make unbounded integer prescriptions constant on an infinite set.
The retained tools are these.
- Identical histories. While 's initial selections and all numerical labels are common, its two histories and prescriptions agree.
- Last-node forcing. If every other selected-leaf count is determined and a single label- node is the only unresolved source of leaves, its count is fixed by Lemma 1(3). This does not determine a higher node's child count while its descendants' counts remain open.
- The endgame. After the first finish nothing can fail.
- Flexible depth-two nodes. Once both counts are known, they realize any ordered merge of those two prescribed leaf lists.
The difficult configuration is a rigid region whose eventual number of marks is not known when an earlier shared child list is committed. Game locality alone does not reveal that count before the numerical history on which it depends exists. Lemma 2 resolves the current node's two requests, but does not solve this forward-dependence problem.
A failure of three-output existence for fixed and a specified threshold rule would give a triangle-free graph of outputs obeying those restrictions. Correct pair outputs determine their labels from their induced partitions, so a triangle in that graph would itself supply three coherent plays. This does not give a negative partition coloring on . In fact the fixed-prefix obstruction shows that every graph supported on disjoint leaf sets has a full-order-type independent set on unrestricted . A negative construction must instead specify a full-type host and prove that every full-type subset of that host contains a color- pair.
Exact three-summand extension and obstruction
For the full countable target put
Use a collapsible nested ladder on as in Definitions 4 and 14, respecting these partial-sum boundaries. At a limit boundary take , as in the remark after Theorem 12. Here is zero or a limit: an infinite summand can only follow other infinite summands in the displayed non-increasing decomposition. When is a successor there is no ladder value to prescribe; the ancestral step is the ordinary predecessor step instead.
The missing replacement for Lemma 26 is this implication: for a normalized coloring on this , an Architect win on an infinite , with history-dependent sufficiently-large bounds, implies a color- triangle. Here normalized means color on equal block types in Definition 12: equal root length at a successor root, and equal root-child ladder index at a limit root. A sufficient stronger construction uses the same winning strategy in three correct complete plays sharing . It has to satisfy all of the following simultaneously.
- At every shared successor node, the two maxima give the same full child list, including all unselected children; the two selected lists have the sizes actually prescribed at their respective histories.
- At every shared limit node, the common maximum gives the same ordinal-labeled child. The two sets specify splitting intervals in that same descendant tree; they are not lists of immediate children that can simply be interleaved.
- The Architect moves at each compulsory partial sum and at the optional lower nodes allowed by Definition 19. The collapsing maps determining those moves must have compatible domains, images, and compositions in the shared tree, with the nested and commuting properties of Definition 14 retained.
- Leaf labels agree between the two games of each tree. The chronology in each pair is legal, its marked leaves are its true induced cell maxima, every label is sufficiently large, and the construction terminates. These requirements cover both inside and outside outputs, unless a justified finite-cover refinement removes a class.
The general-ladder dichotomy and Builder implication remain external source inputs. The finite-height reconstruction does not establish their limit-node compatibility. A replacement must state coherent successor and limit conventions and check its composition with those inputs; the finite-height proof alone does not supply that check.
At the limit-node requirements disappear, but the middle case still lacks a construction. The specific positive obstruction is to the current phase templates: a shared child list of must place its later double before the future prescriptions determining the relevant size in have been made. The local merge lemma supplies only the current two counts. Uniformity under erasing numerical and unselected history is not available. This is an unproved scheduling input, not a proof that G-mid is false. Fixed-shape schedules discharge it only for strategies with those fixed prescriptions.
The negative direction has two separate outstanding inputs: a triangle-free middle pattern or other coloring, and unavoidability in every full-type subset of a specified host. The fixed-prefix embedding proves that the unavoidability assertion on unrestricted is false for every coloring supported on disjoint leaf sets, including strategy-output graphs. The assertion on an appropriate separated host remains unknown here. The containment interpretation is ruled out by L67; the selection-shape interpretation is explicit but has not supplied a triangle-free height-three pattern.
Thus neither direction decides , and no three-summand Lemma-26 replacement is supplied. Reopening the positive construction requires a rule handling the unknown future count, or a justified refinement to strategies with a more usable dependency structure. Reopening the negative construction requires both the specified host and an exclusion argument respecting the actual shared trees. These are obstructions to the recorded routes, not an impossibility theorem for other approaches.
Remaining test and standing
The positive route at rests on the author-recorded normalization and finite-height source interface S, and the unproved G-mid, the three-game construction for middle strategies. Theorem 5 and Propositions 6 and 7 discharge G outside the middle class, online and for actual histories.
The next discriminating test is G-mid. Its fixed-shape part asks for a triangle schedule for every inside pair at height three with middle. Lemma 8 excludes the two spine words for the second tree, and Proposition 9 settles the case of two children at the top split under a condition on . The bounded census found schedules for all middle pairs in its range, so a counterexample, which would be a triangle-free pattern coloring, would have to be larger. The online part must place each double of the second tree without knowing the size of the first tree's first child. A failure of G-mid would not by itself give a negative partition relation: that still needs a coloring of all pairs and a color- pair in every subset of full order type.
The printed patterns support the reduction under the selection-shape reading of the pattern-level page. All three are inside. Theorem 31's pattern is top-first and excludes only six-cliques, and the triangle-free pattern of Theorem 33, at height four, is middle. Its exclusion argument uses a level at which the second tree has interior cells and the first has none, besides the first tree's own two upper levels. At height three, once the first tree uses all three levels, no such level remains. This is a heuristic for a positive answer, not a proof.
The first-tree synchronization mechanism is closed by the symbolic obstruction, and the fixed three-versus-two strategy is fully handled by (3). A rule that instead keeps entirely synchronized is also not general: the finite evidence contains a height-two fixed-shape counterexample to that restriction. The literal transplant has the branching obstruction above; Proposition 6 is exactly the class in which it works.
The extension past is not proved here. The constructions of Theorem 5 and Propositions 6 and 7 use only successor nodes at which both games prescribe. At a limit node on a spine the two games' labels must share their maximum, which fixes the single child, while their sets of ladder intervals can be chosen separately; each game's next Architect move under Definition 19 is then a node of the shared tree, and the spine merge applies at every successor node where either game splits. This suggests that Theorem 5, Propositions 6 and 7 and the reduction hold for every countable , but the check against Definitions 11, 13 and 19 with limit nodes is open. Ladder levels give the Builder freedom that height three lacks: in the printed one-summand schedule they separate the two games of the first tree. So summands equal to , as in , are expected to be the hardest part of the three-summand family.
All local arguments and computations are author-recorded and unreviewed. Definitions 6--19 and the scheduling discussion of Lemma 26 were read in the held journal transcription, with Definitions 9--11 on printed p. 1200, the game rules on pp. 1203--1204 and the one- and two-summand diagrams on pp. 1210--1212 inspected in page images. The two-summand placement rules are stated through the sets of Definition 9(5), which exist only at limit nodes. Read with replaced by the selected positions at a successor root, the rule for 's root contradicts the diagram's first leaves, so the printed schedules do not literally cover . Theorems 19 and 21 and Corollary 2 were read with their proof prose; the companion reconstruction proves the finite-height source interface for the coherent game, using Nash-Williams at statement depth. Theorems 27 and 28 supply external statement-depth premises, not independently checked proofs. The negative patterns in Theorems 31--33 are used only through the reading and calibration stated on the pattern-level page. No negative coloring, full-order-type avoidance proof, or resolution of is claimed.