Papers

The square $G^2$ of a graph joins two vertices at distance at most two; a proper coloring of $G^2$ is a 2-distance coloring of $G$. For a cactus $G$ (every edge on at most one cycle) we determine both the 2-distance chromatic number $\chi(G^2)$ and the choice number $\mathrm{ch}(G^2)$ exactly: they are always equal, and the common value is $\Delta+1$ if $\Delta\ge4$, is 4 if $\Delta=3$ and $G$ has no block equal to $C_5$, is 5 if $\Delta=3$ and $G$ has a $C_5$ block, and is the classical value if $\Delta\le2$. For $\Delta\ge6$ the value $\Delta+1$ is already known, since cacti are outerplanar and hence $K_{2,3}$-minor-free (Hetherington-Woodall; Agnarsson-Halldorsson). Our contribution is the small-degree regime. For subcubic cacti we obtain a complete classification in both the ordinary and list settings, with the 5-cycle as the unique obstruction; the list statement has no prior analogue and is a genuine positive instance of the List Square Coloring Conjecture, which is false in general. A single elimination order then handles all $\Delta\ge4$ uniformly and, in particular, settles the two cases $\Delta\in\{4,5\}$ that the superclass bounds leave at $\Delta+2$. The number 5 turns out to be one obstruction wearing three disguises: $C_5^2=K_5$, the Frobenius number of $\{3,4\}$, and a degenerate $K_4$ list-coloring instance.

We resolve the two-colour three-component conjecture of Fernández, Pavez-Signé and Stein for random bipartite graphs. More precisely, we prove that if $G\sim G(n,n,p)$ and $p\gg\sqrt{\log n/n}$, then with high probability every red–blue edge-colouring of $G$ admits a cover of its vertex set by at most three monochromatic connected components. The proof is based on a uniform expansion lemma for unions of common neighbourhoods and an alternating common-neighbourhood expansion argument.

We develop a scalable approach to computing the magnitude homology Euler characteristic for directed acyclic graphs based on decategorification. Along with motivating mathematical results and some simple controlled examples, we deploy the Euler characteristic in a proof of concept application to the dynamic analysis of multilayer perceptrons, recovering class-discriminative structure while holding simpler subgraph properties fixed.

We define a coupling product and a draw coproduct on permutations and show that they define a graded, connected, cocommutative, free Hopf algebra $\mathbb{KS}$. In characteristic zero, this implies that $\mathbb{KS}$ is isomorphic to a certain cocommutative Hopf algebra associated with the dual of the coradical filtration of the Malvenuto–Reutenauer Hopf algebra on permutations. The coupling product and draw coproduct are permutation analogues of the product and coproduct on the monomial basis of symmetric functions; therefore, we can say that our presentation is a monomial basis for $\mathbb{KS}$.

We study the size of the largest monochromatic connected component that must appear in any edge-coloring of a random graph. Let $G\sim G(n,p)$ with $p\gg 1/n$ and $p=o(1)$, and write $np=he^h$. We show that, with high probability, every $2$-edge-coloring of $G$ contains a monochromatic connected component of order at least $n-\Theta(ne^{-h})$. Moreover, we construct colorings showing that this bound is best possible up to constant factors. We extend this result to three colors: for $p\gg 1/n$ and $p=o(1)$, with high probability every $3$-edge-coloring of $G$ contains a monochromatic connected component of size at least $\frac{n}{2}-\Theta(1/p)$, and this estimate is again tight up to constant factors. In the bipartite setting $G\sim G(n,n,p)$, under the same assumptions on $p$, we prove an analogous statement: with high probability, every $2$-edge-coloring contains two monochromatic components whose union covers all but $\Theta(ne^{-h})$ vertices, and this bound is asymptotically sharp. Our approach is elementary and is based on analyzing large connected structures across suitably balanced vertex partitions.

Let $H$ be a numerical monoid, that is, a cofinite submonoid of $\mathbb N$ (the non-negative integers under addition). Denote by $\mathcal P_{\text{fin},0}(H)$ the monoid obtained by endowing the family of all finite subsets of $H$ containing $0$ with the operation of setwise addition induced by $H$ on its power set. Tringali and Yan [JCTA, 2025] have recently established that $\mathcal P_{\text{fin},0}(\mathbb N)$ has a unique non-trivial automorphism, and conjectured that the automorphism group of $\mathcal P_{\text{fin},0}(H)$ is trivial whenever $H \ne \mathbb N$. We prove this conjecture and, as a byproduct, give a new proof of the Tringali–Yan theorem.

