TITLE:
Sensitivity of Mixing Times of the Eulerian Functional Digraphs of the Full Transformation Semigroup Tn
AUTHORS:
Imelda Elohor Agbedo, Ophokpokpo Matthew Salami, Ojiyovwi Rhoda Osanakpa, Oluranran Clinton Kayoh, Ifeanyi Jeff Ugbene
KEYWORDS:
Full Transformation Semigroup, Functional Digraph, Eulerian Digraph, Lazy Random Walk, Mixing Time, Sensitivity, Spectral Profile, Exploration Time, Three-Distance Theorem
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.16 No.3,
July
22,
2026
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
unif
≤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
mix
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
.