Sensitivity of Mixing Times of the Eulerian Functional Digraphs of the Full Transformation Semigroup T n

Abstract

Let X n = { 1 , 2 , ⋯ , n } and let T n denote the full transformation semigroup of all n n maps α : X n → X n . Each α ∈ T n induces a functional digraph Γ α whose vertex set is X n and whose arc set is { ( x , α ( x ) ) : x ∈ X n } . Because every vertex has out-degree exactly one, Γ α belongs to the class of functional ( mapping ) digraphs . The Eulerian members of this class are precisely the functional digraphs induced by permutations α ∈ S n ⊂ T n : there are n ! Eulerian functional digraphs on X n , and their isomorphism classes are in bijection with the integer partitions of n . A functional digraph is connected (strongly connected) if and only if α is a single n -cycle; there are ( n − 1 ) ! such digraphs, forming a single isomorphism class. This paper studies lazy simple random walks on connected Eulerian functional digraphs of T n from the perspective of quantitative mixing theory. Our main results are as follows: 1) Γ α is Eulerian if and only if α ∈ S n . The number of Eulerian functional digraphs on X n is n ! , with p ( n ) isomorphism classes (one per integer partition of n ), of which exactly one class (the directed n -cycle) is connected. 2) For the connected case ( α an n -cycle), the uniform mixing time satisfies c n 2 ≤ t u n i f ≤ C n 2 for absolute constants c , C > 0 . 3) For the Eulerian directed graph F n on n + 1 vertices formed by gluing two directed n / 2 -cycles at a common vertex (a natural object associated with permutations of cycle type ( n / 2 , n / 2 ) in S n , though not itself a functional digraph), modifying the laziness parameter on a fraction of vertices from 1/2 to p * = 2 / ( 5 + 1 ) reduces t m i x from Θ ( n 2 ) to Θ ( n 3 / 2 ) . 4) For the k -exploration time T k (first time k distinct vertices are visited) on a connected Eulerian functional digraph, E v [ T k ] = O ( k 2 ) . The proofs combine the spectral-profile technique, local central limit theorems, Diophantine approximation via the three-distance theorem, and the cycle structure of S n .