Wiki
Wiki

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

Updated


The negative-pattern route to Problem 592 needs a precise notion of a cell's level. In Schipperus's journal paper, Definition 29 on printed p. 1214 uses G(T,E)G(T,E), with EE a convex set of leaf labels, whereas Definition 9 defines GG with a partition as its second argument. The successor-tree interface records this unresolved interpretation. The argument below rules out one specific proposed completion of that notation. It does not identify the intended definition or refute Theorem 32.

What the containment rule gives

The exact rule and its two obstructions are recorded in L67, at tier 0. For a cell EE, the proposed rule R1R_1 takes the label of the lowest ancestor of max⁡E\max E whose whole leaf set is not contained in EE, except that first and last cells receive level 33.

With this rule, the displayed height-three pattern

A3,B3,A1,B3,A2,B3,A1,B3,A3A_3,B_3,A_1,B_3,A_2,B_3,A_1,B_3,A_3

has cliques of every finite size. The explicit family uses four nested bands of leaf labels and extra terminal root subtrees to give strictly increasing root lengths. The proof checks all pairs symbolically; no finite search is used for this universal conclusion.

On a good partition the same rule instead gives level 11 to every interior cell. Its maximum leaf belongs to G(T,D)G(T,D), while the last child of its label-11 parent does not. That parent therefore has a later leaf outside the cell. Consequently neither the interior A2A_2 nor the interior B3B_3 cells in the displayed word can occur on good pairs.

These are author-recorded deductions by Plasma AI, using the definitions rather than a source theorem. Definition 29 and the displayed Theorem 32 pattern were checked against printed p. 1214. They do not identify the intended source level.

A reading by selection shapes

A second reading gives the printed patterns a definite meaning on good pairs. For an interior cell EE of TT, let its level R3(E)R_3(E) be the level of the lowest common ancestor of max⁡E\max E and the last leaf of TT before min⁡E\min E; first and last cells keep the top level, as in Definition 29. Here the level of a node is kk when its ordinal label lies in (βk−1,βk](\beta_{k-1},\beta_k], so at finite height it is the label itself.

The leaf just before an interior cell is the maximum of the previous cell, since the cells partition the ordered leaf set into consecutive intervals. So R3R_3 assigns to each interior cell the level of the lowest common ancestor of two consecutive selected leaves. A pattern word therefore fixes the level word λ\lambda of the first tree's selection shape XX and the level word μ\mu of the second tree's shape YY. Each level word determines its ordered selection tree. Under R3R_3 the three printed patterns are fixed pairs of shapes. The table gives them at the finite instances β=2,3,4\beta=2,3,4, where the height equals the number of summands:

sourceheightλ\lambda (first tree)μ\mu (second tree)
Theorem 3122(1,1,1)(1,1,1)(2,2)(2,2)
Theorem 3233(1,2,1)(1,2,1)(3,3)(3,3)
Theorem 3344(1,1,3,1,4,1,3,1,1)(1,1,3,1,4,1,3,1,1)(1,1,2,2,2,2,1,1)(1,1,2,2,2,2,1,1)

All three are of inside type. The steps of the printed proofs checked here hold under this reading: that no second-level cell of AA is isolated in Theorem 31, that no third-level cell is isolated and that the next tree lies inside one second-level subtree of the previous one in Theorem 32, and that BB isolates exactly one fourth-level cell of AA in Theorem 33. The complete exclusion arguments were not re-derived, so the reading is a calibrated proposal, not the identified intended definition.

The reading connects the negative route to the height-three attack. By the fixed-shape realization there, a pair of shapes has no triangle schedule exactly when its R3R_3 pattern coloring has no color-11 triangle on good pairs. The fixed-shape strategy for the pair wins for that coloring, so Theorem 5 and Propositions 6 and 7 there give a triangle whenever the pair is outside, top-first or top-last. A triangle-free pattern coloring must therefore be inside and middle: neither the first two nor the last two selected leaves of the first tree may split at its top split. This matches the table. Theorem 31 is top-first and excludes only six-cliques. Theorems 32 and 33 are middle.