We introduce a new research area that is called Asymptotics Learning Theory (ALT) and combines optimization with asymptotic analysis. In particular, ALT provides a unified approach for computing unknown constants/parameters in proven asymptotic expansions using optimization theory. In this paper, we focus on a general asymptotic form which includes a broad class of asymptotics. Furthermore, we study two powerful numerical methods, namely, sliding Linear Least Squares (sLLSQ) and sliding Tikhonov Linear Least Squares (sT-LLSQ). For these techniques we rigorously prove asymptotic estimates that lead to sufficient conditions for convergence (to the correct values of unknown parameters) and convergence-rate guarantees. Despite their strengths, both methods have also limitations, e.g., slow convergence—or even, counterintuitively, divergence—in some cases. Moreover, we present fundamental applications in analytic combinatorics, a beautiful field of mathematics that deals with asymptotic enumeration of discrete structures using complex analysis. The proposed techniques complement existing approaches, such as the ratio method and its variants. Numerical examples also verify the theoretical results. Finally, we discuss interesting research directions in ALT.

Gallai proved that every graph can be partitioned into two sets, each inducing a subgraph with all degrees even. We show that if a graph admits a bipartition in which every vertex has an odd number of neighbors in the opposite part, then it can be partitioned into two sets, each inducing a subgraph with all degrees odd. Consequently, every $n$-vertex graph without isolated vertices has an induced subgraph with all degrees odd on at least $n/5$ vertices, substantially improving the previously known universal lower bound.

In 2007, Zagier identified twelve families of candidates for rank-three modular Nahm sums and established the modularity of three of them. The remaining cases were subsequently confirmed by Wang. Zagier's duality observation indicates that the Nahm sums associated with the duals of these examples might still be modular. We confirm that this is indeed true. The modularity of the dual of the sixth example was previously established by Milas and Wang, while that of the dual of the eleventh example was partially established by the present authors. We settle all remaining cases, thereby establishing the modularity of every defined dual in Zagier's rank-three list. We achieve this by proving new Rogers–Ramanujan type identities that express the relevant Nahm sums as finite sums of infinite products. Along the way we discover two new families of rank-three Nahm sums. As applications, we prove some Nahm sum identities conjectured by Cao–Wang, Li and the present authors.

Infinite Canons is an ongoing series of canons with infinite solutions. More specifically, each canon is based on a melodic line that can be combined in any number of voices, at any tempo ratios (rational or irrational), and with each voice moving either forward or in retrograde inversion, while maintaining harmonic consistency. This paper describes the structure of these maximally self-similar melodic lines based on two different constructions: 1) a discrete prime-factorization approach yielding self-similarity under all rational ratios, and 2) a continuous logarithmic approach extending this to irrational ratios. In both cases the vertical interval between voices in a tempo ratio of $\lambda_i / \lambda_j$ is given by a homomorphism $\phi(\lambda_i / \lambda_j)$, which is a constant independent of time. Furthermore, under these constructions retrograde inversion collapses to transposition, allowing for all manner of table canons. These structures are demonstrated with suggestive realizations of several different infinite canons. Future work includes a more complete mathematical treatment, musical applications, and an interactive program that allows users to explore an unlimited number of realizations of these pieces.

Consider the tree obtained by attaching a leaf to the third vertex of a path with n-1 vertices. In this note, we prove that the characteristic polynomial of this tree is irreducible when n belongs to certain arithmetic progressions modulo 30. As a result there are infinitely many pairwise non-isomorphic trees with an irreducible the characteristic polynomial. Our proof combines several number-theoretic arguments with a result of Gross, Hironaka, and McMullen [GHM09] concerning the cyclotomic factors of the Coxeter polynomials associated with the diagrams En. This resolves affirmatively a conjecture of Akbari, Kumar, Mohar and Pragada.

