A Computational Obstruction to Swapping Area and Dinv: An Automata-Theoretic View of the $q,t$-Catalan Symmetry

Jineon Baek; Byung-Hak Hwang; Joonhyun La; Hongseok Yang

A Computational Obstruction to Swapping Area and Dinv: An Automata-Theoretic View of the $q,t$-Catalan Symmetry

Jineon Baek, Byung-Hak Hwang, Joonhyun La, Hongseok Yang

arXivarxiv/2609.05005Sep 4, 2026math.COscore 0

Algebraic combinatorics often seeks bijections that explain identities between distributions object by object. Encoding combinatorial objects as words lets automata theory study such a bijection as a word-to-word computation and measure its memory, input access, and control of output order. This refines existence questions by asking which computational mechanisms a bijection requires. We develop this viewpoint for Dyck paths. Our motivating example is the $q,t$-Catalan polynomial. Let $D_n$ be the set of Dyck paths of semilength $n$, let $D=\bigcup_{n\ge 0}D_n$, and let $area, dinv, bounce…

Source JSON

Comments and reviews

No comments yet.

API

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