Theorem 32's pattern has a triangle. In the mark-word notation of the attack, the three words

A: B D C C D B,B: A D C C C A,C: A A D B BA:\ B\,D\,C\,C\,D\,B,\qquad B:\ A\,D\,C\,C\,C\,A,\qquad C:\ A\,A\,D\,B\,B

complete the stack process. Their separator levels are (1,1,2,1,1)(1,1,2,1,1), (3,1,2,1,3)(3,1,2,1,3) and (3,3,3,3)(3,3,3,3), and the two projections of each word recover λ=(1,2,1)\lambda=(1,2,1) and μ=(3,3)\mu=(3,3). This agrees with the census in the attack's evidence and with the theorem's exclusion of only four-cliques. A triangle-free pattern for three summands would have to come from a larger middle pair; the census found none among its bounded pairs. Its unavoidability in every subset of full order type would still need a proof.

A fixed prefix defeats disjointness on the unrestricted host

The unavoidability issue has a simple obstruction independent of the choice of levels. For every finite h≥1h\ge1, every coloring of [Wh]2[W_h]^2 whose color-11 pairs have disjoint leaf sets has a color-00 subset of the full type ωωh\omega^{\omega^h}.

To prove this, fix the unary tree P∈Wh−1P\in W_{h-1} whose only leaf is labeled 00. Shift every leaf label of T∈WhT\in W_h up by one, and prepend PP to the list of children of its root. Call the resulting tree e(T)e(T). Its root length is one greater than that of TT, and its remaining root subtrees have the same order as those of TT. Thus ee is an order embedding of WhW_h into itself. Every leaf set of a tree in its image contains 00. No pair in the image can have color 11, proving the assertion.

In particular this obstruction applies to the graph of outputs of any Architect strategy, with or without restrictions on the Builder's infinite set or thresholds. Correct game outputs have disjoint leaf sets. Such an output graph, colored 00 on all other pairs of WhW_h, therefore always has a full-order-type independent set. Failure of a three-output construction cannot yield a negative partition relation by this extension of its output graph.

This does not preclude a pattern coloring on a special full-order-type host Z⊆WhZ\subseteq W_h. An order isomorphism can transport a coloring of [Z]2[Z]^2 to the target ordinal without preserving the original leaf labels. The finite-height family construction supplies such hosts independently of a coloring: unequal-root-length pairs have disjoint full label sets and are good. A full-type subset of such a host cannot be confined to a single root-length block, and the fixed-prefix embedding above need not have its image in that host.

The exact missing negative assertion is consequently host-relative. One must specify ZZ and a color-11 pattern, prove that it has no triangle, and prove that every Y⊆ZY\subseteq Z with ot⁡(Y)=ωω3\operatorname{ot}(Y)=\omega^{\omega^3} contains the pattern. A proof merely that ZZ itself contains the pattern is insufficient. The freedom argument in Schipperus's Section 12 begins with a special full-type family; it cannot be applied as unavoidability on arbitrary subsets of the unrestricted WhW_h. No new unavoidability theorem is asserted here.

Collapsing the four-level negative pattern

One possible negative construction is to merge two adjacent levels of the height-four pattern of Theorem 33. Under the selection-shape reading its words are

λ=(1,1,3,1,4,1,3,1,1),μ=(1,1,2,2,2,2,1,1).\lambda=(1,1,3,1,4,1,3,1,1),\qquad \mu=(1,1,2,2,2,2,1,1).

Identifying levels 44 and 33 does not work. The resulting first shape has four top children, single blocks of sizes 3,2,2,33,2,2,3. Its last two leaves are siblings, and the second shape's first three leaves are siblings. Proposition 11 of the canonical sketch applies with ∣F∣=3|F|=3, and supplies a triangle. This is a symbolic obstruction to that collapse, including every large numerical realization of its fixed shapes.

Identifying levels 33 and 22, and renaming the old level 44 as 33, instead gives the concrete pair

λ′=(1,1,2,1,3,1,2,1,1),μ′=(1,1,2,2,2,2,1,1).\lambda'=(1,1,2,1,3,1,2,1,1),\qquad \mu'=(1,1,2,2,2,2,1,1).

