Results on superstrings, the hierarchical graph, forced occurrence counts and periodic layers, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Preprocessing — Lemma 1.1. Deleting empty, repeated and contained strings keeps all common superstrings; the substring set V has O(L^2) elements and no element of V properly contains a required string.
• Reading a walk — Lemma 2.1. A closed walk from the empty word visiting all required strings spells a common superstring whose length is the cost of the walk.
• Euler tours — Lemma 3.1. A balanced finite multiset of directed edges with connected support has a closed walk using every edge once.
• Superstrings from balanced multisets — Corollary 3.2. A balanced multiset with connected support containing the empty word and all required strings gives a common superstring of length equal to its number of up edges.
• Factor-2 approximation (OpenAI) — Theorem 4.1. A deterministic polynomial-time algorithm outputs a common superstring of length at most 2 OPT.
• Blocked occurrences — Lemma 1.1. B_A(s; N_T) is the number of blocked occurrences of s in T, at most N_T(s).
• Occurrence lower bound (OpenAI) — Lemma 2.2. The forced counts satisfy m(s) <= N_T(s) for every common superstring T; hence W = sum of m(c) <= OPT.
• The base graph (OpenAI) — Lemma 3.1. The base graph is balanced, contains every required string, and has W up edges and W down edges.
• Windows of a closed walk — Lemma 1.2. On the lift of a closed walk, every window [x,e) spells the current word A[x,e) of the walk's periodic text.
• Recorded occurrences (OpenAI) — Lemma 2.1. For every decomposition of the base graph into closed walks, the recorded occurrences of s number m(s).
• Ordered layers (OpenAI) — Lemma 3.1. The walks of a group can be replaced, edge for edge, by pointwise ordered layers of turn length the least period p; all layers together cost W.
• Matching window (OpenAI) — Lemma 4.1. Blocked recorded occurrences number B_A(s;m); every unblocked one lies in a layer window agreeing with the template throughout.
• Agreement bounds — Lemma 5.1. Different periodic texts of periods p and q agree on fewer than p + q consecutive positions (fewer than p if both have period p).
• Maximal rotation — Lemma 5.2. A different text of period q whose forward words are at most the maximal forward word of A at t cannot agree with A on the q positions starting at t.
• Following ordered windows — Lemma 1.1. Windows with nondecreasing starts and ends are joined by a walk of cost equal to the increase of the ends.
• Joining an ordered band — Lemma 2.1. Layers of one group with H - E <= h, h a multiple of p, are joined at cost at most h.
• Collective link (OpenAI) — Lemma 2.2. Under (2.1), k layers of period p are attached to a record at cost kp.
• Host requests (OpenAI) — Lemma 2.3. A host and all layers requesting a connection at its records are rooted with the host's budget and the requesters' budgets.
• Choosing k (OpenAI) — Lemma 3.1. The threshold search stops with 1 <= k <= n, the top k layers form a narrow band, and at most k recorded occurrences of the shortened word have the group's own alignment.
• Partition into rooted layers and blocks (OpenAI) — Proposition 3.2. After processing, every layer is rooted or belongs to exactly one block with a reserved planned link.
• A short contact on a maximal link (OpenAI) — Lemma 4.2. On a cycle of blocks, the link of the block with the largest forward word reaches a word no longer than the period of its target.
• Connecting the base graph (OpenAI) — Theorem 4.3. Closed walks of total cost at most W connect every layer to the empty word.

Reading order

Read the lessons in order; each uses the notation and results of the previous ones.