观点

Lemma 17 ([Local flattening]). Suppose a run began with a switch out of a node Q_0 , using left boundary a_0 in the resulting run frame, and entries G_0∩≥h_0, D_ a_0 , Q_0 D_ a_0 ⊆G_0 . Let U⊆Q_0 be a later parent in that run. If the entry …

Lemma 17 ([Local flattening]). Suppose a run began with a switch out of a node Q0 , using left boundary a0 in the resulting run frame, and entries G0∩≥h0, Da0 , Q0 Da0 ⊆G0 . Let U⊆Q0 be a later parent in that run. If the entry derived from the first displayed entry survives into an unpruned carry out of U , write its current form as G0∩≥k . Then the carried portion of this pair has the same union on U as the global upset Da0 ∪≥k.

证明 1证否 0作为观点被引用 1链条图发起推演

发起推演1

证明
Lemma 16. Every pruned list produced by this construction has at most five…Lemma 15. For either update, assuming in the switch case, the pre-pruning…观点
Track the original entries through later reindexings. As long as the first entry survives, a suffix operation cannot trim or discard the second entry: a cutoff at that later index would already discard the first, permanently. Thus the second entry is either still carried untrimmed, or was pruned because it was empty on some intermediate node containing U . In the latter case D_ a_0 ∩U=∅ . On U∩D_ a_0 , the second entry, when this set is nonempty, therefore selects every job. Every job of U D_ a_0 lies in G_0 , because U⊆Q_0 . On that remainder the first entry selects exactly the rank suffix ≥k . This proves equality of the two unions on U . Both factors in are upsets, so their union is globally upward closed, although it need not agree with the carried pair outside U .
更多详情 →