The square of a graph $G$ is the graph obtained from $G$ after adding an edge between any two vertices of distance $2$. A $k$-irregular graph is a graph with maximum degree $k$ such that vertices of degree $k$ are not adjacent. A list assignment of a graph is a function $L$ that assigns to each vertex a list of permissible colors. The graph is said to be \textit{$L$-colorable} if there exists a proper coloring $f$ such that $f(v) \in L(v)$ for every vertex $v$. A graph $G$ is called \textit{$k$-choosable} if it is $L$-colorable for every list assignment where each list has exactly $k$ colors. The list chromatic number of $G$, denoted by $\chi_l(G)$, is the smallest integer $k$ for which $G$ is $k$-choosable. Cranston and Kim \cite{ck} showed that $\chi_l(G^2) \leq 8$ for all subcubic graphs except the Petersen Graph. Moreover, Cranston and Kim \cite{ck} conjectured that for graphs with maximum degree $k$ and maximum clique size $w (G^2)\leq k^2-1$, we have $\chi_l(G^2) \leq k^2-1$. We prove that for a 4-irregular graph $G$, we have $\chi_l(G^2) \leq 11$. Moreover, we provide an example to show that this bound is sharp.

Two general estimates govern the rank of an $h$-scattered $q$-system: the scattered upper bound and the lower bound for systems maximal under inclusion. We determine exactly when they coincide. Besides $m=h+1$ and $m=h+2$, equality occurs precisely when $h$ is even, $m=h+3$, and $k\equiv h/2\pmod{h+1}$. We also prove rigidity in the first two cases: every extremal system is equivalent to either $\mathbb{F}_q^k$ or a direct sum of elementary Gabidulin systems and $\mathbb{F}_q$-directions. For $h=m-3$ and $k=\ell(m-2)+s$, with $1\leq s<(m-2)/2$, the two bounds differ by one, apart from one boundary case. Starting from an arbitrary maximum scattered $q$-system, we construct extremal quasi-maximum $(m-3)$-scattered systems of rank $\ell m+s$. Every such extension preserves lower bounds on the generalized rank weights of the initial code. When an explicit independence condition holds, the construction also produces a nondegenerate dual pair of quasi-MRD codes. We parametrize these extensions by subspaces of a quotient space and derive a uniform lower bound on the number of inequivalent outputs. Known order-two families yield codes separated from every nontrivial direct sum under an explicit numerical condition, while higher-order families are separated from a specified order-one direct-sum class. We conclude with a fully explicit binary example.

A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. A graph is $k$-degenerate if each of its subgraphs contains a vertex of degree at most $k$. It was known that every 1-planar graph is 8-choosable. In this paper, we show that every 1-planar graph without 6-cycles is 5-degenerate and hence 6-choosable.

A $k$-majority tournament on a finite vertex set is defined by $2k-1$ linear orders, with $u\to v$ when $u$ lies above $v$ in at least $k$ of the orders. Let $F(k)$ be the maximum, over all $k$-majority tournaments, of the size of a minimum dominating set. Alon, Brightwell, Kierstead, Kostochka, and Winkler proved that $C_1k/\log k \leq F(k) \leq C_2k\log k$ for suitable positive constants $C_1$ and $C_2$. In this paper, we prove the linear lower bound $F(k)\ge \left\lfloor\frac{k+1}{2}\right\rfloor $ for $k\ge 3$.

For North-East lattice paths (which we simply call lattice paths), we define intersection in terms of common edges. We prove that a family of paths from $(0,0)$ to $(n,n)$ in which every two distinct paths have an even number of common edges has size at most $2^n$, and that this bound is attained. If $M_{\mathrm{odd}}(n)$ denotes the maximum size of a family in which every two distinct paths have an odd number of common edges, then we prove \[ M_{\mathrm{odd}}(n)\le n(n-1)+1 \] and construct families showing that $M_{\mathrm{odd}}(n)=\Theta(n^2)$. Finally, we construct at least $C_n$ distinct extremal even-intersecting families, where $C_n$ is the $n$th Catalan number, and conjecture that these are all the extremal families.

