ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P4.09 / 649–674
https://doi.org/10.26493/1855-3974.1753.52a
(Also available at http://amc-journal.eu)
Top-heavy phenomena for transformations*
Yaokun Wu † , Yinfeng Zhu
School of Mathematical Sciences and MOE-LSC, Shanghai Jiao Tong University,
Shanghai 200240, China
Received 19 July 2018, accepted 5 February 2022, published online 19 August 2022
Abstract
Let S be a transformation semigroup acting on a set Ω. The action of S on Ω can be
naturally extended to be an action on all subsets of Ω. We say that S is ℓ-homogeneous
provided it can send A to B for any two (not necessarily distinct) ℓ-subsets A and B of Ω.
On the condition that k ≤ ℓ < k + ℓ ≤ |Ω|, we show that every ℓ-homogeneous transfor-
mation semigroup acting on Ω must be k-homogeneous. We report other variants of this
result for Boolean semirings and affine/projective geometries. In general, any semigroup
action on a poset gives rise to an automaton and we associate some sequences of integers
with the phase space of this automaton. When this poset is a geometric lattice, we pro-
pose to investigate various possible regularity properties of these sequences, especially the
so-called top-heavy property. In the course of this study, we are led to a conjecture about
the injectivity of the incidence operator of a geometric lattice, generalizing a conjecture of
Kung.
Keywords: Incidence operator, kernel space, rank, strong shape, valuated poset, weak shape.
Math. Subj. Class. (2020): 05B35, 20M20, 47D03, 52C35
1 Introduction
1.1 Transformation and phase space
Let Γ be a digraph, namely a pair consisting of its vertex set V(Γ) and arc set E(Γ) ⊆
V(Γ) × V(Γ). We call Γ symmetric if (u, v) ∈ E(Γ) holds if and only if so does (v, u) ∈
E(Γ). For any A ⊆ V(Γ), we adopt the notation Γ[A] for the subdigraph of Γ induced by
*We thank Peter Cameron, Alexander Ivanov, Peter Šemrl, Johannes Siemons and Qing Xiang for useful
discussions. Especially, Peter Šemrl reminded us the result of Taussky and Zassenhaus while Johannes Siemons
suggested that the isomorphism of two permutation modules can be read from Figure 6. This work has been
supported by NSFC (11971305, 11671258) and STCSM (17690740800).
†Corresponding author.
E-mail addresses: ykwu@sjtu.edu.cn (Yaokun Wu), fengzi@sjtu.edu.cn (Yinfeng Zhu)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
650 Ars Math. Contemp. 22 (2022) #P4.09 / 649–674
A which has vertex set A and arc set E(Γ) ∩ (A × A). The number of weakly connected
components and the number of strongly connected components of Γ will be dubbed wcc(Γ)
and scc(Γ), respectively.
For a set Ω, all maps from Ω to itself form the set ΩΩ. For each g ∈ ΩΩ and α ∈ Ω,
we write αg for the image of α under the map g. The composition of maps provides an
associative product on the set ΩΩ and thus turns it into a monoid, namely a semigroup with
a multiplicative unit. We call this monoid the full transformation monoid on Ω and denote
it by T(Ω). A subset of T(Ω) which is closed under map composition, whether or not it
contains the identity map on Ω, is called a transformation semigroup acting on Ω. Let S be
a transformation semigroup on Ω. We say that S is transitive on a set A ⊆ Ω if for every
α, β ∈ A we can find g ∈ S such that αg = β; we call S transitive if S is transitive on
Ω. If the transformation semigroup S is generated by a set G ⊆ ΩΩ, namely S consists
of products of elements of G of positive length, we call (S,G) a deterministic automaton
on Ω [67, Section 1]. The phase space of an automaton (S,G) on Ω, denoted by Γ(S,G),
is the digraph with vertex set Ω and arc set {(α, αg) : α ∈ Ω, g ∈ G}. When Ω has at
least two elements, the claim that S is transitive is equivalent to the claim that Γ(S,G) is
strongly connected for any generator setG of S. We write Γ(S, S) simply as Γ(S) and note
that each strongly/weakly connected component of Γ(S) coincides with a strongly/weakly
connected component of Γ(S,G) for any generator set G of S. For all work in this paper,
we can simply focus on Γ(S) instead of considering Γ(S,G) for any specific generator set
G. We emphasize Γ(S,G) from the phase space viewpoint here to highlight the connection
between semigroup theory and automata theory, and to indicate the role played by the
choice of G in some problems related to various distance functions on the phase space, say
the Černý conjecture. For any set Ω, a subset of T(Ω) forms a permutation group on Ω
whenever it is a transformation semigroup and each element has an inverse in it, namely
it is a set of bijective transformations of Ω and is closed under compositions and taking
inverses. Permutation groups correspond to reversible deterministic automata.
Let Ω be a set. We follow the common practice to use 2Ω for the power set of Ω. For
each g ∈ T(Ω), let g be the element in T(2Ω) that sends each A ∈ 2Ω to Ag .= {ag :
a ∈ A}. More generally, for each G ⊆ T(Ω), G refers to the set {g : g ∈ G}. For
any transformation semigroup S on Ω and any generator set G of S, S, as a semigroup
derived from S, is known to be the powerset transformation semigroup of S acting on 2Ω
and (S,G) is known to be the powerset automaton of (S,G). It may be interesting to iterate
the powerset automaton construction and examine the evolution of the phase spaces of the
resulting automata.
When discussing transformation semigroups, we may often be more interested in those
which preserve some structures, say simplicial maps for simplicial complexes, continuous
maps for topological spaces, ordering preserving maps for posets, or adjacency-preserving
maps in matrix geometry [52, 66]. Unlike the work on group actions on posets [3, 59]
and matroids [19], very little has been done on semigroup actions on these structures [62].
Moving from group actions to semigroup actions is just to consider general deterministic
automata instead of reversible ones.
1.2 Valuated poset and its shape
For any two sets Ω and Ψ, if they are different or if we do not emphasize that they may be
equal, the image of ω ∈ Ω under a map g ∈ ΨΩ is denoted g(ω); note that we often write
it as ωg when Ω = Ψ.
Y. Wu and Y. Zhu: Top-heavy phenomena for transformations 651
A poset P consists of a set Ω and a binary relation <P on it which is transitive and
acyclic, namely we require that α <P α never happens, and that α <P β and β <P γ
implies α <P γ for all α, β, γ ∈ Ω. We often just write P for its ground set Ω and we
say the poset P is finite if |P | is finite. For each α ∈ P , the principal ideal generated by
α is the set {β : β <P α} ∪ {α} ⊆ P , which we denote by P↓(α); the principal filter
generated by α is the set {β : α <P β} ∪ {α} ⊆ P , which we denote by P↑(α). An
ideal (filter) is a union of principal ideals (filters). A map g from a poset P to a poset Q
is order-preserving if g(β) ∈ Q↓(g(α)) holds whenever β ∈ P↓(α). We use End(P ) to
denote the set of all order-preserving maps from P to itself.
Let Z≥0 be the set of nonnegative integers which carries a natural poset structure such
that a < b in Z≥0 if and only if b − a is a positive integer. A valuation on a poset P is
an order-preserving map rP from P to the poset Z≥0; we call rP (x) the rank of x in the
valuated poset. When we say P is a valuated poset, we are considering the poset P together
with a valuation rP , though the valuation may be only implicitly indicated. The rank of a
valuated poset P , denoted by r(P ), is the maximum value of rP (α) for α ∈ P if it exists
and is ∞ otherwise. For a poset P , the symbols like <P and rP will often be abbreviated
to < and r when no confusion can arise. Let P be a valuated poset. For any k ∈ Z≥0, we
write Pk for the set {α ∈ P : r(α) = k}. We call the sequence |P0|, |P1|, . . . the shape of
the valuated poset and refer to it by S(P ). If r(P ) < ∞, S(P ) is a sequence of r(P ) + 1
nonnegative integers.
Let P be a valuated poset and let S be a subsemigroup of End(P ). The weak shape of
P under the action of S is the sequence
wcc(Γ(S)[P0]),wcc(Γ(S)[P1]), . . .
which we denote by WS(S, P ); while the strong shape of P under the action of S is the
sequence
scc(Γ(S)[P0]), scc(Γ(S)[P1]), . . .
which we denote by SS(S, P ). Note that
S(P ) = WS(S, P ) = SS(S, P )
when the semigroup S consists of the identity transformation from End(P ).
The main purpose of this note is to propose a study of the possible regularity in the
strong/weak shape of a semigroup acting on a valuated poset.
1.3 Geometric lattice and top-heavy property
A matroid M consists of a ground set EM and a rank function rM from 2EM to the set of
nonnegative integers plus infinity such that the rank axioms are satisfied [13, Section 1.5].
The flats of a matroid M , ordered by inclusion, form a very pretty structure, called the
matroid lattice of M and denoted by F(M). For each nonnegative integer t, let Ft(M)
be the set of all rank-t flats of the matroid M . A geometric lattice is an atomic and
semimodular lattice which does not have any infinite chain [64, page 305]. We mention
that a geometric lattice is cryptomorphic to a natural object called combinatorial geome-
try [64, Theorem 23.1] and that finite geometric lattice is nothing but finite matroid lattice
[36, page 163, Birkhoff’s Theorem]. A geometric/matroid lattice has a natural valuated
poset structure, where the valuation is given by its rank function. For example, for a ma-
troid M , all elements in Ft(M) have rank t. In a geometric lattice, the elements of rank 1,
652 Ars Math. Contemp. 22 (2022) #P4.09 / 649–674
2 and 3 are viewed as points, lines and planes, respectively, thus giving geometric intuitions
to many results about geometric lattices.
For each linear space V and each nonnegative integer k, we use Gr(k, V ) for the set
of all k-dimensional linear subspaces of V and we call
⋃∞
k=0 Gr(k, V ) the Grassmannian
of V , which is denoted by Gr(V ). If V is finite dimensional, Gr(V ) is surely a geometric
lattice with elements from Gr(k, V ) having rank k.
Example 1.1. Let n and k be two positive integers such that k < n. Fix a non-degenerate
inner product on Qn, say ⟨, ⟩. For each g ∈ GLn(Q), let g⊤ stand for the adjoint of g,
namely the element such that ⟨ug, v⟩ = ⟨u, vg⊤⟩ for all u, v ∈ Qn, and we write g#
for (g−1)⊤. Let S ≤ GLn(Q) be a matrix group acting on Qn. If S is transitive on
the set of all dimension-k subspaces and if g# ∈ S for all g ∈ S, then S is transitive
on the set of dimension-(n − k) subspaces. To see this, fix a pair of subspaces (U,U ′)
which are orthogonal complements to each other with respect to ⟨, ⟩ and (dimU,dimU ′) =
(k, n − k). For each g ∈ S, we can see that Ug and U ′g# are orthogonal complements
to each other with respect to the given inner product ⟨, ⟩. Considering the set of pairs
{(Ug, U ′g#) : g ∈ S}, we see that the transitivity on Gr(k,Qn) implies transitivity on
Gr(n− k,Qn).
Motivated by Example 1.1, here is a very simple question on the very simple geometric
lattice Gr(Q3). Surprisingly, we even could not find any discussion of it in the literature.
Question 1.2. If S is a general matrix group acting on Q3, can we draw the conclusion
that S is transitive on Gr(1,Q3) from the assumption of its transitivity on Gr(2,Q3)?
What about only assuming that S is a matrix semigroup?
Some seemingly weird properties of sequences turn out to be ubiquitous when we are
examining some interesting structures or processes [6, 10, 11, 29, 58, 61]. We review
some of them below. Let c0, c1, . . . , be a sequence of n+ 1 real numbers, where n can be
finite or infinite. We call it t-top-heavy if ck ≤ twhenever there exists an integer ℓ such that
k ≤ ℓ ≤ k+ℓ ≤ n and cℓ ≤ t; we call it top-heavy if it is t-top-heavy for all t ∈ R, namely
ck ≤ cℓ holds for all k, ℓ such that k ≤ ℓ ≤ k + ℓ ≤ n; We call it unimodal if you cannot
find three distinct integers i, j, k such that 0 ≤ i < j < k ≤ n and ci − cj > 0 > cj − ck;
we call it log-concave if c2i ≥ ci−1ci+1 for all i = 1, . . . , n − 1. When n is finite, we call
the sequence real-rooted provided the polynomial c0 + c1x + · · · + cnxn in the unknown
x only has real roots and we call it ultra-log-concave provided c0
(n0)
, . . . , cn
(nn)
forms a log-
concave sequence. Note that Question 1.2 is about the possible 1-top-heavy property of the
strong shape of Gr(Q3) under a matrix semigroup action.
In the 1970s, two log-concavity conjectures [61, Conjecture 3] appeared in combina-
torics community which claim that the sequences of Whitney numbers of both the first kind
and the second kind of a finite matroid are log-concave. The first conjecture was verified
by Adiprasito, Huh and Katz [1]. Mason [40] had made variants and stronger versions of
the second conjecture; but even the original conjecture is still open. Dowling and Wilson
[23] conjectured that the sequence of Whitney numbers of the second kind of a finite ma-
troid is top-heavy. When restricted to finite realizable matroids, this top-heavy conjecture
was proved by Huh and Wang [28]. The second log-concavity conjecture as described
above, which is about the Whitney numbers of the second kind [50], simply says that the
shape of every geometric lattice is log-concave. The above-mentioned Dowling-Wilson
top-heavy conjecture says that the shape of every finite geometric lattice is top-heavy. On
Y. Wu and Y. Zhu: Top-heavy phenomena for transformations 653
the condition that these two conjectures are both true, we know that the shape of a finite
geometric lattice is both log-concave (and hence unimodal) and top-heavy. Can we draw
this conclusion for the strong/weak shape of some semigroup actions on some geometric
lattices?
Boolean lattices, partition lattices and projective/affine geometries are some most well-
known geometric lattices. It is easy to see that their shapes are all ultra-log-concave
(and hence real-rooted) and top-heavy [37]. The main result of this paper, Theorems 2.1
and 2.12, declare the top-heavy property for the strong/weak shape of some semigroups
acting on Boolean lattices and projective/affine geometries. The semigroups considered by
us are those derived from “simple” transformations. We also report our attempt at tackling
the same problem for partition lattices and the Vámos matroid.
In Section 2, we will present our main results as well as pertinent problems, examples,
and remarks. The first three subsections are devoted to Boolean lattices, partition lattices
and projective/affine geometries. The last subsection is a simple discussion in the context
of matroids. Before digging into the proofs of the main results, we develop some technical
tools in Section 3. In the sequel, we provide in Sections 4 to 7 all the proofs missing from
Sections 2.1 to 2.4. We conclude the paper in Section 8 with a brief discussion of the
present work and some possible further research.
2 A top-heavy promenade
2.1 Boolean semiring and homogeneity
For any set Ω, the set BΩ
.
=
⋃∞
k=0
(
Ω
k
)
forms a poset under the inclusion relationship,
which is often known as the Boolean semiring over Ω, and the set 2Ω gives rise to the
Boolean algebra over Ω. When we view BΩ as a valuated poset, unless stated otherwise,
the valuation will be r(A) = |A| for all A ∈ BΩ. If Ω is a finite set, BΩ coincides with 2Ω
and is referred to as a Boolean lattice.
Let A and Ω be two sets with A ⊆ Ω. For any g ∈ ΩΩ, write g|A for the restriction
of g on A. Let S be a transformation semigroup on Ω. For any positive integer k ≤ |Ω|,
we name S k-homogeneous if the transformation semigroup S is transitive on
(
Ω
k
)
, that is,
scc(Γ(S)[
(
Ω
k
)
] = 1. The stabiliser permutation group of (S,A) is the permutation group
SA
.
= {g|A : g ∈ S,Ag = A} acting on A. The relative transformation semigroup of
(S,A) is the transformation semigroup S̃A
.
= {g|A : g ∈ S,Ag ⊆ A} acting on A. Note
that the action of S̃A on A may not be transitive even if S acts on A transitively.
Theorem 2.1. Let Ω be a set of size n. Let S be a transformation semigroup on Ω and let
Γ be the phase space of S.
(1) SS(S,BΩ) is 1-top-heavy.
(2) Both WS(S,BΩ) and SS(S,BΩ) are top-heavy.
(3) Let k and ℓ be two integers such that 0 ≤ k ≤ ℓ ≤ k + ℓ ≤ n+ 1. Let A ∈
(
Ω
k
)
and
B ∈
(
Ω
ℓ
)
. If n < ∞ and S is ℓ-homogeneous, then scc(Γ(SA)) = wcc(Γ(SA)) ≤
wcc(Γ(SB)) = scc(Γ(SB)).
Question 2.2. Take a finite set Ω and two integers k and ℓ such that k ≤ ℓ < k+ℓ ≤ |Ω|+1.
Let S be an ℓ-homogeneous transformation semigroup acting on Ω. For any A ∈
(
Ω
k
)
and
B ∈
(
Ω
ℓ
)
, does it always hold that wcc(Γ(S̃A)) ≤ wcc(Γ(S̃B))?
654 Ars Math. Contemp. 22 (2022) #P4.09 / 649–674
When restricting to permutation groups, the results in Theorem 2.1 are all known more
than 40 years ago: Claim (1) for an infinite set Ω was discovered by Brown [12, Corol-
lary 1]; Claim (2) for a finite set Ω was derived by Livingstone and Wagner [38, Theo-
rem 1]; Claim (3), as well as a positive answer to Question 2.2 for permutation groups, was
proved by Cameron [15, Proposition 2.3] under the mild restriction of k + ℓ ≤ |Ω|. Let
G be a group acting on a finite set Ω. By Theorem 2.1(2), or more precisely Livingstone-
Wagner Theorem [38, Theorem 1], we know that the strong/weak shape of 2Ω under the
action of G is a symmetric unimodal distribution. This means that, for any two integers k
and ℓ such that k ≤ ℓ < k + ℓ ≤ |Ω|, the number of G-orbits on
(
Ω
ℓ
)
is equal to the sum
of a nonnegative integer c plus the number of G-orbits on
(
Ω
k
)
. As an improvement of this
fact, Siemons [56, Corollary 4.3] found a natural linear space whose dimension equals this
integer c and he [56, Theorem 4.2] even obtained an algorithm to reconstruct the G-orbits
on
(
Ω
k
)
from the information on the G-orbits on
(
Ω
ℓ
)
without reference to the group G.
Question 2.3. Let Ω be a finite set, and let k and ℓ be two integers such that k ≤ ℓ <
k + ℓ ≤ |Ω|. Let S be a transformation semigroup on Ω and let Γ be the phase space of S.
(1) Is there a counterpart of [56, Corollary 4.3] which explains the nonnegativity con-
straint on the integer wcc(Γ[
(
Ω
ℓ
)
])− wcc(Γ[
(
Ω
k
)
])?
(2) If S is (ℓ + 1)-homogeneous, is there a counterpart of [56, Corollary 4.3] which
explains the nonnegativeness of the integer scc(Γ(SB)) − scc(Γ(SA)) for any A ∈(
Ω
k
)
and B ∈
(
Ω
ℓ+1
)
?
(3) Is there any algorithm to determine the weakly connected components of Γ[
(
Ω
k
)
] from
the weakly connected components of Γ[
(
Ω
ℓ
)
] without reference to the transformation
semigroup S?
Example 2.4. Let Ω be a set carrying a linear order ≺. A map g ∈ ΩΩ is order-preserving
with respect to ≺ provided αg is not bigger than βg in ≺ whenever α is not bigger than β
in ≺. Let S be the monoid consisting of all order-preserving maps on Ω with respect to the
given linear order ≺. It is easy to see that S is ℓ-homogeneous for all ℓ ≤ |Ω| but it is even
not 2-transitive; by contrast, this phenomenon never happens for permutation groups due
to a result of Livingstone and Wagner [38, Theorem 2(b)]. Note that the only permutation
contained in S is the identity map in case that Ω is a finite set. This suggests that you may
not be able to read Theorem 2.1 or answer Question 2.3 directly from those known facts on
permutation groups.
Example 2.5. Let Ω = {1, . . . , 6}. Let r and b be two maps in T(Ω) such that
r(1) = r(2) = 3, r(3) = r(4) = 5, r(5) = r(6) = 1;
b(6) = b(1) = 2, b(2) = b(3) = 4, b(4) = b(5) = 6.
Let S = ⟨r, b⟩. On the left of Figure 1, we depict the phase space Γ(S, {r, b}); on the right
of Figure 1, we display both the strong shape and the weak shape of 2Ω under the action of
S. Both weak shape and strong shape are unimodal and top-heavy. But neither of them is
log-concave. Note that the peak of the weak shape does not happen at the middle rank 3.
Y. Wu and Y. Zhu: Top-heavy phenomena for transformations 655
Vertex set(
Ω
6
)
(
Ω
5
)
(
Ω
4
)
(
Ω
3
)
(
Ω
2
)
(
Ω
1
)
(
Ω
0
)
wcc
1
6
15
7
1
1
1
scc
1
6
15
19
10
1
1
1
2
3
4
5
6
Figure 1: Γ(S, {r, b}) and Γ(S, {r, b})[
(
Ω
k
)
], k ∈ {0, 1, . . . , 6}. See Example 2.5.
Example 2.6. Let Ω be a set of size n ≥ 3 and let S be a transformation semigroup acting
on Ω. If SS(S, 2Ω) is not a sequence of all ones and has at least two ones at the beginning
of it, then it cannot be log-concave. This happens when S is the alternating group of order
n ≥ 4 and when S is 2-homogeneous but not 3-homogeneous.
Example 2.7. Let n and k be two integers such that 1 ≤ k ≤ n. Let Ω be a set of size n
and take X ∈
(
Ω
k
)
. Let S be the set {f ∈ T(Ω) : f |X = Id |X ,Ωf = X}. Note that S is
a transformation semigroup on 2Ω satisfying
wcc(Γ(S)[
(
Ω
i
)
] =
{
1, if 0 ≤ i ≤ k;(
n
i
)
, if k + 1 ≤ i ≤ n.
This shows that the sequence WS(S, 2Ω) is unimodal and top-heavy and that it is not log-
concave when n ≥ 2. Note that SS(S, 2Ω) is a sequence of all ones.
Question 2.8. Let S be a transformation semigroup acting on an n-element set Ω. When
can we conclude that the strong/weak shape of 2Ω under the action of S is unimodal?
Neumann [44] asked whether every λ-homogeneous permutation group is θ-homogene-
ous for all cardinals λ > θ ≥ ℵ0. Assuming Martin’s Axiom, Shelah and Thomas [55] gave
a negative answer to it. Hajnal [26] supplied an example to show that 2θ-homogeneity does
not imply θ-homogeneity. An observation in the same vein by Penttila and Siciliano [47,
Remark 4.6] was based upon the Generalized Continuum Hyphothesis. For each statement
in Theorem 2.1(3), Question 2.2 and 2.3, it is interesting to see whether or not it holds in
the case that Ω is an infinite set. We are also wondering if the rich theory on oligomorphic
permutation groups [16] should have a counterpart for transformation semigroups.
656 Ars Math. Contemp. 22 (2022) #P4.09 / 649–674
2.2 Partition lattice
Let Ω be a set. For any map s ∈ ΩΩ, we define its kernel map, denoted by s−1, to be the
map from 2Ω to 2Ω that sends X ∈ 2Ω to Xs−1 = {y ∈ Ω : ys ∈ X} ∈ 2Ω. To illustrate
the definition, we depict the phase space of a map s on the left of Figure 2 and part of
the phase space of s−1 in the middle of Figure 2. A partition of Ω is a set of nonempty
disjoint subsets of Ω whose union is Ω. We call these elements of a partition its blocks.
The rank of a partition π is
∑
B∈π(|B| − 1). Write P(Ω) for the set of all partitions of Ω
of finite ranks. When |Ω| < ∞, the set P(Ω) together with the refinement relation forms a
geometric lattice, which we call the partition lattice of Ω. Note that the rank of a partition
in this geometric lattice is |Ω| minus the number of its blocks. Let Pk(Ω) be the set of
rank-k partitions of Ω, namely, those partitions of Ω of size |Ω| − k. Each transformation
s ∈ ΩΩ induces a transformation s∗ of 2Ω such that Πs∗ = {πs−1 : π ∈ Π} \ {∅} for all
Π ∈ P(Ω). We demonstrate part of the phase space of s∗ on the right of Figure 2 for the
map s as shown on the left there. Let S be a transformation semigroup on Ω. We have a
derived transformation semigroup S∗ := {s∗ : s ∈ S} on P(Ω), which we call the kernel
space of S. We say that S is k-kernel homogeneous if for all Π,Π′ ∈ Pk(Ω) there exists
s ∈ S such that Πs∗ = Π′, which surely implies scc(Γ(S∗)[Pk(Ω)]) ≤ 1.
1
2
3
4
5
6
s
{2, 3}{4, 5}
{1, 6}
s−1
123|4|56 16|23|45
s∗
Figure 2: A map, its inverse and the derived action on partitions.
Example 2.9. On the left of Figure 3, we depict the so-called Černý automaton C4 =
Γ(S,G), whereG = {a, b} consists of two transformations on a four-element set Ω. On the
right of Figure 3, we depict the automaton Γ(S∗, G∗) where S∗ is acting on P(Ω). Observe
that WS(S∗,P(Ω)) = (1, 1, 1, 1) and SS(S∗,P(Ω)) = (1, 2, 2, 1) are both unimodal and
top-heavy.
For any finite set Ω, A ∈ 2Ω, π ∈ P(Ω) and s ∈ ΩΩ, it holds
r(A) ≥ r(As) and r(π) ≤ r(πs∗).
This difference between Boolean lattice and partition lattice somehow hints at our difficulty
of turning the following conjecture into a result like Theorem 2.1.
Conjecture 2.10. Let Ω be a finite set and let S be a semigroup acting on Ω. Then both
WS(S∗,P(Ω)) and SS(S∗,P(Ω)) are top-heavy.
For each set Ω and each positive integer k ≤ |Ω|, we use P(Ω, k) for the set of partitions
of Ω into k blocks.
Y. Wu and Y. Zhu: Top-heavy phenomena for transformations 657
0 1
23
a
b
a
b
a
b
a b
0
1
2
3
0 3
1
2
2 3
0
1
0 1
2
3
1 2
0
3
0 1
2 3
0 3
1 2
1 3
0
2
0 2
1
3
0 1 3
2
0 1 2
3
0 2 3
1
1 2 3
0
0 2
1 3
0 1 2 3
b∗
a∗
a∗
b∗
a∗
b∗
a∗
b∗
a∗
b∗
a∗
b∗
a∗
b∗
a∗
b∗
a∗
b∗
a∗
b∗
a∗
b∗
a∗
b∗
a∗, b∗
a∗
b∗
a∗
Figure 3: Černý automaton C4 and its kernel space. See Example 2.9.
Question 2.11. (1) Take two positive integers k and ℓ with k < ℓ. Let Ω be an infinite
set and let S be a semigroup S acting on Ω. If S∗ is transitive on P(Ω, ℓ), is it true
that S∗ is transitive on P(Ω, k)?
(2) The shapes of all Dowling lattices, which include all partition lattices, are real-rooted
[8]. What about the top-heavy property of the (strong/weak) shapes of Dowling
lattices under a semigroup action?
There has been an active study of those permutation groups which are transitive on the
set of all ordered or unordered partitions of a set of a given shape [2, 21, 39, 43]. But even
when confining our attention to permutation groups, we are not aware of any work related
to Conjecture 2.10 and Question 2.11.
2.3 Subspace lattice
Let Ω be a possibly infinite set of size n, let k be a nonnegative integer with k ≤ n and let F
be a finite field. We mention that Gr(k, FΩ) is a q-analogue of
(
Ω
k
)
and their relationship is
like the one between Johnson graphs and Grassmann graphs [45]. For each prime power q,
we write Fq for the q-element finite field. Write Matn(Fq) for the multiplicative semigroup
of all Ω by Ω matrices over Fq each row/column of which have finitely many nonzeros; and
write Affn(Fq) for the semigroup of all affine linear transformation on Fnq equipped with
the associated product of composition. We regard the empty set as the dimension-(−1)
affine/linear subspace. The set of all nonempty finite linear subspaces of Fnq is denoted
by Pq,n
.
= Gr(Fnq ) and the set of all dimension-k linear subspaces of Fnq is denoted by
Pkq,n
.
= Gr(k,Fnq ). By a finite affine subspace of a linear space V , we mean a translate
of a finite linear subspace of V . The set of all finite affine subspaces of Fnq is denoted by
Aq,n and the set of all dimension-k affine subspaces of Fnq is denoted by Ak+1q,n . Note that
Pq,n and Aq,n are known as projective geometry and affine geometry over the field Fq ,
respectively. For each nonnegative integer k, we put the rank of each element in Pkq,n and
the rank of each element in Akq,n to be k, thus getting two valuated posets Pq,n and Aq,n,
658 Ars Math. Contemp. 22 (2022) #P4.09 / 649–674
which are geometric lattices when n <∞.
We are ready to display Theorem 2.12, a q-analogue of Theorem 2.1. Kantor [31,
Theorem 1] deduced a q-analogue of the aforementioned result of Livingstone and Wagner
[38, Theorem 1]. If the semigroup S ≤ Matn(Fq) is a subgroup of the general linear group
GLn(Fq), Stanley [59, Corollary 9.9] found that SS(SP ,Pq,n) and WS(SP ,Pq,n) are both
symmetric and unimodal for finite n. Penttila and Siciliano [47, Theorem 4.4(ii), (iii)]
generalized this result of Stanley for groups to the case that n is infinite.
Theorem 2.12. Let n be the size of a nonempty set, and let q be a prime power.
(1) Let S ≤ Matn(Fq) be a linear transformation semigroup acting on Fnq . For each
g ∈ S, write gP for g|Pq,n . Let SP be the transformation semigroup {gP : g ∈ S}
acting on Pq,n. Then SS(SP ,Pq,n) and WS(SP ,Pq,n) are both top-heavy.
(2) Let T ≤ Affn−1(Fq) be an affine linear transformation semigroup acting on Fn−1q .
For each g ∈ T , write gA for g|Aq,n−1 . Let TA be the transformation semigroup
{gA : g ∈ T} acting on Aq,n−1. Then SS(TA,Aq,n−1) and WS(TA,Aq,n−1) are
both top-heavy.
Remark 2.13. When n is infinite, Theorems 2.1 and 2.12 in the original version of this
paper, submitted on 19 July 2018, contains weaker results. Following the proof presented
by Bercov and Hobby for [9, Corollary 1] and also the proof of Roy for [51, Theorem],
we used the existence of Ramsey number [49, Theorem A] to derive Theorem 2.1(1) for
infinite n. A similar argument based on Ramsey number shows that both SS(SP ,Pq,n)
and SS(TA,Aq,n−1) are 1-top-heavy for infinite n in the setting of Theorem 2.12. After
the acceptance of this paper in 2022, we notice the work of Penttila and Siciliano [47,
Lemma 3.1], which was submitted on 30 April 2019 and published in 2021, and thus arrive
at the corresponding strengthening in Theorem 2.1(2) and Theorem 2.12 via an application
of their idea. See Lemma 3.6.
Remark 2.14. Kantor [32, Theorem 2] determined all the ordered-basis-transitive finite
geometric lattices of rank at least three: Roughly speaking, they are Boolean lattices, pro-
jective (affine) geometries, and four sporadic designs. Kantor’s classification theorem along
with Theorems 2.1 and 2.12 may be a basis for getting homogeneity results about ordered-
basis-transitive matroids.
Question 2.15. A general projective geometry is defined to be a modular combinatorial
geometry that is connected in the sense that the point set cannot be expressed as the union
of two proper flats [64, page 313]. Can we establish a counterpart of Theorem 2.12 for
general projective geometries?
In mathematics we encounter quite some nice duality phenomena, say Chow’s Theorem
[45, Corollary 3.1] and many duality concepts for matroids [13]. For projectie geometry,
we have the following duality result of Stanley [59, Corollary 9.9].
Theorem 2.16 (Stanley). Let F be a finite field and let k and n be two positive integers
with k < n. For any subgroup G of GL(n, F ), the number of orbits of the action of G on
Gr(k, Fn) must be the same with the number of orbits of G acting on Gr(n− k, Fn).
Question 2.17. If n is the size of an infinite set, does Theorem 2.16 still hold? Here, we
should first of all choose a good definition for infinite Grassmannians [46].
Y. Wu and Y. Zhu: Top-heavy phenomena for transformations 659
2.4 A glimpse of matroid
In previous subsections, we discuss those poset endomorphisms which are derived from
either set transformations or linear transformations. Since finite geometric lattices just en-
code information of finite matroids, it is natural to ask why not directly consider matroids
and morphisms among matroids, namely those transformations which preserve “indepen-
dence structure”.
Let M1 and M2 be two matroids and let f be a map from EM1 to EM2 . We call f a
weak map from M1 to M2 provided
rM1(A) ≥ rM2(Af)
holds for all A ⊆ EM1 , and we call f a strong map from M1 to M2 provided the preimage
of any flat in M2 is a flat of M1 [33, 35, 57]. It is known that all strong maps must be weak
maps.
Let M be a matroid on the ground set EM = Ω. Let TM (Ω) (T∗M (Ω)) be the monoid
consisting of all elements of T(Ω) which are weak (strong) maps from M to itself. If we
know that S is a subsemigroup of TM (Ω) (T∗M (Ω)) acting on Ω, we can define a digraph
ΓM,t(S) on Ft(M) as follows: for any X,Y ∈ Ft(M), there is an arc from X to Y if and
only if there is g ∈ S such that the minimum flat containing Xg in M is Y. What is the
relationship between the connectivity of ΓM,t(S) and ΓM,r(S) for different t and r? We
can ask the same question by imposing the extra condition that every element f ∈ S is a
bijection on Ω. If the matroid is a very special uniform matroid, namely a matroid in which
all sets are independent, one can see that what is discussed in Section 1.3 becomes a very
special case of this general setting.
Vámos matroid, also known as Vámos cube, is a famous non-algebraic matroid [5, 22,
42, 54]; see [24, Example 6.30] for a description of this rank-4 matroid over a ground set
of size eight.
Example 2.18. Let M be the Vámos matroid and let S be a subsemigroup of T∗M (EM ). It
holds wcc(ΓM,1(S)) ≤ wcc(ΓM,2(S)) ≤ wcc(ΓM,3(S)) and scc(ΓM,1(S)) ≤
scc(ΓM,2(S)) ≤ scc(ΓM,3(S)).
Remark 2.19. Compared with the Fundamental Theorem of Projective (Affine) Geometry
[17, 48], we think that weak/strong maps and bijective weak/strong maps for matroids are
natural extensions of linear transformations and invertible linear transformations for linear
spaces. We also mention the well-adopted viewpoint that the full permutation group and
the full transformation semigroup can be interpreted as the general linear group and the
linear transformation semigroup over the field with one element.
3 Valuated poset and incidence operator
3.1 Hereditary endomorphism and injective incidence operator
To prepare for a proof of our main results listed in Section 2, we will introduce a key prop-
erty and then present a key lemma for our work. The key property is the so-called hereditary
endomorphisms. The key lemma is Lemma 3.2, which gives us some information of the
strong/weak shapes of a poset under some semigroup action, provided the semigroup con-
sists of hereditary endomorphisms and that some linear map associated with the poset is
injective.
660 Ars Math. Contemp. 22 (2022) #P4.09 / 649–674
β βgPℓ
Pk ∩ P↓(β)
Pℓ
Pk ∩ P↓(βg)
g
g
bijective
Figure 4: An (ℓ, k)-hereditary endomorphism.
Let P be a valuated poset. For any nonnegative integers k ≤ ℓ, we call the poset P
(k, ℓ)-finite provided Pk ̸= ∅, Pℓ ̸= ∅ and the set Pℓ ∩ P↑(α) is finite for every α ∈ Pk;
we call P (ℓ, k)-finite provided Pk ̸= ∅, Pℓ ̸= ∅ and the set P↓(β) ∩ Pk is finite for
every β ∈ Pℓ; we call g ∈ End(P ) a (k, ℓ)-hereditary endomorphism if for all α ∈ Pk
which satisfies rP (g(α)) = rP (α) = k it happens that g induces a bijection from the set
Pℓ ∩ P↑(α) to Pℓ ∩ P↑(αg); we call g ∈ End(P ) an (ℓ, k)-hereditary endomorphism if
for each β ∈ Pℓ, rP (βg) = rP (β) = ℓ ensures that g induces a bijection from the set
Pk ∩ P↓(β) to Pk ∩ P↓(βg). See Figure 4 for an illustration. For any k, ℓ ∈ Z≥0, we
designate by hEndk,ℓ(P ) the set of all (k, ℓ)-hereditary endomorphisms of the valuated
poset P .
Let S be a transformation semigroup on a valuated poset P and let G be a generating
set of S. For any two nonnegative integers k and ℓ with k ≤ ℓ ≤ r(P ), we set ΠS,G(k, ℓ)
to be the digraph with vertex set Pk and arc set
{(α, α′) ∈ Pk × Pk : ∃g ∈ G, β ∈ Pℓ s.t. βg ∈ Pℓ, α′ = αg, α ∈ P↓(β)};
we set ΠS,G(ℓ, k) to be the digraph with vertex set Pℓ and arc set
{(α, α′) ∈ Pℓ × Pℓ : ∃g ∈ G, β ∈ Pk s.t. βg ∈ Pk, α′ = αg, α ∈ P↑(β)}.
We use the shorthand ΠS(k, ℓ) for ΠS,S(k, ℓ).
Lemma 3.1. Let P be a valuated poset. Take two nonnegative integers k and ℓ such that
k, ℓ ≤ r(P ) and that P is (ℓ, k)-finite. Let S be a sub-semigroup of hEndℓ,k(P ), let G
be a generator set of S, and let Γ .= Γ(S,G). Let β ∈ Pℓ and let α ∈ Pk be an element
comparable with β. Assume that g and h are two elements of S such that βg ∈ Pℓ and
βgh = β. Then there exists f ∈ S such that βgf ∈ Pℓ and αgf = α. Especially, if every
weakly connected component of Γ[Pℓ] is strongly connected, then so is ΠS,G(k, ℓ).
Proof. The second claim is immediate from the first and so our task is just to prove the
first one. Without loss of generality, we assume that k < ℓ. Since β(gh) = β and gh ∈
S ≤ hEndℓ,k(P ), it follows that gh induces a permutation on Pk ∩ P↓(β). But from the
assumption that P is (ℓ, k)-finite, we see that Pk ∩ P↓(β) is a finite set, which contains
α. This means that there exists a positive integer r such that α(gh)r = α. Accordingly,
for f = (hg)r−1h ∈ S it holds (βg)f = (βg)(hg)r−1h = β(gh)r = β ∈ Pℓ and
(αg)f = (αg)(hg)r−1h = α(gh)r = α, finishing the proof.
For any set Ω, QΩ refers to the linear space of all rational functions on Ω. If P is an
(ℓ, k)-finite valuated poset, the incidence operator ζk,ℓP : QPk → QPℓ is the linear operator
Y. Wu and Y. Zhu: Top-heavy phenomena for transformations 661
such that for all f ∈ QPk and β ∈ Pℓ, we have
(ζk,ℓP (f))(β) =
{∑
α∈Pk∩P↓(β) f(α), if k ≤ ℓ;∑
α∈Pk∩P↑(β) f(α), if k > ℓ.
(3.1)
Lemma 3.2. Let P be a valuated poset. Take two nonnegative integers k and ℓ not ex-
ceeding r(P ) such that P is (ℓ, k)-finite, and hence ζk,ℓP is well-defined. Let S be a sub-
semigroup of hEndℓ,k(P ) and let Γ stand for Γ(S). Assume that ζ
k,ℓ
P is an injective linear
map from QPk to QPℓ .
(1) wcc(Γ[Pk]) ≤ wcc(ΠS(k, ℓ)) ≤ wcc(Γ[Pℓ]).
(2) scc(Γ[Pk]) ≤ scc(ΠS(k, ℓ)) ≤ scc(Γ[Pℓ]).
Proof. (1) The first inequality is a consequence of the fact that E(ΠS(k, ℓ)) ⊆ E(Γ[Pk]).
Let W ⊆ QPℓ be the subspace of all functions which are constant on each weakly
connected component of Γ[Pℓ]; let V ⊆ QPk be the subspace of all functions which
are constant on each weakly connected component of ΠS(k, ℓ). Note that dim(V ) =
wcc(ΠS(k, ℓ)) and dim(W ) = wcc(Γ[Pℓ]) and so it suffices to demonstrate dim(V ) ≤
dim(W ).
By symmetry, we only deal with the case of k ≤ ℓ. For every f ∈ V and every arc
(β, βg) of Γ[Pℓ], we have
(ζk,ℓP (f))(βg) =
∑
α′∈Pk∩P↓(βg)
f(α′)
=
∑
α∈Pk∩P↓(β)
f(αg) (g ∈ hEndℓ,k(P ))
=
∑
α∈Pk∩P↓(β)
f(α) (f ∈ V )
= (ζk,ℓP (f))(β).
This says that ζk,ℓP (f) ∈ W for all f ∈ V . Hence, by the injectivity of ζ
k,ℓ
P , dim(V ) ≤
dim(W ), as wanted.
(2) The first inequality is a consequence of the fact that E(ΠS(k, ℓ)) ⊆ E(Γ[Pk]).
Let W ′ ⊆ QPℓ be the subspace of all functions which are constant on each strongly
connected component of Γ[Pℓ]; let V ′ ⊆ QPk be the subspace of all functions which
are constant on each strongly connected component of ΠS(k, ℓ). Note that dim(V ′) =
scc(ΠS(k, ℓ)) and dim(W ′) = scc(Γ[Pℓ]) and so it suffices to demonstrate dim(V ′) ≤
dim(W ′). Take f ∈ V ′. As ζk,ℓP is injective, we aim to show that ζ
k,ℓ
P (f) ∈W ′.
By symmetry, we only deal with the case of k ≤ ℓ. Assume that β and βg are from
the same strongly connected component of Γ[Pℓ], where g ∈ S. By the first claim of
Lemma 3.1, for every α ∈ Pk ∩ P↓(β), α and αg fall into the same strongly connected
component of Γ[Pk] and so, as f ∈ V ′,
f(α) = f(αg). (3.2)
662 Ars Math. Contemp. 22 (2022) #P4.09 / 649–674
This allows us to write
(ζk,ℓP (f))(βg) =
∑
α′∈Pk∩P↓(βg)
f(α′)
=
∑
α∈Pk∩P↓(β)
f(αg) (g ∈ hEndℓ,k(P ))
=
∑
α∈Pk∩P↓(β)
f(α) (Equation (3.2))
= (ζk,ℓP (f))(β),
proving that ζk,ℓP (V
′) ⊆W ′, as desired.
3.2 Injectivity
In order to apply Lemma 3.2, we may need to have some results to guarantee the injectivity
of an incidence operator. In this regard, a good understanding of the incidence algebra of a
poset may be valuable [36, 68]. We mention that Guiduli [4, Theorem 9.4] established an
injectivity result for the so-called rank-regular semi-lattices. It may also be quite useful if
the following conjecture [34, Conjecture 1.1] can be verified.
Conjecture 3.3 (Kung). Let P be a finite geometric lattice. Let k and ℓ be two positive
integers such that k ≤ ℓ ≤ r(P )2 . Then ker(ζ
k,ℓ
P ) = {0}.
We suggest a slight strengthening of Kung’s Conjecture (Conjecture 3.3) as follows.
Conjecture 3.4. Let P be a geometric lattice. Let k and ℓ be two nonnegative integers
such that k ≤ ℓ ≤ k + ℓ ≤ r(P ). If P is (ℓ, k)-finite, then ζk,ℓP is an injective map.
Remark 3.5. Let M be a matroid of rank r. Let S be a subsemigroup of T ∗M (EM ). For
every f ∈ S, let f ′ : F(M) → F(M) be the map sending a flat X ∈ F(M) to the
minimum flat containing Xf in M . Assume that f ′ ∈ hEndℓ,k(F(M)) for every f ∈ S.
In light of Lemma 3.2, if Conjecture 3.4 is valid for the lattice F(M), we will be able
to conclude that both the sequence (wcc(ΓM,0(S)), . . . ,wcc(ΓM,r(S))) and the sequence
(scc(ΓM,0(S)), . . . , scc(ΓM,r(S))) are top-heavy.
Let P be a valuated poset which is (ℓ, k)-finite for all nonnegative integers k ≤ ℓ. We
say that P has a top-heavy injective incidence operator provided ζk,ℓP is an injective linear
map from QPk to QPℓ for all nonnegative integers k and ℓ satisfying k ≤ ℓ ≤ k+ℓ ≤ r(P ).
Penttila and Siciliano [47, Lemma 3.1] pointed out a simple way to establish some
injectivity result for linear operators between infinite-dimensional linear spaces whenever
they fulfil certain finiteness characteristics. We reformulate their observation below for the
convenience of our later usage.
Lemma 3.6. Let P be a valuated poset. Let k ≤ ℓ be two nonnegative integers such that
P is (ℓ, k)-finite. Assume that for every A ∈ Pk, we can find a finite subset Y of Pk+ℓ such
that the ideal generated by Y in P , denoted Y ↓ and with the restriction of rP as its rank
function, contains A and possesses a top-heavy injective incidence operator. Then ζk,ℓP is
an injective linear map from QPk to QPℓ .
Y. Wu and Y. Zhu: Top-heavy phenomena for transformations 663
Proof. Take f ∈ ker ζk,ℓP . Assume, for sake of contradiction, that f(A) ̸= 0 for some
A ∈ Pk. Choose Y ⊆ Pk+ℓ such that A ∈ Y ↓ ∩ Pk and Y ↓ possesses a top-heavy
injective incidence operator. Let Q represent the resulting valuated poset on Y ↓. Let g
be the restriction of f on Qk and let h be the restriction of ζ
k,ℓ
P (f) = 0 on Y . We have
0 = h = ζk,ℓQ (g) but g(A) = f(A) ̸= 0, violating the assumption that Y ↓ has a top-heavy
injective incidence operator.
3.3 Incidence operator as an intertwiner
For f ∈ ΨΩ, we sometimes need to talk about f(ω) for ω /∈ Ω. Following the practice
of those mathematics with natural multivalued operations [7, 14, 65], we create a universal
“don’t care” symbol ⋆ /∈ Ψ and will set f(ω) = ⋆. We often regard ⋆ as all possible values
in Ψ and so, whenever we have some addition operation + on Ψ, we extend it to Ψ ∪ {⋆}
by setting ⋆+ ψ = ⋆ for all ψ ∈ Ψ ∪ {⋆}.
Let P be a valuated poset. Let k and ℓ be two nonnegative integers no greater than
r(P ). Let g ∈ PP . For f ∈ QPk , we write fg†,k for the element in ({⋆} ∪ Q)Pk , where
⋆ stands for “don’t care” and can be thought of as the whole set Q, such that the following
holds for all β ∈ Pk:
fg†,k(β) =
{
f(βg), if βg ∈ Pk;
⋆, if βg /∈ Pk.
Denote by Fix g†,k the set of f ∈ QPk for which
fg†,k(β) ∈ {f(β), ⋆}
holds for all β ∈ Pk. If g ∈ hEndℓ,k(P ), we say that it is a good (ℓ, k)-hereditary
endomorphism of P provided that for any β ∈ Pℓ with βg /∈ Pℓ it holds αg /∈ Pk for
some α ∈ Pk which is comparable to β in P . Assuming that g is a good (ℓ, k)-hereditary
endomorphism of P , for any β ∈ Pℓ and f ∈ QPk we will have
(ζk,ℓP (f)g
†,ℓ)(β) = (ζk,ℓP (f))(βg)
=
∑
α′∈Pk∩(P↓(βg)∪P↑(βg))
f(α′)
=
∑
α∈Pk∩(P↓(β)∪P↑(β))
f(αg)
= (ζk,ℓP (fg
†,k))(β)
whenever βg ∈ Pℓ, and that
(ζk,ℓP (f)g
†,ℓ)(β) = (ζk,ℓP (f))(βg)
= ⋆
= (ζk,ℓP (fg
†,k))(β)
whenever βg /∈ Pℓ. This observation can be summarized by the commutative diagram
in Figure 5, which implies that Fix g†,k is mapped by ζk,ℓP to Fix g
†,ℓ for all good (ℓ, k)-
hereditary endomorphisms g of P .
664 Ars Math. Contemp. 22 (2022) #P4.09 / 649–674
f ζk,ℓP (f)
fg†,k ζk,ℓP (fg
†,k)
ζk,ℓP
g†,k
ζk,ℓP
g†,ℓ
Figure 5: The incidence operator intertwines with every good hereditary endomorphism.
Example 3.7. (1) Let Ω be a set of size n. Assume that 2 ≤ k < ℓ ≤ n. Here is an
easy observation used often in the study of synchronizing automata: For any g ∈ ΩΩ
and any A ∈
(
Ω
ℓ
)
, we have |Ag| = ℓ if and only if |Bg| = k for all B ∈
(
A
k
)
.
This conclusion is surely not valid any more when k ≤ 1. Note that g is a good
(ℓ, k)-hereditary endomorphism of the Boolean lattice 2Ω for each g ∈ ΩΩ.
(2) Take integers n, k and ℓ such that 2 ≤ k < ℓ ≤ n and let q be a prime power.
Let P = Pq,n or P = Aq,n−1. Similar to the above claim on Boolean lattice,
M is a good (ℓ, k)-hereditary endomorphism of P for each M ∈ Matn(Fq) or
M ∈ Affn−1(Fq), respectively.
4 Boolean semiring
Let Ω be a set and let k and ℓ be two nonnegative integers such that k < ℓ ≤ |Ω|. For the
valuated poset P = BΩ, we write the incidence operator ζ
k,ℓ
P defined in Equation 3.1 as
ζk,ℓΩ . That is,
(ζk,ℓΩ (f))(B) =
∑
A∈(Bk)
f(A)
for all f ∈ Q(
Ω
k) and B ∈
(
Ω
ℓ
)
.
Following a common approach in establishing homogeneity of permutation groups
[15, 41] [20, pages 20-22], we will make use of the ensuing result on the rank of the subset
inclusion matrix. The result has been discovered independently by many but the earliest ap-
pearance of it dates back to the work of Gottlieb [25, Corollary 2]. Among many different
proofs of this classical result, we refer the reader to [18, Corollary] and [56, Theorem 2.4].
Note that it gives a positive answer to Conjecture 3.4 for Boolean lattices.
Lemma 4.1 (Gottlieb). Let Ω be a nonempty finite set. Then ker ζk,ℓΩ = {0} for any two
integers k and ℓ satisfying 0 ≤ k ≤ ℓ ≤ k + ℓ ≤ |Ω|.
Let Ω be a set and S be a transformation semigroup on Ω. Let Ω♯ .= {(ω,C) : ω ∈
C ∈ 2Ω} and, for each g ∈ S, let g♯ be the transformation on Ω♯ which sends (ω,C)
to (ωg,Cg) for all (ω,C) ∈ Ω♯. Let S♯ stand for the transformation semigroup on Ω♯
consisting of all elements g♯ for g ∈ S. For all positive integers ℓ, we use the following
notation:
Ω♯ℓ
.
= {(ω,C) : ω ∈ C ∈
(
Ω
ℓ
)
}
Y. Wu and Y. Zhu: Top-heavy phenomena for transformations 665
and
Γ♯ℓ(S)
.
= Γ(S♯)[Ω♯ℓ].
Here is a result analogous to Lemma 3.1.
Lemma 4.2. Let m be a positive integer and let S be an m-homogeneous transforma-
tion semigroup acting on a set Ω. Then the digraph Γ♯m(S) is symmetric. Especially,
wcc(Γ♯m(S)) = scc(Γ
♯
m(S)).
Proof. Take (ω,C) ∈ Ω♯m and g ∈ S such that |Cg| = m.Our task is to show the existence
of h ∈ S such that (ωg,Cg)h♯ = (ω,C). As S is m-homogeneous, we can find f ∈ S
such that Cgf = (Cg)f = C. Hence, the fact that |C| = m < ∞ allows us to obtain
a positive integer r for which (gf)r|C is the identity map on C. This means that we can
choose h to be f(gf)r−1.
Lemma 4.3. Let Ω be a set, let m be an integer satisfying |Ω| ≥ m > 1, and let S be a
transformation semigroup on Ω. For every X ∈
(
Ω
m
)
, it holds
scc(Γ(SX)) = wcc(Γ(SX)) ≤ wcc(Γ♯m(S)) ≤ scc(Γ♯m(S)). (4.1)
Moreover, if S is m-homogeneous, then
scc(Γ(SX)) = wcc(Γ(SX)) = wcc(Γ
♯
m(S)) = scc(Γ
♯
m(S)). (4.2)
Proof. It is trivial to see that wcc(Γ(SX)) = scc(Γ(SX)) and wcc(Γ♯m(S)) ≤ scc(Γ♯m(S)).
Let us call each strongly/weakly connected component of Γ(SX) a component. To prove
Equation (4.1), let us find an injective map ψ from the set of components of Γ(SX) to the
set of weakly connected components of Γ♯m(S).
For each γ ∈ X , let the weakly connected component of Γ♯m(S) containing (γ,X) be
ψ′(γ). Take γ1, γ2 from the same component of Γ(SX). We may assume that γ1g = γ2
and Xg = X for some g ∈ S. As (γ1, X)g♯ = (γ1g,Xg) = (γ2, X), we see that
ψ′(γ1) = ψ
′(γ2). For each component C of Γ(SX), we can now choose any γ ∈ C
and get a well-defined map ψ by setting ψ(C) = ψ′(γ). For every weakly connected
component C♯ of Γ♯m(S), let ϕ(C
♯) be the set {γ ∈ X : (γ,X) ∈ C♯}. It is routine to
check that ϕψ(C) = C for every component C of Γ(SX), proving that ψ is injective, as
desired.
Assume now S is m-homogeneous. It follows from Lemma 4.2 that wcc(Γ♯m(S)) =
scc(Γ♯m(S)). We thus call each strongly/weakly connected component of Γ
♯
m(S) simply
a component. Since S is m-homogeneous, for every component C♯ of Γ♯m(S), we have
ϕ(C♯) ̸= ∅. This verifies that ϕ and ψ are inverses of each other. We thus get Equation (4.2)
and so finish the proof.
Proof of Theorem 2.1. (1) This is a special case of (2).
(2) This is direct from Lemmas 3.2, 3.6 and 4.1.
(3) Since S is ℓ-homogeneous, it follows from Lemma 4.3 that
wcc(Γ(SA)) = scc(Γ(SA)) ≤ wcc(Γ♯k(S))
666 Ars Math. Contemp. 22 (2022) #P4.09 / 649–674
and
wcc(Γ(SB)) = scc(Γ(SB)) = wcc(Γ
♯
ℓ(S)).
It then remains to prove wcc(Γ♯ℓ(S)) ≥ wcc(Γ
♯
k(S)).
We regard Ω♯ as a valuated poset by putting r((α,X)) = |X| and requiring (α,X) <
(β, Y ) if and only if α = β ∈ Ω and X ⊊ Y ⊆ Ω. Note that S♯ ⊆ hEndℓ,k(Ω♯). In view
of Lemma 3.2(1), it is sufficient to show that ζk,ℓ
Ω♯
is injective.
For each nonnegative integer m and each α ∈ Ω, let Ω♯m,α
.
= {(α,A) : (α,A) ∈ Ω♯m}.
Corresponding to the partition Ω♯k =
⋃
α∈Ω Ω
♯
k,α and Ω
♯
ℓ =
⋃
β∈Ω Ω
♯
ℓ,β , the Ω
♯
k×Ω
♯
ℓ matrix
ζk,ℓ
Ω♯
is viewed as a partitioned matrix with blocks ζα,β , which are the submatrices with row
index set Ω♯k,α and column index set Ω
♯
ℓ,β , where α, β ∈ Ω. Observe that
ζα,β =
{
ζk−1,ℓ−1Ω\{α} , if α = β;
0, otherwise.
Since (k − 1) + (ℓ− 1) ≤ |Ω| − 1, it follows from Lemma 4.1 that ζα,α = ζk−1,ℓ−1Ω\{α} is of
full row rank for all α ∈ Ω. This implies that ζk,ℓ
Ω♯
is an injective linear map, as desired.
Remark 4.4. Let Ω be a set, which is not necessarily finite. Let k and ℓ be two integers
with k ≤ ℓ ≤ k + ℓ ≤ |Ω|. For all f ∈ Q(
Ω
ℓ) and A ∈
(
Ω
k
)
, we put
(ζℓ,kΩ (f))(A) =
∑
A⊆B
f(B).
Making use of Lemma 4.1, it is easy to see that the linear transformation ζℓ,kΩ : Q
(Ωℓ)
fin →
Q(
Ω
k)
fin is always a surjective map. Unfortunately, we do not see if this observation is helpful
for getting a possible counterpart of Theorem 2.1(3) for an infinite set Ω.
5 A graded Möbius algebra
Möbius algebra is a semigroup algebra which plays an important role in combinatorics
[36, Section 3.6]. Huh and Wang [28] introduced a graded Möbius algebra for geometric
lattices. Let L be a finite geometric lattice with rank function (valuation) r. Define a Q-
algebra M(L,Q), called the graded Möbius algebra of L [28], to be the linear space with
L as a Q-basis together with a multiplication given by
xy =
{
x ∨ y, if r(x) + r(y) = r(x ∨ y)
0, if r(x) + r(y) > r(x ∨ y),
and extended by linearity and distributivity. For any nonnegative integers k ≤ ℓ, it is easy
to see that the linear map ξk,ℓL as specified below is well-defined:
ξk,ℓL : QLk → QLℓ
ϕ 7→ (
∑
x∈L1 x)
ℓ−kϕ.
We call a finite geometric lattice a realizable lattice if it is the matroid lattice of a finite
realizable matroid. Here is the main result of Huh and Wang [28, Theorem 6] in their work
Y. Wu and Y. Zhu: Top-heavy phenomena for transformations 667
on solving the realizable case of the top-heavy conjecture of Dowling-Wilson. Huh and
Wang [28, Conjecture 7] conjectured that Theorem 5.1 holds without the assumption of
realizability.
Theorem 5.1 (Huh and Wang). Let L be a finite realizable geometric lattice with rank r.
For any integers k and ℓ such that k ≤ ℓ ≤ k + ℓ ≤ r, the linear map ξk,ℓL is injective.
Remark 5.2. (1) The partition lattice P(Ω) is isomorphic with the flat lattice of the
graphic matroid of the complete graph on Ω. Note that a graphic matroid is regular,
namely it is representable over every field. This means that finite partition lattices
are realizable.
(2) Assume that L is a either a Boolean lattice, or a subspace lattice or a partition lattice.
It is easy to see that ξk,ℓL = CL,k,ℓζ
k,ℓ
L for some positive integer CL,k,ℓ which is
determined by L, k and ℓ. Especially, ξk,k+1L = ζ
k,k+1
L . An important message
here is that, ζk,ℓL and ξ
k,ℓ
L , as two Q-linear maps, are either both injective or both
non-injective.
Kung [34, Theorem 1.3] verified Conjecture 3.3 for partition lattices of finite sets. We
can improve his result a little bit now. When Ω is finite, Lemma 5.3 claims that Conjec-
ture 3.4 holds for partition lattices.
Lemma 5.3. Let Ω be a set. Let k and ℓ be two integers such that k ≤ ℓ ≤ k + ℓ ≤ |Ω|.
Then ker(ζk,ℓP(Ω)) = {0}.
Proof. By Lemma 3.6, Theorem 5.1, and Remark 5.2.
Let Ω be a finite set and let k and ℓ be two integers such that 0 ≤ k ≤ ℓ ≤ k+ ℓ ≤ |Ω|.
By virtue of Lemma 5.3, ker(ζk,ℓP(Ω)) = {0}. So, to prove Conjecture 2.10 via Lemma 3.2,
we want to have s∗ ∈ hEndℓ,k(P(Ω)) for all s ∈ ΩΩ. It is a pity that what we can have
instead is s∗ ∈ hEndk,ℓ(P(Ω)) for all s ∈ ΩΩ.
For any transformation g on a set Ω, we associate a partition kerΩ(g) of Ω in which two
elements α and β fall into the same part provided αg = βg, and we call kerΩ(g) the kernel
of g. Note that kerΩ(g1g2) = kerΩ(g2)g∗1 for all g1, g2 ∈ T(Ω). For any transformation
semigroup S on Ω, let PS(Ω) stand for the set {kerΩ(s) : s ∈ S} = {kerΩ(IdΩ)s∗ :
s ∈ S}, and call it the kernel partition subposet induced by S. It is clear that PS(Ω)
is invariant under the action of the kernel space S∗. Inheriting the rank function on PΩ,
PS(Ω) is still a valuated poset.
For a permutation group, all its elements have the same kernel. For a transformation
semigroup, the existence of different kernels may make some arguments for permutation
groups invalid. It looks interesting to study the action of the kernel space S∗ on the kernel
partition subposet PS(Ω).
Example 5.4. Consider the Černý automaton C4 = Γ(S,G) as illustrated in Figure 3,
where G = {a, b}. All partitions of {1, 2, 3, 4}, excepting {{0, 2}, {1, 3}} which is dis-
played in red in Figure 3, belong to PS(Ω). One can check that
WS(S∗|PS(Ω),PS(Ω)) = (1, 1, 1, 1)and SS(S∗|PS(Ω),PS(Ω)) = (1, 2, 1, 1),
both of which being unimodal.
668 Ars Math. Contemp. 22 (2022) #P4.09 / 649–674
Example 5.5. Let Ω = {1, . . . , 6} and let S = ⟨r, b⟩ be the transformation semigroup
acting on Ω as defined in Example 2.5. Simple calculations shows that PS(Ω) is given by
{{{1}, {2}, {3}, {4}, {5}, {6}} , {{1, 2}, {3, 4}, {5, 6}} , {{1, 6}, {2, 3}, {4, 5}}} .
One can further check that WS(S∗|PS(Ω),PS(Ω)) = SS(S∗|PS(Ω),PS(Ω)) = (1, 0, 0, 1).
If you delete those 0-entries (equivalently, adjusting the rank function for PS(Ω)), the
resulting sequence (1, 1) is still unimodal.
6 Linear space
6.1 Top-heavy shape
Let n be the size of a nonempty set Ω. Let k and ℓ be two integers satisfying 0 ≤ k ≤
ℓ ≤ n. Let q be a prime power. As q-analogues of the set incidence operator speci-
fied in Equation (3.1), we define two linear transformations Mk,ℓq,n : QP
k
q,n → QP
ℓ
q,n and
Nk,ℓq,n : QA
k
q,n−1 → QA
ℓ
q,n−1 as follows:
(Mk,ℓq,n(f))(Y )
.
=
∑
X≤Y,X∈Pkq,n
f(X),
and
(Nk,ℓq,n(f
′))(Y ′)
.
=
∑
X′≤Y ′,X′∈Akq,n−1
f(X ′),
for all f ∈ QP
k
q,n , Y ∈ Pℓq,n and f ′ ∈ QA
k
q,n−1 , Y ′ ∈ Aℓq,n−1.
Kantor [30, Theorem] obtained a q-analogue of Gottlieb’s Theorem [25, Corollary 2],
which implies that Conjecture 3.4 holds for affine/projective geometries.
Lemma 6.1 (Kantor). Let n be a positive integer. Let k and ℓ be two nonnegative integers
such that k ≤ ℓ ≤ k + ℓ ≤ n and let q be any prime power. Then both Mk,ℓq,n and N
k,ℓ
q,n−1
are injective.
Proof of Theorem 2.12. Let k and ℓ be two integers such that 0 ≤ k ≤ ℓ ≤ k + ℓ ≤ n.
Note that SP ⊆ hEndk,ℓ(Pq,n) and TA ⊆ hEndk,ℓ(Aq,n−1). Since both Pq,n and Aq,n−1
are (ℓ, k)-finite, the result follows readily from Lemmas 3.2, 3.6 and 6.1.
6.2 Duality: A result of Stanley
First Proof of Theorem 2.16. Let F be a field and Ω be a set. For each linear subspace
U ≤ FΩ, let U⊥ be the subspace of FΩ given by
U⊥
.
= {f ∈ FΩ :
∑
ω∈Ω
f(ω)g(ω) = 0 for all g ∈ U}.
Take a matrix A ∈ FΩ×Ω and record its transpose by A⊤. For any f ∈ FΩ, which
can be thought of as a row vector indexed by Ω, the image of f under the action of A,
written as fA, can be thought of as the product of the row vector f and the matrix A.
The matrix A induces a transformation  on Gr(FΩ) such that U ∈ Gr(FΩ) is sent to
Y. Wu and Y. Zhu: Top-heavy phenomena for transformations 669
f Mk,ℓq,n(f)
fg‡,k Mk,ℓq,n(fg
‡,k)
Mk,ℓq,n
g‡,k
Mk,ℓq,n
g‡,ℓ
Figure 6: The incidence operator intertwines with every linear isomorphism g.
UÂ
.
= {fA : f ∈ U}. It is easy to see that for any U,W ∈ Gr(V ) we have the
implication
UÂ =W =⇒W⊥Â⊤ ≤ U⊥; (6.1)
especially, when A ∈ GLn(F ) it holds
UÂ =W ⇐⇒W⊥Â⊤ = U⊥. (6.2)
According to Taussky and Zassenhaus [63, Theorem 1], we can find P ∈ GLn(F ) such
that P = P⊤ and A⊤ = PAP−1. This means that Equations (6.1), (6.2) become
UÂ =W =⇒ (W⊥P̂ )Â ≤ U⊥P̂
and
UÂ =W ⇐⇒ (W⊥P̂ )Â = U⊥P̂ , (6.3)
respectively. It is well-known that q-binomial coefficients (Gaussian coefficients) occur
in pairs, namely in any n-dimensional linear space over a finite field, the number of k-
dimensional subspaces is equal to the number of (n − k)-dimensional subspaces [24,
Proposition 5.31] [60, Section 3]. In general, as a consequence of Equation 6.3, for any
A ∈ GLn(F ), the number of k-dimension subspaces of Fn fixed by  equals to the num-
ber of (n − k)-dimension subspaces of Fn fixed by Â. If F is a finite field and G is a
subgroup of GLn(F ), in view of the Orbit Counting Lemma (also known as Burnside’s
Lemma), the above discussion leads to a proof of Theorem 2.16.
Second Proof of Theorem 2.16. LetG ≤ GLn(Fq) and let k be a positive integer fulfilling
k ≤ n2 . The group G can be seen as a permutation group acting on both Gr(n− k,F
n
q ) =
Pkq,n and Gr(n− k,Fnq ) = Pn−kq,n ; we use Wk and Wn−k for the two permutation modules
accordingly. From Lemma 6.1, we see that Mk,n−kq,n is an Fq-linear isomorphism from
Pkq,n to Pn−kq,n . From Figure 5 and Example 3.7, we have the commutative diagram in
Figure 6 for 2 ≤ k ≤ n2 ; assuming that g comes from the group G, clearly our deduction
of Figure 5 shows that Figure 6 is also valid for k = 1. This then shows that Wk and Wn−k
are isomorphic permutation modules for G. In particular, the number of orbits of G on
Pkq,n and the number of its orbits on Pn−kq,n must be equal.
By examining the proofs of Theorem 2.16, we intend to understand the challenge of
extending some results on group actions to that on semigroup actions. The above two
670 Ars Math. Contemp. 22 (2022) #P4.09 / 649–674
proofs apply to a set of invertible linear operators over finite linear spaces. If we have a
single linear operator A ∈ Matn(F ), by considering its action on the linear space obtained
by “collapsing” the eventual kernel of A to zero, we may somehow still say something
similar to above. When we have a subsemigroup S of the full linear transformation monoid
acting on a finite linear space, different elements of S may have different eventual kernels
and that makes it nontrivial to glean global information about the semigroup action.
7 Vámos matroid
Proof of Example 2.18. A simple calculation shows that ker(ζk,ℓF(M)) = {0} for (k, ℓ) ∈
{(1, 2), (2, 3)}. Let f ∈ S and let f ′ : F(M) → F(M) be the map sending each flat
X ∈ F(M) to the minimum flat containing Xf in M . By Lemma 3.2, we will be done if
we can show that f ′ ∈ hEndℓ,k(F(M)) for (k, ℓ) = (1, 2), (2, 3).
If we know that f is a bijection or that |EMf | ≤ 2, we can easily check that f ′ ∈
hEndℓ,k(F(M)), as wanted. We intend to find a contradiction under the hypothesis that
neither of them holds.
By assumption, we can take three distinct elements x, y, z in EMf such that |xf−1| ≥
2. Let A be the minimum flat containing {x, y, z} and let B = Af−1. Observe that
|A| ∈ {3, 4}. Since f is a strong map, B is a flat containing at least four elements and so
|B| ∈ {4, 8}.
CASE 1: |B| = 8.
Take any X ∈
(
A
2
)
. Note that X must be a flat and thus so is Xf−1. Since |EMf | ≥ 3,
we deduce that the flat Xf−1 is not equal to EM and so |Xf−1| ≤ 4. Considering that
|A| ∈ {3, 4}, we find that |A| = 4 and each element in A has two perimages under f . Note
that every element in
(
A
2
)
is a flat. It follows that {Xf−1 : X ∈
(
A
2
)
} is a set of six distinct
flats and each of them contains four elements, which cannot happen for the Vámos matroid
M .
CASE 2: |B| = 4.
Thanks to the assumption of |B| = 4, we see that C = {x, y} is a flat in M satisfying
|Cf−1| = 3. Note that no three-elements subset of any four-elements flat in M can be a
flat. This means thatCf−1 is not a flat, violating the assumption that f is a strong map.
8 Concluding remarks
We have discussed some top-heavy phenomena for transformation semigroups acting on
Boolean semirings, affine/projective geometries, and flat lattice of Vámos matroid; see The-
orems 2.1 and 2.12 and Example 2.18. But some problems remain, say Question 2.2, 2.3
and 2.8, Conjecture 2.10 and Question 2.11, and Question 2.15. Our work relies on various
injectivity results, say Lemmas 4.1, 5.3 and 6.1, which can all be deduced from Theo-
rem 5.1 and Remark 5.2. We may think of Conjecture 3.4 as a natural companion to [28,
Conjecture 7]. Since our results on comparing the number of components inside Pk and
that of Pℓ for various valuated posets P come from the injectivity of the relevant incidence
operators (Lemma 3.2), we indeed have an injective map from components of Pk to that
of Pℓ which respects the poset structure. It is noteworthy that we do not find any general
results on the unimodality of the strong/weak shape of a semigroup action on a valuated
poset. We are wondering if the theory on the Lefschetz properties of commutative graded
Y. Wu and Y. Zhu: Top-heavy phenomena for transformations 671
algebras [27] will be useful in this line of research.
Penttila and Siciliano [47, Lemma 3.1] suggested a machinery (Lemma 3.6) to remove
certain finiteness assumption. But we do not see any way to solve Question 1.2 and 2.17 by
this means. Since there are many other approaches to go from finite to infinite [53], it will
not be a surprise if Question 1.2 has a positive solution as simple as that for Theorem 2.12.
Here is another such question. By our definition, a valuated poset only has nonnegative
integers as ranks of its elements. We may allow ranks to be any (not necessarily finite)
cardinal number and then examine all the work in this paper again. A few results of this
kinds from the literature have been addressed at the end of Section 2.1.
ORCID iDs
Yaokun Wu https://orcid.org/0000-0002-6811-7067
Yinfeng Zhu https://orcid.org/0000-0003-1724-5250
References
[1] K. Adiprasito, J. Huh and E. Katz, Hodge theory for combinatorial geometries, Ann. of Math.
(2) 188 (2018), 381–452, doi:10.4007/annals.2018.188.2.1.
[2] J. André, J. a. Araújo and P. J. Cameron, The classification of partition homogeneous groups
with applications to semigroup theory, J. Algebra 452 (2016), 288–310, doi:10.1016/j.jalgebra.
2015.12.025.
[3] C. A. Athanasiadis, The symmetric group action on rank-selected posets of injective words,
Order 35 (2018), 47–56, doi:10.1007/s11083-016-9417-9.
[4] L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics With Applications to Ge-
ometry and Computer Science, Department of Computer Science, The University of Chicago,
1992.
[5] A. Bachem and A. Wanka, Separation theorems for oriented matroids, Discrete Math. 70
(1988), 303–310, doi:10.1016/0012-365x(88)90006-4.
[6] M. Baker, Hodge theory in combinatorics, Bull. Am. Math. Soc. (N.S.) 55 (2018), 57–80, doi:
10.1090/bull/1599.
[7] M. Baker and N. Bowler, Matroids over partial hyperstructures, Adv. Math. 343 (2019), 821–
863, doi:10.1016/j.aim.2018.12.004.
[8] M. Benoumhani, Log-concavity of Whitney numbers of Dowling lattices, Adv. in Appl. Math.
22 (1999), 186–189, doi:10.1006/aama.1998.0621.
[9] R. D. Bercov and C. R. Hobby, Permutation groups on unordered sets, Math. Z. 115 (1970),
165–168, doi:10.1007/bf01109854.
[10] A. Björner and T. Ekedahl, On the shape of Bruhat intervals, Ann. of Math. (2) 170 (2009),
799–817, doi:10.4007/annals.2009.170.799.
[11] F. Brenti, Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an
update, in: Jerusalem Combinatorics ’93, Amer. Math. Soc., Providence, RI, volume 178 of
Contemp. Math., pp. 71–89, 1994, doi:10.1090/conm/178/01893.
[12] M. Brown, Weak n-homogeneity implies weak (n− 1)-homogeneity, Proc. Am. Math. Soc. 10
(1959), 644–647, doi:10.2307/2033668.
[13] H. Bruhn, R. Diestel, M. Kriesell, R. Pendavingh and P. Wollan, Axioms for infinite matroids,
Adv. Math. 239 (2013), 18–46, doi:10.1016/j.aim.2013.01.011.
672 Ars Math. Contemp. 22 (2022) #P4.09 / 649–674
[14] V. M. Bukhshtaber, A. M. Vershik, S. A. Evdokimov and I. N. Ponomarenko, Combinatorial
algebras and multivalued involutive groups, Funct. Anal. Its Appl. 30 (1996), 158–162, doi:
10.1007/bf02509502.
[15] P. J. Cameron, Transitivity of permutation groups on unordered sets, Math. Z. 148 (1976),
127–139, doi:10.1007/bf01214702.
[16] P. J. Cameron, Oligomorphic permutation groups, in: Perspectives in mathematical sciences.
II, World Sci. Publ., Hackensack, NJ, volume 8 of Stat. Sci. Interdiscip. Res., pp. 37–61, 2009,
doi:10.1142/9789814273657\ 0003.
[17] A. Chubarev and I. Pinelis, Fundamental theorem of geometry without the 1-to-1 assumption,
Proc. Am. Math. Soc. 127 (1999), 2735–2744, doi:10.1090/s0002-9939-99-05280-6.
[18] D. de Caen, A note on the ranks of set-inclusion matrices, Electron. J. Comb. 8 (2001), Note 5,
2, doi:10.37236/1590.
[19] E. Delucchi and S. Riedel, Group actions on semimatroids, Adv. in Appl. Math. 95 (2018),
199–270, doi:10.1016/j.aam.2017.11.001.
[20] P. Dembowski, Finite Geometries: Reprint of the 1968 Edition, Springer Berlin, Heidelberg,
2012, doi:10.1007/978-3-642-62012-6.
[21] E. Dobson and A. Malnič, Groups that are transitive on all partitions of a given shape, J. Alge-
braic Comb. 42 (2015), 605–617, doi:10.1007/s10801-015-0593-2.
[22] R. Dougherty, C. Freiling and K. Zeger, Networks, matroids, and non-Shannon information
inequalities, IEEE Trans. Inform. Theory 53 (2007), 1949–1969, doi:10.1109/tit.2007.896862.
[23] T. A. Dowling and R. M. Wilson, Whitney number inequalities for geometric lattices, Proc.
Am. Math. Soc. 47 (1975), 504–512, doi:10.2307/2039773.
[24] G. Gordon and J. McNulty, Matroids: A Geometric Introduction, Cambridge University Press,
Cambridge, 2012, doi:10.1017/cbo9781139049443.
[25] D. H. Gottlieb, A certain class of incidence matrices, Proc. Am. Math. Soc. 17 (1966), 1233–
1237, doi:10.2307/2035716.
[26] A. Hajnal, A remark on the homogeneity of infinite permutation groups, Bull. London Math.
Soc. 22 (1990), 529–532, doi:10.1112/blms/22.6.529.
[27] T. Harima, T. Maeno, H. Morita, Y. Numata, A. Wachi and J. Watanabe, The Lefschetz
properties, volume 2080 of Lecture Notes in Mathematics, Springer, Heidelberg, 2013, doi:
10.1007/978-3-642-38206-2.
[28] J. Huh and B. Wang, Enumeration of points, lines, planes, etc, Acta Math. 218 (2017), 297–317,
doi:10.4310/acta.2017.v218.n2.a2.
[29] O. Johnson, I. Kontoyiannis and M. Madiman, Log-concavity, ultra-log-concavity, and a max-
imum entropy property of discrete compound Poisson measures, Discrete Appl. Math. 161
(2013), 1232–1250, doi:10.1016/j.dam.2011.08.025.
[30] W. M. Kantor, On incidence matrices of finite projective and affine spaces, Math. Z. 124 (1972),
315–318, doi:10.1007/bf01113923.
[31] W. M. Kantor, Line-transitive collineation groups of finite projective spaces, Israel J. Math. 14
(1973), 229–235, doi:10.1007/bf02764881.
[32] W. M. Kantor, Homogeneous designs and geometric lattices, J. Comb. Theory Ser. A 38 (1985),
66–74, doi:10.1016/0097-3165(85)90022-6.
[33] J. P. S. Kung, Strong maps, in: Theory of matroids, Cambridge Univ. Press, Cambridge, vol-
ume 26 of Encyclopedia Math. Appl., pp. 224–253, 1986, doi:10.1017/cbo9780511629563.
011.
Y. Wu and Y. Zhu: Top-heavy phenomena for transformations 673
[34] J. P. S. Kung, The Radon transforms of a combinatorial geometry. II. Partition lattices, Adv.
Math. 101 (1993), 114–132, doi:10.1006/aima.1993.1044.
[35] J. P. S. Kung and H. Q. Nguyen, Weak maps, in: Theory of matroids, Cambridge Univ.
Press, Cambridge, volume 26 of Encyclopedia Math. Appl., pp. 254–271, 1986, doi:10.1017/
cbo9780511629563.012.
[36] J. P. S. Kung, G.-C. Rota and C. H. Yan, Combinatorics: the Rota way, Cambridge Mathemat-
ical Library, Cambridge University Press, Cambridge, 2009, doi:10.1017/cbo9780511803895.
[37] E. H. Lieb, Concavity properties and a generating function for Stirling numbers, J. Comb.
Theory. 5 (1968), 203–206, doi:10.1016/s0021-9800(68)80057-2.
[38] D. Livingstone and A. Wagner, Transitivity of finite permutation groups on unordered sets,
Math. Z. 90 (1965), 393–403, doi:10.1007/bf01112361.
[39] W. J. Martin and B. E. Sagan, A new notion of transitivity for groups and sets of permutations,
J. London Math. Soc. (2) 73 (2006), 1–13, doi:10.1112/s0024610705022441.
[40] J. H. Mason, Matroids: unimodal conjectures and Motzkin’s theorem, in: Combinatorics (Proc.
Conf. Combinatorial Math., Math. Inst., Oxford, 1972), 1972 pp. 207–220.
[41] V. B. Mnukhin and I. J. Siemons, On the Livingstone-Wagner theorem, Electron. J. Comb. 11
(2004), Research Paper 29, 8, doi:10.37236/1782.
[42] M. M. Mukhopadhyay and E. Vassiliev, On the Vámos matroid, homogeneous pregeometries
and dense pairs, Australas. J. Comb. 75 (2019), 158–170, https://ajc.maths.uq.edu.
au/?page=get_volumes&volume=75.
[43] Y. Nakashima, A partial generalization of the Livingstone-Wagner theorem, Ars Math. Con-
temp. 2 (2009), 207–215, doi:10.26493/1855-3974.92.46f.
[44] P. M. Neumann, Homogeneity of infinite permutation groups, Bull. London Math. Soc. 20
(1988), 305–312, doi:10.1112/blms/20.4.305.
[45] M. Pankov, Geometry of Semilinear Embeddings: Relations to Graphs and Codes, World Sci-
entific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015, doi:10.1142/9465.
[46] M. Pankov, Apartments preserving transformations of Grassmannians of infinite-dimensional
vector spaces, Linear Algebra Appl. 531 (2017), 498–509, doi:10.1016/j.laa.2017.06.016.
[47] T. Penttila and A. Siciliano, On the incidence map of incidence structures, Ars Math. Contemp.
20 (2021), 51–68, doi:10.26493/1855-3974.1996.db7.
[48] A. Putman, The fundamental theorem of projective geometry, 2010, https://www3.nd.
edu/˜andyp/notes/.
[49] F. P. Ramsey, On a Problem of Formal Logic, Proc. London Math. Soc. (2) 30 (1929), 264–286,
doi:10.1112/plms/s2-30.1.264.
[50] G.-C. Rota, Combinatorial theory, old and new, in: Actes du Congrès International des
Mathématiciens (Nice, 1970), Tome 3, Gauthier-Villars, Paris, pp. 229–233, 1971.
[51] P. Roy, Another proof that weak n-homogeneity implies weak (n−1)-homogeneity, Proc. Am.
Math. Soc. 49 (1975), 515–516, doi:10.2307/2040675.
[52] P. Šemrl, The Optimal Version of Hua’s Fundamental Theorem of Geometry of Rectangu-
lar Matrices, Mem. Am. Math. Soc. 232 (2014), vi+74, https://bookstore.ams.org/
memo-232-1089.
[53] J.-P. Serre, How to use finite fields for problems concerning infinite fields, in: Arithmetic,
Geometry, Cryptography and Coding Theory, Amer. Math. Soc., Providence, RI, volume 487
of Contemp. Math., pp. 183–193, 2009, doi:10.1090/conm/487/09532.
674 Ars Math. Contemp. 22 (2022) #P4.09 / 649–674
[54] P. D. Seymour, On secret-sharing matroids, J. Comb. Theory Ser. B 56 (1992), 69–73, doi:
10.1016/0095-8956(92)90007-k.
[55] S. Shelah and S. Thomas, Homogeneity of infinite permutation groups, Arch. Math. Logic 28
(1989), 143–147, doi:10.1007/bf01633987.
[56] J. Siemons, On partitions and permutation groups on unordered sets, Arch. Math. (Basel) 38
(1982), 391–403, doi:10.1007/bf01304806.
[57] M. T. Stamps, Topological representations of matroid maps, J. Algebraic Comb. 37 (2013),
265–287, doi:10.1007/s10801-012-0366-0.
[58] R. P. Stanley, Two combinatorial applications of the Aleksandrov-Fenchel inequalities, J.
Comb. Theory Ser. A 31 (1981), 56–65, doi:10.1016/0097-3165(81)90053-4.
[59] R. P. Stanley, Some aspects of groups acting on finite posets, J. Comb. Theory Ser. A 32 (1982),
132–161, doi:10.1016/0097-3165(82)90017-6.
[60] R. P. Stanley, GL(n,C) for combinatorialists, in: Surveys in combinatorics (Southampton,
1983), Cambridge Univ. Press, Cambridge, volume 82 of London Math. Soc. Lecture Note Ser.,
pp. 187–199, 1983, https://math.mit.edu/˜rstan/pubs/.
[61] R. P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry,
in: Graph theory and its applications: East and West (Jinan, 1986), New York Acad. Sci., New
York, volume 576 of Ann. New York Acad. Sci., pp. 500–535, 1989, doi:10.1111/j.1749-6632.
1989.tb16434.x.
[62] T. Stokes, Semigroup actions on posets and preimage quasi-orders, Semigroup Forum 85
(2012), 540–558, doi:10.1007/s00233-012-9436-9.
[63] O. Taussky and H. Zassenhaus, On the similarity transformation between a matrix and its
transpose, Pacific J. Math. 9 (1959), 893–896, http://projecteuclid.org/euclid.
pjm/1103039127.
[64] J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press,
Cambridge, 2nd edition, 2001, doi:10.1017/cbo9780511987045.
[65] O. Y. Viro, On basic concepts of tropical geometry, Proc. Steklov Inst. Math. 273 (2011), 252–
282, doi:10.1134/s0081543811040134.
[66] Z.-X. Wan, Geometry of Matrices, World Scientific Publishing Co., Inc., River Edge, NJ, 1996,
doi:10.1142/9789812830234.
[67] Y. Wu, Z. Xu and Y. Zhu, A five-element transformation monoid on labelled trees, European J.
Comb. 80 (2019), 401–415, doi:10.1016/j.ejc.2018.07.014.
[68] Y. Wu and S. Zhao, Incidence matrix and cover matrix of nested interval orders, Electron. J.
Linear Algebra 23 (2012), 43–65, doi:10.13001/1081-3810.1504.