Unavoidable Pattern¶
Require that, over every finite alphabet, some alphabet-dependent length threshold forces every longer word to contain a contiguous nonerasing morphic instance of the pattern.
Core Idea¶
An unavoidable pattern is a finite pattern of variables whose nonerasing substitution instances cannot be excluded from arbitrarily long words over any finite alphabet. Let Δ be a finite variable alphabet and let the nonempty pattern be p ∈ Δ⁺. For a finite nonempty terminal alphabet Σ, a nonerasing morphism h: Δ* → Σ* assigns every variable X a nonempty word h(X) ∈ Σ⁺ and extends by concatenation. A word w ∈ Σ* encounters p when some contiguous factor of w is h(p) for such an h.
Scope of Application¶
Unavoidable patterns belong literally to combinatorics on words and neighboring formal disciplines.
- Pattern avoidance. They mark the boundary between variable patterns that infinite words can exclude and those forced in every sufficiently long word on every finite alphabet.
- Extremal word length. For an unavoidable
pand fixed alphabet size, one studies the longest avoiding word or the least forcing threshold. Even when existence is settled, sharp bounds can be difficult. - Formal languages and algorithms. Encounter testing asks for a factor together with a consistent nonerasing variable substitution; classification asks whether any finite-alphabet infinite avoidance witness exists.
- Free semigroups and identities. A pattern is a term in a free semigroup, and nonerasing substitutions are homomorphisms between free semigroups.
Clarity¶
Keep four levels separate: pattern, instance, encounter, and unavoidability.
A pattern is a variable word such as ABA. Its A and B do not yet denote terminal letters. An instance is a word such as 0110 obtained by selecting one morphism—here h(A)=0 and h(B)=11, so h(ABA)=0110. A larger word encounters the pattern if it has that instance as a contiguous factor.
Manages Complexity¶
The definition compresses an infinite adversarial search into a threshold property. For a fixed Σ, every candidate word below N_Σ can in principle be inspected; beyond that boundary, the theorem certifies that no new counterexample can exist. This separates two tasks: deciding whether a threshold exists and estimating how large the least threshold must be.
Abstract Reasoning¶
Audit the quantifiers before searching. Decide whether the claim is about a fixed alphabet, all alphabets of one size, or every finite alphabet. Record whether the threshold may depend on the alphabet and whether witnesses may depend on each tested word.
Separate variables from terminals. Treat equal variables as equality constraints on whole nonempty blocks. A candidate match is invalid if two occurrences of A receive different strings, even when every position looks locally similar.
Knowledge Transfer¶
Within its home disciplines, the abstraction transfers literally. Combinatorics on words emphasizes finite and infinite avoidance; free-semigroup theory reads patterns as terms and substitutions as homomorphisms; formal-language and algorithmic work treats encounter as constrained factor matching; complexity work studies the size of forcing thresholds. The same variables, nonerasing maps, factors, and quantifier order survive each transfer.
The broader transferable skeleton is a finite forbidden schema that eventually becomes compulsory under every construction from a bounded vocabulary.
Relationships to Other Abstractions¶
Current abstraction Unavoidable Pattern Domain-specific
Parents (1) — more general patterns this builds on
-
Unavoidable Pattern is part of Boundedness Prime
Unavoidable Pattern strictly presupposes
prime:formal_system.
Hierarchy path (1) — routes to 1 parentless root
- Unavoidable Pattern → Boundedness
Neighborhood in Abstraction Space¶
Unavoidable Pattern sits in a sparse region of the domain-specific corpus (68th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Formal Languages, Types & Programs (41 abstractions)
Nearest neighbors
- Pattern Language (Formal Languages) — 0.87
- Hamming Scheme — 0.86
- Morphology — 0.85
- Trie — 0.85
- Phonotactics — 0.84
Computed from structural-signature embeddings · 2026-09-08