A numerical semigroup is a subset of the nonnegative integers, closed under addition and with finite complement. The size of the complement is its genus. The problem of counting semigroups by the largest gap got very important through the so-called Frobenius problem, first documented in 1884. Accordingly, the largest gap is called the Frobenius number. In the last two decades, counting by the genus has become a subject of even more intense study, mostly because of the non-solved conjectures on its monotonic and super-Fibonacci growth. We propose a new approach to counting semigroups by the Frobenius number and by the genus, by introducing two ad-hoc trees. Those are leaf-discriminating trees in the sense that their leaves correspond exactly to the objects we want to count and, so, exploring these trees is optimal. On the theoretical side, it is known that the number of semigroups of each genus grows asymptotically with the genus as the Fibonacci numbers and that the number of semigroups of each Frobenius number grows asymptotically as a two-step doubling sequence. We prove a formula for the number of numerical semigroups of each Frobenius number $F$, genus $g$, and multiplicity $m$ (first nonzero nongap), for $m\geq(F+1)/3$. It is known that asymptotically almost all semigroups satisfy this inequality. This formula gives a multiparameter exact version of the increasing behaviours just mentioned. On the computational side, we implemented a recursive descending algorithm based on the so-called seeds structure, trimming the general semigroup tree exactly at those nodes with no descendants with a given genus, in the first case, or with no descendants with a given Frobenius number, in the second case. We refined the parallelizing strategies and we overcame the previous limitation of the length of integers in the bitwise representation of the gap sequence and the seed sequence.

In this paper, by the method of comparing coefficients, we establish a new generating function of multivariable Al-Salam-Carlitz polynomials which contains both Rogers' and Bowman's symmetirc expansion formulas and the classical $q$-Mehler formula as special cases. Some new $q$-series identities related to the multivariable Al-Salam-Carlitz polynomials are also presented.

We determine both the excluded vertex-minors and the excluded pivot-minors for the class of graphs of rank-width at most two. Up to local equivalence and graph isomorphism, there are exactly 25 excluded vertex-minors: 1 graph on 8 vertices, 18 on 9 vertices, and 6 on 10 vertices. Up to pivot equivalence and graph isomorphism, there are exactly 609 excluded pivot-minors: 2 on 8 vertices, 447 on 9 vertices, 146 on 10 vertices, 10 on 11 vertices, and 4 on 12 vertices. No excluded vertex-minor occurs on 11–16 vertices, and no excluded pivot-minor occurs on 13–16 vertices; the author's 16-vertex bound makes both lists complete. The proof is computer-assisted. Instead of enumerating all graphs, we reverse the one-vertex reduction theorem for prime graphs. For each $n$, we retain exactly the prime $n$-vertex graphs of rank-width at most two, modulo local equivalence and isomorphism, and extend those graphs by one vertex. Local-equivalence classes are identified by an exact canonical key obtained from the associated isotropic system, the binary row space of $[I\mid A(G)]$. A restricted version of the same key classifies pivot equivalence exactly. The vertex-minor and pivot-minor computations examine, respectively, more than $9.0\times 10^{10}$ and $4.9\times 10^{11}$ prime extensions in their 16-vertex final layers.

For a simple graph $G$ of order $n$, let $S_2(G)=\lambda_1(G)+\lambda_2(G)$ denote its spectral sum. We determine, for every $n\geq5$, the exact maximum of $S_2(G)$ and all equality cases. The unique maximizer, up to isomorphism, is the complement of the disjoint union of a suitably balanced complete bipartite graph and isolated vertices, with the sizes of its three parts determined by $n$ modulo $7$. Denoting this graph by $K_n^\star$, we further show that $ S_2(K_n^\star)\leq\frac{8n}{7}-2,$ with equality exactly when $7\mid n$. This proves a conjecture of Kumar, Liu, Monterde, Pragada and Tait, which strengthens the Aouchiche–Hansen 2010 conjecture by extending it from connected graphs to all graphs and by asserting uniqueness of the extremal graph. The result also subsumes the 2008 conjecture of Ebrahimi B., Mohar, Nikiforov, and Ahmady. The proof combines Ky Fan's variational principle with a spectral inequality for weighted Ferrers quotients to reduce the problem to an explicit family whose complements have incidence rank one. Exact integer optimization and a separate equality analysis then yield the maximum and uniqueness.

