CS Paper Radar

Cycle Counting and Character Expectations Using Alternating Structures

Noam Ta Shma

cs.FL math.GR ·submitted 2026-08-27 18:26 UTC · v1
theory

Abstract

Recently, two related papers [arXiv:2412.13941, arXiv:2409.03626] found a connection between two subjects: the w-cycle theorem, which is a theorem about counting appearances of cycles reading out a word w in certain graphs, and character expectations on word measures. The w-cycle theorem was proven independently by [arXiv:1410.2540] using stackings and by [arXiv:1410.2579] using bislim structures. In the current work, we generalize stackings and bislim structures to alternating stackings and alternating bislim structures. We show how this significantly strengthens the w-cycle theorem for words admitting such alternating structures, and as a result, also strengthens the recent results of [arXiv:2412.13941] and [arXiv:2409.03626]. We show that generic words admit alternating bislim structures, and therefore, the strengthened results hold for generic words. Using our new machinery, we address conjectures of Wilton, of Hanany-Puder and of Puder-Shomroni. We prove that all three conjectures hold for generic words, but we also find counterexamples for the first two.

Comment
59 pages, 22 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Every Regular Language Has a Bipartite Cactus Automaton

cs.FL ·2026-10-08 ·Mario Grobler, Till Koziel, Sebastian Siebertz
published similarity 0.58
Abstract · In Proceedings GandALF 2026, arXiv:2610.08898

Thompson's classical construction turns every regular expression into an equivalent epsilon-NFA whose transition graph is series-parallel. The construction uses epsilon-transitions, and eliminating them by the usual shortcut construction need not preserve planarity or the bound of two on the treewidth of the transition graph. Book and Chandra proved that every regular language nevertheless has an epsilon-free NFA with a planar transition graph. We show that the transition graph can in fact be chosen to be a bipartite cactus: every cycle is even, and any two cycles have at most one vertex in common. In particular, it is outerplanar and has treewidth at most two. This is a considerably more simple structure than the general series-parallel guarantee supplied by Thompson's construction. The proof is a direct induction on parity-typed regular expressions and uses only elementary closure properties of cactus graphs.

0.32

Crown graphs maximise the representation number of bipartite graphs

cs.DM math.CO ·2026-09-24 ·Matthew J. Colbrook, Catherine Drysdale
theory similarity 0.57
Abstract

The representation number of a graph is the least positive integer $k$ for which its vertices can be arranged in a word, each occurring $k$ times, so that two distinct letters alternate precisely when the corresponding vertices are adjacent. We prove that every bipartite graph on $N\ge9$ vertices has representation number at most $\lceil N/4\rceil$. Together with the known representation number of crown graphs, this settles the conjecture that crowns maximise the representation number among bipartite graphs of the same order. The proof develops a construction of Mozhui and Krishna by reducing the choice of a representing word to an ordering problem for neighbourhoods. We characterise the obstructions to this ordering and use probability estimates to exclude them for all sufficiently large balanced bipartitions. Two finite assertions complete the argument, each established by a checked Boolean unsatisfiability certificate. A refinement of the ordering argument treats the remaining odd part sizes directly. The main theorem and the crown-extremality corollary, including the finite certificate arguments, have also been formalised and verified in Lean 4.

0.25

Shuffle squares in smooth binary words and the Kolakoski sequence

cs.FL math.CO ·2026-10-01 ·Kory Kilpatrick
similarity 0.57
Abstract · Includes an exact finite certificate and standalone Python verifier. Research, computation, and writing performed by GPT-5.6 Sol and GPT-6-A…

A binary word is a shuffle square if its positions can be partitioned into two identical subsequences. A finite word over $\{1,2\}$ is smooth if repeated finite run-length differentiation remains binary until the empty word is reached. This paper proves that every smooth binary word in which both letters have even multiplicity is a shuffle square once its length is at least $18$. There are exactly $34$ exceptions, all of length at most $16$. The infinite part of the proof is a parity-return atom induction: a smooth even-Parikh word factors uniquely into smooth parity atoms, and every such atom has length at most $8$. A finite, independently checkable certificate handles lengths $18$ through $40$. As a consequence, a nonempty prefix of the classical Kolakoski sequence is a shuffle square if and only if both symbols occur an even number of times and its length is not $4$ or $8$. There are infinitely many such prefixes. In fact, the entire infinite Kolakoski sequence can be partitioned into two identical infinite subsequences with monochromatic blocks of uniformly bounded length.

0.54

Subsequence Analysis Problems for Binary Parikh Matrices

cs.FL cs.CC ·2026-10-05 ·Szilárd Zsolt Fazekas, Xinhao Huang, Robert Mercaş
publishedtheory similarity 0.57
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