The first shape has two top children with block sizes (3,2)(3,2) and (2,3)(2,3); the second has block sizes (3,1,1,1,3)(3,1,1,1,3) at level 22. No triangle exclusion or completing schedule for this pair is proved here. In particular the published exclusion proof does not transfer: it uses that the later tree isolates a level-22 cell while the earlier tree has no such interior cell. The collapsed first word has interior level-22 cells, so that hypothesis is false. Deciding this pair is a specific finite structural test, still subject to the separate host-relative unavoidability obligation. The ten leaves of its first shape place it outside the retained census, whose leaf bound is six.

Consequences for the route

The rule R1R_1 cannot support the four-clique exclusion required by that pattern. Restricting pairs to different root lengths does not repair it. The construction makes no assertion that its pairs are correct plays of the Architect--Builder game or that they belong to the special full-type set used in a source proof. L67 separately explains why restricting this rule to good pairs does not recover the displayed pattern. Any replacement rule still needs its exclusion proof and its realization theorem.

Nor does finite height turn the game into a finite problem by itself. At a successor node, Definition 9 gives one selected child position for each child in GG, together with the last child position. If the last position is mm, the full tree has m+1m+1 children, however small the selected set is. An increasing relabeling preserves the selected set's order and size but can change mm, so it need not preserve the underlying tree. A bound on selected leaves does not bound these unselected child subtrees.

Consequently, a finite pattern search requires a proved compression and expansion rule, or an explicit bound on the full trees and a conclusion limited to that bound. A positive three-game schedule must separately handle strategy choices that depend on the numerical history, and must realize arbitrarily large legal moves on the same three trees. A finite static pattern and an adaptive winning strategy are not interchangeable without such a bridge. Reopening the pattern route requires a justified level definition and its actual tree constraints, calibrated against a published negative relation before new searches are interpreted. The selection-shape reading above is calibrated in that way against the checked proof steps; under it, the fixed-shape realization of the attack supplies the compression and expansion rule for pattern searches.

The held Darby paper supplies a concrete coloring for comparison. Its Definition 3.5, on printed p. 212, defines Γ1\Gamma_1 by nine interleaved segments. The outer two AA segments and every BB segment contain box coordinates; the three interior AA segments contain none. Of those three, the middle contains a triangle coordinate, while the other two are nonempty and contain none. Encoding these requirements as levels 3,2,13,2,1 gives exactly the displayed word. Box and triangle coordinates are defined using prefix levels and sublevels, so this comparison does not identify them with the containment rule R1R_1 or with Schipperus's cut-piece levels. Darby's Lemma 3.6 states that Γ1\Gamma_1 has no four-clique. Transferring that exclusion to another model requires an actual correspondence of coordinates and admissible pairs, not just the same word.

Darby's Theorem 6.1, on printed p. 221, proves negative relations against a six-element target when α\alpha is additively but not multiplicatively indecomposable, and against a four-element target when also αˉ\bar\alpha is not multiplicatively indecomposable. In the problem's notation α=ωγ\alpha=\omega^\gamma, these hypotheses correspond respectively to at least two and at least three indecomposable summands in γ\gamma. The four-summand negative relation against a triangle is instead attributed to Schipperus in Theorem 6.4, without proof there; its printed exponent and the surrounding interpretation are qualified on the theorem card. Conjecture 6.9, on printed p. 222, explicitly leaves the three-summand positive relation against a triangle open. Thus Darby's proved four-clique exclusion calibrates a coloring, but does not decide the three-summand question.

Definition 3.5 and the statements of Lemma 3.6, Theorems 6.1 and 6.4, and Conjecture 6.9 were checked against the printed pages. The proofs of Darby's exclusion and realization theorems have not been checked here. The remaining source obligation is to compare those definitions with Schipperus's Definition 29 and prove the needed transfer to the adaptive game. Larson's An ordinal partition avoiding pentagrams concerns the two-summand negative relation with a five-element target; its full pattern definitions and proof remain unexamined here. Neither this comparison nor L67 removes the separate adaptive-scheduling gap.