Given a numerical semigroup $S$ and a positive integer $p$, the quotient $\frac{S}{p}=\{n\in \mathbb{N} \mid pn\in S\}$ also forms a numerical semigroup. When $S=\langle a,b\rangle$ with $\gcd(a,b)=1$, a well-known open problem is to find a closed-form formula for the Frobenius number $g\!\left(\frac{\langle a,b\rangle}{p}\right)$, which remains open even in the special case $b=a+1$. Inspired by Curtis's theorem on the non-existence of polynomial formulas for the Frobenius number $g(\langle s_1,s_2,s_3\rangle)$, we provide a negative answer to this open problem in a certain sense. Concretely, we obtain the following three main results. (i): The Frobenius number $g\!\left(\frac{\langle a,b\rangle}{p}\right)$ cannot be represented, uniformly in $a,b,p$, by any finite collection of polynomial (or rational) formulas. (ii): For each fixed $p$, the function $a\mapsto g\!\left(\frac{\langle a,a+1\rangle}{p}\right)$ is a quadratic quasi-polynomial with period dividing $p$. (iii): There is no nonzero polynomial $F\in \mathbb{C}[X_1,X_2,X_3]$ satisfying $F\left(a,p,g\!\left(\frac{\langle a,a+1\rangle}{p}\right)\right)=0$ for all primes $a,p$ with $2<p<a$; the same conclusion already holds if only $p$ is required to be prime and $a$ ranges over all integers greater than $p$. While (iii) is stronger than (i), the proofs of the two results reveal different insights. Dirichlet's theorem on primes in arithmetic progressions plays a crucial role in our arguments.

The necessary and sufficient conditions for the Moran-type measures generated by two-element and three-element digit sets to be spectral have been given. The main result indicates that the spectrality of such a Moran-type measure is completely determined by the number of 2-factors and 3-factors in the zero set of the Fourier transform of each term in the convolution. The proof shows that, without the existence of Hadamard triples, the problem becomes much more complicated and difficult than the case with the existence of Hadamard triples.

