So for recap, a transformation f: [n]→[n] is nonpermutational ([n] stands for the set {1,...,n} here) if f(X)=X implies |X|=1 for any nonempty subset X of [n].
(These guys are interesting now since a reduced automaton recognizes a definite language if and only if every nonempty word induces a nonpermutational transformation on the set of states, but it's not important for now.)
For example, f=(2,3,3) and g=(1,1,2) are nonpermutational (we write transformations of [n] also as vectors, the above f is defined as f(1)=2, f(2)=3 and f(3)=3), but their product fg = (1,2,2) is not since fg({1,2})={1,2}. Product here is function composition, i.e. fg(x)=g(f(x)). Sorry for the ordering: when f and g are words inducing some transformation on the state set of an automaton, then fg, the concatenation of f and g in this order induces a function that way: first we apply (i.e. "read") f, then g.
That's why we will write pf instead of f(p) for a p in [n].
Thinking a bit, the following are equivalent for a function f:[n]→[n]:
- f is nonpermutational;
- f k is constant for some k;
- the graph of f is a rooted tree with edges directed towards the root and with a loop attached to the root.
Here "the graph of f" is the one with vertex set [n] and p→q is an edge if and only if pf=q. Thus, each node has outdegree one. Since the graph is finite, this implies the existence of at least one cycle.
Clearly, since if f is any transformation of [n], then f(X)=X with X being the (nonempty) set of all nodes lying on some cycle. Thus if f is nonpermutational, then the above X has only one element, hence there is only one vertex lying on a cycle -- which has to be a loop then. Removing this loop we get a DAG (a directed acyclic graph), with each node but the originally looped one having outdegree one, showing 1) implies 3). Now 3) implies 2) since each application of f takes each vertex closed to the root and thus f n maps each vertex to the root. Finally, 2) implies 1) since if Xf=X, then Xf k=X as well. Since f k is by assumption a constant, X is a singleton, thus f is indeed nonpermutational.
In the following, when f is a nonpermutational transformation, Fix(f) denotes its unique fixed point.
We are interested in the following question: given n, how large can a semigroup of nonpermutational transformations of [n] be at most? Since the set of all nonpermutational functions do not form a semigroup, it's not that easy as counting all the nonpermutational functions but the answer is a hell less number.
Trivial bound: nn. It's the total number of transformations...
A slightly lower but still trivial bound: n(n-2). It's (by Cayley's formula) the number of rooted trees on the vertex set [n], so it's the total number of nonpermutational transformations. But, they do not form a semigroup...
A somewhat more carefully designed bound: n!. To see this, let S be a semigroup consisting of nonpermutational transformations only. Let Si, for i in [n], stand for the set of those members f of S with Fix(f)=i. Then each Si is also a semigroup (since if p is a fixed point of f and g, then it is the fixed point of fg as well). Now for i in [n], let us consider the graph Gi with vertices [n] and (p,q) being an edge iff pf=q for some f in Si. Observe that since Si is a semigroup, Gi is transitive (if f maps p to q and g maps q to r then fg maps p to r). Clearly i is a sink of Gi (there is a loop attached on i and no any other outgoing edges). Let's remove this loop and let Gi' stand for the resulting graph. Suppose there is a cycle in Gi'. Then by transitivity, there is a loop in Gi' as well (removing the loop from the sink does not affect transivity), implying that there is a function in Si having a fixed point different from i which is nonsense by definition of Si. Hence Gi' is a transitive DAG -- a strict partial ordering of [n] with maximal element i. Let < be an arbitrary linear extension of this partial order. Then any member f obeys p<pf for p<>i and if=i. The total number of such f's is (n-1)!: one can choose (n-1) different values for the first element, (n-2) for the second and so on. Thus, |Si| is at most (n-1)! and since S is the disjoint union of n such Si's we get the upper bound n(n-1)!=n!.
Next time we reduce this bound a bit by a horrible case analysis to get an upper bound n((n-1)!-(n-3)!)...
stay tuned
A slightly lower but still trivial bound: n(n-2). It's (by Cayley's formula) the number of rooted trees on the vertex set [n], so it's the total number of nonpermutational transformations. But, they do not form a semigroup...
A somewhat more carefully designed bound: n!. To see this, let S be a semigroup consisting of nonpermutational transformations only. Let Si, for i in [n], stand for the set of those members f of S with Fix(f)=i. Then each Si is also a semigroup (since if p is a fixed point of f and g, then it is the fixed point of fg as well). Now for i in [n], let us consider the graph Gi with vertices [n] and (p,q) being an edge iff pf=q for some f in Si. Observe that since Si is a semigroup, Gi is transitive (if f maps p to q and g maps q to r then fg maps p to r). Clearly i is a sink of Gi (there is a loop attached on i and no any other outgoing edges). Let's remove this loop and let Gi' stand for the resulting graph. Suppose there is a cycle in Gi'. Then by transitivity, there is a loop in Gi' as well (removing the loop from the sink does not affect transivity), implying that there is a function in Si having a fixed point different from i which is nonsense by definition of Si. Hence Gi' is a transitive DAG -- a strict partial ordering of [n] with maximal element i. Let < be an arbitrary linear extension of this partial order. Then any member f obeys p<pf for p<>i and if=i. The total number of such f's is (n-1)!: one can choose (n-1) different values for the first element, (n-2) for the second and so on. Thus, |Si| is at most (n-1)! and since S is the disjoint union of n such Si's we get the upper bound n(n-1)!=n!.
Next time we reduce this bound a bit by a horrible case analysis to get an upper bound n((n-1)!-(n-3)!)...
stay tuned
No comments:
Post a Comment