The universality index corresponding to a word is the largest integer k such that every word of length k over the given alphabet occurs in it as a subsequence. Relative to languages this notion can be investigated with respect to both existential and universal quantifiers, with the former corresponding to the existence of a word in the language with universality index at least k, while the latter considers the index across all words that the language contains. In this work we study the existential (exists-universality) and universal (forall-universality) subsequence universality (as introduced in [Adamson et al., ISAAC 2023]) for binary languages consisting of all words with a fixed number of letters a, letters b, and subsequences ab. We prove that both exists- and forall-universality admit exact arithmetic characterizations for these languages. Extending the above notions, we end the paper by initiating the analysis of the probability of a fixed word occurring as subsequence of the words in such a language. To this end, we prove that, for every fixed pattern word w and an error tolerance, given as input the subsequence counts describing a language, the ratio of words in the language having the pattern w as a subsequence admits an additive approximation scheme that is polynomial-time in the binary encoding of the input counts.

0.49

The lattice of antichains of intervals: Dyck paths, level sets, and sweep dimension

cs.DM math.CO ·2026-10-30 ·Paolo Boldi, Sebastiano Vigna
theory similarity 0.55
Abstract

The Clarke-Cormack-Burkowski lattice $\mathcal{E}_n$ is the lattice of antichains of intervals of the chain $\{0,1,\dots,n-1\}$, the algebraic structure underlying minimal-interval semantics, a query semantics used in information retrieval. We give an explicit, elementary anti-isomorphism between $\mathcal{E}_n$ minus its top element and the Stanley lattice of Dyck words of semilength $n+1$ (an anti-isomorphism whose existence is implicit in work of Ferrari and Munarini), under which the rank of an antichain is $\binom{n+1}{2}$ minus the area of the associated Dyck word. Hence the rank generating function of $\mathcal{E}_n\setminus\{\top\}$ is the reverse of the Carlitz-Riordan $q$-Catalan polynomial. Using a local limit theorem for the area of random-walk excursions, we confirm unconditionally an asymptotic formula of Takács: the size $λ_n$ of the largest level set of $\mathcal{E}_n$ satisfies $λ_n\simκ\,4^{n+1}/(n+1)^3$, where $κ\approx1.0807$. Finally, for the antichains of intervals of an arbitrary finite poset $P$ we study the sweep dimension, the minimum number of linear orders needed to separate every interval from every element outside it. It equals the Dushnik-Miller dimension of the lattice of convex subsets of $P$, it is the least $k$ for which $P$ maps into $\mathbb{R}^k$ so that every interval is the preimage of an upper orthant, and it lies between $\max(2,w)$ and $2w$, where $w$ is the width of $P$, both bounds being tight. Antichains of intervals embed, preserving joins, into $k$-dimensional staircase regions.

0.13

Language-Representability: Possibilities and Limitations

cs.FL ·2026-08-25 ·Zhidan Feng, Henning Fernau, Pamela Fleischmann, Kevin Mann, Silas Cato Sacher
published similarity 0.55
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

The study of word-representability was initiated by the seminal work of Kitaev and Pyatkin in 2008 that has later led to the monograph by Kitaev and Lozin in 2015. In this paper, we build on the very recent work by Fernau et al. who proposed a general framework that generalizes certain aspects of word-representability, so that any binary language describes a graph class. In this work, we systematically study particularly small languages and observe that they characterize well-known graph classes, e.g., interval, permutation, circle, and bipartite chain graphs. Thus, we strengthen the bond between formal languages and graph classes, even for small binary languages. We also show some limitations of our approach by proving that, e.g., families of sparse graphs like planar graphs cannot be characterized by any language following this approach.

0.37

A generalized monoid of infinite words: asymptotic prefix-suffix quotients and algebraic structure

cs.FL math.GR ·2026-08-20 ·A. Alvarez Cruz, E. A. Alvarez Gutierrez
similarity 0.54
Abstract

A generalized monoid of words tilde{Sigma}* is constructed as the quotient of moderate nets of finite words by an asymptotic equivalence relation based on a bidirectional prefix-suffix metric. The main algebraic result is that this quotient is a monoid containing Sigma* faithfully, with a reversal involution, a natural divisibility preorder, failure of cancellation, and nontrivial idempotents. The construction is designed so that any functional depending only on a logarithmic prefix descends to the quotient, yielding a well-defined action of logarithmic-prefix functionals. Finite scalar values arise only after applying an additional renormalization functional, which depends on the chosen mould and window. With respect to the fixed truncation injection, the monoid strictly enlarges the classical set Sigma^{infty}: an explicit oscillating net is exhibited that has no limit in the Cantor space but defines a genuine element of tilde{Sigma}* not coming from a finite or right-infinite word under that injection.

0.50

Repetition Avoidance in Curling-Number Transforms

cs.DM math.COcs.FL ·2026-08-16 ·Geoffrey Caveney, Haoxuan, Dong, Jeffrey Shallit
similarity 0.54
Abstract

We study repetition avoidance in a word ${\bf w}$ and its curling-number transform $C({\bf w})$. For alphabets of sizes $2$, $3$, and $4$, we use Thue-Morse-based morphic constructions and exhaustive finite searches. A ternary word for which both ${\bf w}$ and $C({\bf w})$ are overlap-free has length at most $84$, whereas over four letters an infinite example exists. Hence $4$ is the smallest alphabet size admitting simultaneous infinite overlap-freeness. The infinite constructions are verified in Walnut; the finite maxima are obtained by exhaustive breadth-first search and checked independently.

0.04