[#P3068] Minimum avoiding alphabet for every avoidable word

A neutral schematic of the objects and relations in the statement.

Problem. Let \(u\) be a finite word using \(c(u)\) distinct variables. Define \(m(u)\) as the least alphabet size admitting an infinite word with no contiguous factor equal to \(\phi(u)\) for any nonerasing morphism \(\phi\). Determine \(m(u)\) for every avoidable word \(u\).

1Context

Known frontier: General estimates and values for special pattern classes are known. Open boundary: Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u.

2Problem setup

Definition 1 (avoidable word). A pattern u is avoidable when such an infinite word exists over some finite alphabet.

Definition 2 (nonerasing morphism). A morphism from pattern variables to nonempty finite words, extended to a pattern by concatenation.

Remark 1. This is Problem 2.5 in the 2026 Lyapin Notebook; the public formulation fixes the input and equivalence conventions needed for independent review.

3What counts as a solution

Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u.

1Status

Current status (Current status and exact unresolved remainder). OPEN as checked on 2026-08-01. Strongest checked neighboring result: General estimates and values for special pattern classes are known. Exact unresolved remainder: Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u.^[1][2]

1Records

Record	Kind	Assessment
	Result	Supported
claim · Claim 1 OPEN as checked on 2026-08-01. Strongest checked neighboring result: General estimates and values for special pattern classes are known. Exact unresolved remainder: Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u.^[1][2] Relevance to this problem This is the dated publication status for the canonical target Minimum avoiding alphabet for every avoidable word. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details The problem was checked as open on 2026-08-01. The strongest neighboring result found in the cited sources is: General estimates and values for special pattern classes are known. The exact unresolved remainder is: Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u. A complete resolution must meet the following acceptance conditions: - Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u. Open full record →
	Result	Supported
claim · Claim 2 General estimates and values for special pattern classes are known.^[1][2] Relevance to this problem Locates the present research frontier immediately below Minimum avoiding alphabet for every avoidable word. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details General estimates and values for special pattern classes are known. This leaves the following boundary unresolved: Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u. The distinction is retained here so a restricted theorem, finite computation, or neighboring case is not presented as a solution of the full target. Related: Claim 1 Open full record →
	Trace	Supported
attempt · Route 1 The exact formulation, named variants, 2025–2026 updates, and repository-wide semantic duplicates were checked on 2026-08-01. The source collection still marks the stated remainder open. Living-database status remains subject to later literature not indexed there.^[1][2] Relevance to this problem Documents why Minimum avoiding alphabet for every avoidable word was treated as a distinct open target on 2026-08-01. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope No narrower scope recorded Sources Reference 1, Reference 2 What happened The audit ran on 2026-08-01 across source collection and its cited primary literature, Crossref/arXiv or MathSciNet stable records, TheoremDB published, prospecting, formal-conjecture, packet, and retired corpus. It checked the exact statement, its named or normalized variants, recent status evidence, and the controlled TheoremDB corpus. Queries included: - "Lyapin notebook" "Problem 2.5" - "Minimum avoiding alphabet for every avoidable word" - site:arxiv.org semigroup "avoidable word" open problem The exact formulation, named variants, 2025–2026 updates, and repository-wide semantic duplicates were checked on 2026-08-01. The source collection still marks the stated remainder open. Living-database status remains subject to later literature not indexed there. Related: Claim 1 Open full record →
	Trace	Reported
attempt · Route 2 Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u. Relevance to this problem Turns the remaining uncertainty in Minimum avoiding alphabet for every avoidable word into a checkable research target. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded What happened Research should address this boundary directly: Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u. A claimed resolution should satisfy every item below and preserve the statement's exact quantifiers and normalizations: - Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. OPEN as checked on 2026-08-01. Strongest checked neighboring result: General estimates and values for special pattern classes are known. Exact unresolved remainder: Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u.

Equivalent-formulation queries: "Lyapin notebook" "Problem 2.5"; "Minimum avoiding alphabet for every avoidable word"; site:arxiv.org semigroup "avoidable word" open problem
Strongest checked neighboring result: General estimates and values for special pattern classes are known.
Exact unresolved remainder: Give a formula or effective complete classification returning the exact integer m(u) for every avoidable u.

How the 4 records connectTyped relations and evidence flow

ProblemMinimum avoiding alphabet for every avoidable word

Claim 1Current status and exact unresolved remainderin this packetSupported
Route 1Dated source and duplicate auditchecksSupported
Claim 2Strongest checked neighboring resultinformsSupported
Route 2Work at the unresolved boundaryaddressesReported

2See also

Cycle Double Cover Conjecturecombinatorics
The Total Coloring Conjecturecombinatorics
Sabidussi's Compatibility Conjecturecombinatorics

How to cite

TheoremDB contributors, “Minimum avoiding alphabet for every avoidable word,” TheoremDB research memory, snapshot of August 1, 2026. https://theoremdb.org/statements/avoidable-word-minimum-alphabet

This page as plain text: avoidable-word-minimum-alphabet.md

This problem includes 4 records joined by 3 typed links, sourced from doi.org^[1], current as of August 1, 2026.

1References

Packet source. Bershadsky, S., Kublanovsky, S., and Mashevitzky, G., “The Lyapin's notebook: a collection of unsolved problems in Semigroup Theory”. arXiv (2026). DOI 10.48550/arXiv.2604.04763. Problem 2.5 and its immediately following status paragraph. ↗ open copy ↗preprint · primary source · arXiv:2604.04763, checked 2026-08-01 · checked 2026-08-01Source use: original summary.States the numbered open problem, identifies its proposer, and summarizes known special cases.Also cited at S. Bershadsky, S. Kublanovsky, and G. Mashevitzky, “The Lyapin’s notebook: a collection of unsolved problems in Semigroup Theory,” arXiv:2604.04763 (2026). Problem 2.5 and its immediately following status paragraph.Source used to assess the problem's recorded status.For Minimum avoiding alphabet for every avoidable word: This is the dated publication status for the canonical target Minimum avoiding alphabet for every avoidable word.Source named by the research packet.
Kirby A. Baker, George F. McNulty, and Walter Taylor, “Growth problems for avoidable words”. Theoretical Computer Science 69(3) (1989), 319-345. DOI 10.1016/0304-3975(89)90071-6. Bounds for avoidable patterns. ↗journal article · secondary source · checked 2026-08-01Source use: original summary.Provides established estimates and foundational definitions for the exact alphabet-size problem.Source used to assess the problem's recorded status.For Minimum avoiding alphabet for every avoidable word: Provides established estimates and foundational definitions for the exact alphabet-size problem.

Original TheoremDB statement and summary based on citation-only scholarly sources; no source prose, proof, table, code, or figure is reproduced.

[#P3068] Minimum avoiding alphabet for every avoidable word

1Context

2Problem setup

3What counts as a solution

1Status

1Records

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Records

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance