Delphi.science

Algorithms for Short Human-Verifiable Proofs of Non-Word-Representability

Source: arxiv.org/abs/2611.08553

Sergey Kitaev, Junting Zhong

arXivarxiv/2611.08553Nov 5, 2026math.COscore 0

A graph is word-representable if it can be represented using alternation of letters in words. The class of word-representable graphs generalizes several important graph families and admits a characterization via semi-transitive orientations. Recognizing word-representability is an NP-complete problem, and a major bottleneck in the theory of word-representable graphs is providing efficient justifications of non-word-representability of graphs, rather than merely referring to software verification. Recently, Kitaev and Sun initiated the development of methods for the automatic generation of…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.08553
curl -X POST /api/v1/records/arxiv/2611.08553/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.08553/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'