Narrow Results

We consider the problem of partitioning effectively a given irreflexive (and possibly symmetric) rational relation $R$ into two asymmetric rational relations. This problem is motivated by a recent method of embedding an $R$-independent language into one that is maximal $R$-independent, where the method requires to use an asymmetric partition of $R$. We solve the problem when $R$ is length-separable, which means that the following two subsets of $R$ are rational: the subset of word pairs $(u,v)$ where $\left|u\right|\le \left|v\right|$; and the subset of word pairs $(u,v)$ where $\left|u\right|\ge \left|v\right|$. This property is satisfied by all recognizable, all left synchronous, and all right synchronous relations. We leave it as an open problem when $R$ is not length-separable. We also define zero-avoiding transducers for length-separable relations, which makes our partitioning solution constructive.

For a directed graph G, we generalize the Catalan numbers by using the canonical generating partial isometries of the Cuntz–Krieger algebra for the transition matrix A^G of the directed edges of G. The generalized Catalan numbers enumerate the number of Dyck paths for the graph G. Its generating functions will be studied.

Dyck path categories are introduced as a combinatorial model of the category of representations of quivers of Dynkin-type ${𝔸}_n$. In particular, it is proved that there is a bijection between some Dyck paths and perfect matchings of some snake graphs. The approach allows us to give formulas for cluster variables in cluster algebras of Dynkin-type ${𝔸}_n$ in terms of Dyck paths.

We prove evaluations of Hankel determinants of linear combinations of moments of orthogonal polynomials (or, equivalently, of generating functions for Motzkin paths), thus generalizing known results for Catalan numbers.

A dispersed Dyck path (DDP) of length $n$ is a lattice path on $\mathbb{N}\times \mathbb{N}$ from $(0,0)$ to $(n,0)$ in which the following steps are allowed: “up” $(x,y)\to (x+1,y+1)$; “down” $(x,y)\to (x+1,y-1)$; and “right” $(x,0)\to (x+1,0)$. An ascent in a DDP is an inclusion-wise maximal sequence of consecutive up steps. A 1-ascent is an ascent consisting of exactly 1 up step.

We give a closed formula for the total number of 1-ascents in all dispersed Dyck paths of length $n$, #A191386 in Sloane’s OEIS. Previously, only implicit generating function relations and asymptotics were known.

We consider a Wigner-type ensemble, i.e. large hermitian $N\times N$ random matrices $H=H^{\ast }$ with centered independent entries and with a general matrix of variances $S_{xy}=𝔼|H_{xy}{|}^2$. The norm of $H$ is asymptotically given by the maximum of the support of the self-consistent density of states. We establish a bound on this maximum in terms of norms of powers of $S$ that substantially improves the earlier bound $2\parallel S{\parallel }_{\infty }^{1/2}$ given in [O. Ajanki, L. Erdős and T. Krüger, Universality for general Wigner-type matrices, Prob. Theor. Rel. Fields 169 (2017) 667–727]. The key element of the proof is an effective Markov chain approximation for the contributions of the weighted Dyck paths appearing in the iterative solution of the corresponding Dyson equation.

We prove evaluations of Hankel determinants of linear combinations of moments of orthogonal polynomials (or, equivalently, of generating functions for Motzkin paths), thus generalizing known results for Catalan numbers.

Frustration-free (FF) spin chains have a property that their ground state minimizes all individual terms in the chain Hamiltonian. We ask how entangled can the ground state of a FF quantum spin-s chain with nearest-neighbor interactions be for small values of s. While FF spin-1/2 chains are known to have unentangled ground states, the case s = 1 remains less explored. We propose the first example of a FF translation-invariant spin-1 chain that has a unique highly entangled ground state and exhibits some signatures of a critical behavior. The ground state can be viewed as the uniform superposition of balanced strings of left and right parentheses separated by empty spaces. Entanglement entropy of one half of the chain scales as ½ log (n) + O(1), where n is the number of spins. We prove that the energy gap above the ground state is polynomial in 1/n. The proof relies on a new result concerning statistics of Dyck paths which might be of independent interest.

Note from Publisher: This article contains the abstract only.