Let $t(N)$ be the largest $t$ for which there exist distinct sets $A_1,\dots,A_t \subseteq \{1,\dots,N\}$ such that $A_i \cap A_j$ is a nonempty arithmetic progression for all $i \neq j$ (Erdos Problem #272). Simonovits and Sos proved $t(N)=O(N^2)$ and conjectured $\binom{N}{2}+1$ is best possible; Szabo disproved this by a construction giving $t(N) \geq \binom{N}{2}+1+\lfloor(N-1)/4\rfloor$, proved the asymptotics $t(N)=N^2/2+O(N^{5/3}(\log N)^3)$, and asked whether $t(N)=\binom{N}{2}+O(N)$ and whether some element lies in all sets of any extremal family (the kernel question). We determine $t(N)$ exactly for all $3 \leq N \leq 12$ by exhaustive computation: in this entire range Szabo's lower bound is exact, and we conjecture that $t(N)=\binom{N}{2}+1+\lfloor(N-1)/4\rfloor$ for every $N$. Towards the matching upper bound we prove, for every $N$, that Szabo's bound is the exact maximum over all families with a common element (starred families). The proof combines a self-contained “defect-one” counting inequality for staircase regions with a new structural theorem: every non-progression member of such a family contains a bad pair that no other member can share. Consequently the sharpened conjecture reduces to a single remaining statement, namely Szabo's kernel conjecture that some element lies in all sets of an extremal family, and we prove first structural constraints on putative non-starred extremal families.

We give a new proof of Maurer's homotopy theorem for matroids using polyhedral methods, in contrast to Maurer's original combinatorial proof. The same polyhedral approach yields a homotopy theorem for delta-matroids, from which the corresponding results for matroids, even delta-matroids, and antisymmetric matroids follow. We further prove an analogous theorem for integral polymatroids.

In Problem 6 of his 1988 paper on differential posets, Stanley asked for the least possible cardinality of a fixed rank of an $r$-differential poset and suggested that the minimum should be attained by $Y^r$, the $r$-fold Cartesian power of Young's lattice. We disprove the resulting universal coefficientwise lower bound. For every $r\geq 3$, we construct an infinite $r$-differential poset $P^{(r)}$ satisfying $\lvert P^{(r)}_4\rvert=\lvert (Y^r)_4\rvert-\lfloor r/3\rfloor$. For $r=3$, the construction replaces thirteen rank-four lower-cover blocks of $Y^3$ by twelve blocks with the same point and pair incidence multiplicities, producing the initial rank sequence $1,3,9,22,50$ instead of $1,3,9,22,51$. A reflection extension then yields an infinite differential poset. The construction does not address the cases $r=1$ and $r=2$.

We develop a mesoscopic framework for analyzing perturbations of finite point sets. Given a reference node set $Y$ with known cubature and approximation properties, we consider a disordered node set $Q$ that is observed only through its populations in cubes at scale $r>0$. By imposing Hall-type (HT) combinatorial constraints on these populations, we prove the existence of a perfect matching between $Y$ and $Q$ with $O(r)$ range. This allows integral approximation estimates on coarser cubes at scale $h>r$ to be transferred from $Y$ to $Q$ with explicit error control and anchors $Q$ to a periodic grid. We then use translation-invariant quasi-interpolation methods to obtain high-order estimates of order $h^s$ as in the quasi-uniform setting, but for a different class of geometries. The key restrictions are the HT conditions and the bound $r\le Ch$, where $C<1$ is scale independent.

External difference families (EDFs) are closely related to algebraic manipulation detection (AMD) codes, a cryptographic primitive that protects messages against additive tampering by an adversary who cannot observe the transmitted codeword. We first study a cyclotomic construction of external partial difference families over finite fields and derive a necessary and sufficient condition under which the resulting families are EDFs. For even block sizes up to $14$, we obtain explicit criteria in terms of quadratic and biquadratic residues, yielding new $R$-optimal weak AMD codes. We then construct bounded generalized strong external difference families using cyclotomic classes over finite fields, direct products of finite fields, and generalized cyclotomic classes over integer residue rings. These constructions give infinite families of systematic $G$-optimal strong AMD codes with flexible parameters.

We study the problem of constructing the nearest graph Laplacian matrix to a given Laplacian while enforcing a prescribed connected-component structure. Let the vertex set be partitioned into nonempty disjoint blocks $C_1,\ldots,C_k$, and let $U=[u_1,\ldots,u_k]$ be the matrix of the corresponding block-indicator vectors. The constraint $MU=0$ ensures that these prescribed indicators lie in the nullspace of the optimized Laplacian $M^\star$, and hence the associated graph has at least $k$ connected components. To guarantee exactly the prescribed components, we impose additional block-connectivity constraints on the principal blocks $M_j=M[C_j,C_j]$. These constraints ensure that each prescribed block induces a connected weighted subgraph. The resulting problem is a convex semidefinite optimization problem with a strictly convex Frobenius-norm objective. We prove existence and uniqueness of the minimizer and show that the optimized Laplacian has exactly the prescribed connected components, with nullspace $\operatorname{span}\{u_1,\ldots,u_k\}$. The framework proposed in this work provides a principled tool for quantifying the minimum structural intervention required to transform a graph-based network into one having a prescribed group-separated structure. Numerical examples, including the Sampson monastery positive-affection network, illustrate the nearest faction-consistent weighted reconstruction and the minimum Laplacian perturbation required to realize the prescribed faction structure.

The permanent rank of a matrix $A$ is the size of the maximal square submatrix in $A$ which has a nonzero permanent. In this paper we characterize additive transformations $\Phi$ which preserve matrices of per-rank-one. Under an additional assumption that $\Phi$ is surjective or that it preserves per-rank-one in both directions we prove that $\Phi$ is a composition of a multiplication with diagonal matrices and permutation matrices from both sides, transposition, and injective endomorphism of the base field.

We study the combinatorial structure of parity sequences associated with the accelerated Collatz map with the goal of identifying extremal configurations and relating them to the existence of periodic orbits. To each finite sequence of an orbit, we associate a binary word whose ones encode the odd iterates, and we introduce a functional $C(d)$ on such words which provides an explicit expression for the iterates and characterizes possible periodic cycles. We define a natural rotation action on binary words, compatible with the cyclic structure of periodic orbits, and consider the functional $C_{\min}(d)$ as a canonical representative of each rotation class. In this setting, we formulate and solve a discrete optimization problem on the set of binary words of fixed length and prescribed density. We prove that Christoffel words are, up to rotation, the unique maximizers of $C_{\min}(d)$ on $D_{N,r}$, the set of binary words of length $N$ with exactly $r$ ones, thereby establishing a direct connection between the dynamics of the Collatz problem and the classical theory of balanced words. As a consequence, we obtain restrictions on the possible existence of nontrivial cycles and derive explicit bounds for the minimum element of an orbit in terms of its length and the proportion of odd iterates. These results show that the combinatorial structure of parity sequences imposes strong constraints on Collatz dynamics and suggest that extremal configurations are governed by classical objects from the combinatorics on words, exhibiting a pronounced structural rigidity.