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
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.