Sandwich semigroups in locally small categories I: foundations

Fix (not necessarily distinct) objects i and j of a locally small category S, and write \(S_{ij}\) for the set of all morphisms \(i\rightarrow j\). Fix a morphism \(a\in S_{ji}\), and define an operation \(\star _a\) on \(S_{ij}\) by \(x\star _ay=xay\) for all \(x,y\in S_{ij}\). Then \((S_{ij},\star _a)\) is a semigroup, known as a sandwich semigroup, and denoted by \(S_{ij}^a\). This article develops a general theory of sandwich semigroups in locally small categories. We begin with structural issues such as regularity, Green’s relations and stability, focusing on the relationships between these properties on \(S_{ij}^a\) and the whole category S. We then identify a natural condition on a, called sandwich regularity, under which the set \({\text {Reg}}(S_{ij}^a)\) of all regular elements of \(S_{ij}^a\) is a subsemigroup of \(S_{ij}^a\). Under this condition, we carefully analyse the structure of the semigroup \({\text {Reg}}(S_{ij}^a)\), relating it via pullback products to certain regular subsemigroups of \(S_{ii}\) and \(S_{jj}\), and to a certain regular sandwich monoid defined on a subset of \(S_{ji}\); among other things, this allows us to also describe the idempotent-generated subsemigroup \(\mathbb E(S_{ij}^a)\) of \(S_{ij}^a\). We also study combinatorial invariants such as the rank (minimal size of a generating set) of the semigroups \(S_{ij}^a\), \({\text {Reg}}(S_{ij}^a)\) and \(\mathbb E(S_{ij}^a)\); we give lower bounds for these ranks, and in the case of \({\text {Reg}}(S_{ij}^a)\) and \(\mathbb E(S_{ij}^a)\) show that the bounds are sharp under a certain condition we call MI-domination. Applications to concrete categories of transformations and partial transformations are given in Part II.     

Packing chromatic number versus chromatic and clique number

The packing chromatic number \(\chi _{\rho }(G)\) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets \(V_i\), \(i\in [k]\), where each \(V_i\) is an i-packing. In this paper, we investigate for a given triple (a, b, c) of positive integers whether there exists a graph G such that \(\omega (G) = a\), \(\chi (G) = b\), and \(\chi _{\rho }(G) = c\). If so, we say that (a, b, c) is realizable. It is proved that \(b=c\ge 3\) implies \(a=b\), and that triples \((2,k,k+1)\) and \((2,k,k+2)\) are not realizable as soon as \(k\ge 4\). Some of the obtained results are deduced from the bounds proved on the packing chromatic number of the Mycielskian. Moreover, a formula for the independence number of the Mycielskian is given. A lower bound on \(\chi _{\rho }(G)\) in terms of \(\Delta (G)\) and \(\alpha (G)\) is also proved.     

A group of continuous self-maps on a topological groupoid

The group of bisections of groupoids plays an important role in the study of Lie groupoids. In this paper another construction is introduced. Indeed, for a topological groupoid G, the set of all continuous self-maps f on G such that (x, f(x)) is a composable pair for every \(x\in G\), is denoted by \(S_G\). We show that \(S_G\) by a natural binary operation is a monoid. \(S_G(\alpha )\), the group of units in \(S_G\) precisely consists of those \(f\in S_G\) such that the map \(x\mapsto xf(x)\) is a bijection on G. Similar to the group of bisections, \(S_G(\alpha )\) acts on G from the right and on the space of continuous self-maps on G from the left. It is proved that \(S_G(\alpha )\) with the compact- open topology inherited from C(G, G) is a left topological group. For a compact Hausdorff groupoid G it is proved that the group of bisections of \(G^2\) is isomorphic to the group \(S_G(\alpha )\) and the group of transitive bisections of G, \(Bis_T(G)\), is embedded in \(S_G(\alpha )\), where \(G^2\) is the groupoid of all composable pairs.     

Riemannian <Emphasis Type="Italic">M</Emphasis>-spaces with homogeneous geodesics

We investigate homogeneous geodesics in a class of homogeneous spaces called M-spaces, which are defined as follows. Let G / K be a generalized flag manifold with \(K=C(S)=S\times K_1\), where S is a torus in a compact simple Lie group G and \(K_1\) is the semisimple part of K. Then, the associated M-space is the homogeneous space \(G/K_1\). These spaces were introduced and studied by H. C. Wang in 1954. We prove that for various classes of M-spaces the only g.o. metric is the standard metric. For other classes of M-spaces we give either necessary, or necessary and sufficient conditions, so that a G-invariant metric on \(G/K_1\) is a g.o. metric. The analysis is based on properties of the isotropy representation \(\mathfrak {m}=\mathfrak {m}_1\oplus \cdots \oplus \mathfrak {m}_s\) of the flag manifold G / K [as \({{\mathrm{Ad}}}(K)\)-modules].     

The order continuity in ordered algebras

Let A be an ordered algebra with a unit \(\mathbf{e}\) and a cone \(A^+\). The class of order continuous elements \(A_\mathrm{n}\) of A is introduced and studied. If \(A=L(E)\), where E is a Dedekind complete Riesz space, this class coincides with the band \(L_\mathrm{n}(E)\) of all order continuous operators on E. Special subclasses of \(A_\mathrm {n}\) are considered. Firstly, the order ideal \(A_\mathbf{e}\) generated by \(\mathbf{e}\). It is shown that \(A_\mathbf{e}\) can be embedded into the algebra of continuous functions and, in particular, is a commutative subalgebra of A. If A is an ordered Banach algebra with normal cone \(A^+\) then \(A_\mathbf{e}\) is an AM-space and is closed in A. Secondly, the notion of an orthomorphism in the ordered algebra A is introduced. Among others, the conditions under which orthomorphisms are order continuous, are considered. In the second part, the main emphasis will be on the case of an ordered \(C^*\)-algebra A and, in particular, on the case of the algebra B(H), where H is an ordered Hilbert space with self-adjoint cone \(H^+\). If the cone \(A^+\) is normal then every element of \(A_\mathbf{e}\) is hermitian. In H the operations are introduced which coincide with the lattice ones when H is a Riesz space. It is shown that every regular \(T\in B(H)\) is an order continuous element and operators \(T\in (B(H))_I\) have properties which are analogous to the properties of orthomorphisms on Riesz spaces.     

Lower Bounds for Locally Highly Connected Graphs

We propose a conjecture regarding the lower bound for the number of edges in locally k-connected graphs and we prove it for \(k=2\). In particular, we show that every connected locally 2-connected graph is \(M_3\)-rigid. For the special case of surface triangulations, this fact was known before using topological methods. We generalize this result to all locally 2-connected graphs and give a purely combinatorial proof. Our motivation to study locally k-connected graphs comes from lower bound conjectures for flag triangulations of manifolds, and we discuss some more specific problems in this direction.     

Multi-player Last Nim with Passes

We introduce a class of impartial combinatorial games, Multi-player Last Nim with Passes, denoted by MLNim\(^{(s)}(N,n)\): there are N piles of counters which are linearly ordered. In turn, each of n players either removes any positive integer of counters from the last pile, or makes a choice ‘pass’. Once a ‘pass’ option is used, the total number s of passes decreases by 1. When all s passes are used, no player may ever ‘pass’ again. A pass option can be used at any time, up to the penultimate move, but cannot be used at the end of the game. The player who cannot make a move wins the game. The aim is to determine the game values of the positions of MLNim\(^{(s)}(N,n)\) for all integers \(N\ge 1\) and \(n\ge 3\) and \(s\ge 1\). For \(n>N+1\) or \(n=N+1\ge 3\), the game values are completely determined for any \(s\ge 1\). For \(3\le n\le N\), the game values are determined for infinitely many triplets (N, n, s). We also present a possible explanation why determining the game values becomes more complicated if \(n\le N\).     

Generalized Bernstein Operators on the Classical Polynomial Spaces

We study generalizations of the classical Bernstein operators on the polynomial spaces \(\mathbb {P}_{n}[a,b]\), where instead of fixing \(\mathbf {1}\) and x, we reproduce exactly \(\mathbf {1}\) and a polynomial \(f_1\), strictly increasing on [a, b]. We prove that for sufficiently large n, there always exist generalized Bernstein operators fixing \(\mathbf {1}\) and \(f_1\). These operators are defined by non-decreasing sequences of nodes precisely when \(f_1^\prime > 0\) on (a, b), but even if \(f_1^\prime \) vanishes somewhere inside (a, b), they converge to the identity.     

Anti-Ramsey Numbers of Graphs with Small Connected Components

The anti-Ramsey number, AR(n, G), for a graph G and an integer \(n\ge |V(G)|\), is defined to be the minimal integer r such that in any edge-colouring of \(K_n\) by at least r colours there is a multicoloured copy of G, namely, a copy of G that each of its edges has a distinct colour. In this paper we determine, for large enough \(n,\, AR(n,L\cup tP_2)\) and \(AR(n,L\cup kP_3)\) for any large enough t and k, and a graph L satisfying some conditions. Consequently, we determine AR(n, G), for large enough n, where G is \(P_3\cup tP_2\) for any \(t\ge 3,\, P_4\cup tP_2\) and \(C_3\cup tP_2\) for any \(t\ge 2,\, kP_3\) for any \(k\ge 3,\, tP_2\cup kP_3\) for any \(t\ge 1,\, k\ge 2\), and \(P_{t+1}\cup kP_3\) for any \(t\ge 3,\, k\ge 1\). Furthermore, we obtain upper and lower bounds for AR(n, G), for large enough n, where G is \(P_{k+1}\cup tP_2\) and \(C_k\cup tP_2\) for any \(k\ge 4,\, t\ge 1\).     

A method to find generators of a semi-simple Lie group via the topology of its flag manifolds

In this paper we continue to develop the topological method to get semigroup generators of semi-simple Lie groups. Consider a subset \(\Gamma \subset G\) that contains a semi-simple subgroup \(G_{1}\) of G. If one can show that \( \Gamma \) does not leave invariant a contractible subset on any flag manifold of G, then \(\Gamma \) generates G if \(\mathrm {Ad}\left( \Gamma \right) \) generates a Zariski dense subgroup of the algebraic group \(\mathrm {Ad}\left( G\right) \). The proof is reduced to check that some specific closed orbits of \(G_{1}\) in the flag manifolds of G are not trivial in the sense of algebraic topology. Here, we consider three different cases of semi-simple Lie groups G and subgroups \(G_{1}\subset G\).     

Semidefinite bounds for nonbinary codes based on quadruples

For nonnegative integers q, n, d, let \(A_q(n,d)\) denote the maximum cardinality of a code of length n over an alphabet [q] with q letters and with minimum distance at least d. We consider the following upper bound on \(A_q(n,d)\). For any k, let \(\mathcal{C}_k\) be the collection of codes of cardinality at most k. Then \(A_q(n,d)\) is at most the maximum value of \(\sum _{v\in [q]^n}x(\{v\})\), where x is a function \(\mathcal{C}_4\rightarrow {\mathbb {R}}_+\) such that \(x(\emptyset )=1\) and \(x(C)=\!0\) if C has minimum distance less than d, and such that the \(\mathcal{C}_2\times \mathcal{C}_2\) matrix \((x(C\cup C'))_{C,C'\in \mathcal{C}_2}\) is positive semidefinite. By the symmetry of the problem, we can apply representation theory to reduce the problem to a semidefinite programming problem with order bounded by a polynomial in n. It yields the new upper bounds \(A_4(6,3)\le 176\), \(A_4(7,3)\le 596\), \(A_4(7,4)\le 155\), \(A_5(7,4)\le 489\), and \(A_5(7,5)\le 87\).     

Universal Cycle Packings and Coverings for <Emphasis Type="Italic">k</Emphasis>-Subsets of an <Emphasis Type="Italic">n</Emphasis>-Set

A cyclic sequence of elements of [n] is an (n, k)-Ucycle packing (respectively, (n, k)-Ucycle covering) if every k-subset of [n] appears in this sequence at most once (resp. at least once) as a subsequence of consecutive terms. Let \(p_{n,k}\) be the length of a longest (n, k)-Ucycle packing and \(c_{n,k}\) the length of a shortest (n, k)-Ucycle covering. We show that, for a fixed \(k,p_{n,k}={n\atopwithdelims ()k}-O(n^{\lfloor k/2\rfloor })\). Moreover, when k is not fixed, we prove that if \(k=k(n)\le n^{\alpha }\), where \(0<\alpha <1/3\), then \(p_{n,k}={n\atopwithdelims ()k}-o({n\atopwithdelims ()k}^\beta )\) and \(c_{n,k}={n\atopwithdelims ()k}+o({n\atopwithdelims ()k}^\beta )\), for some \(\beta <1\). Finally, we show that if \(k=o(n)\), then \(p_{n,k}={n\atopwithdelims ()k}(1-o(1))\).     

Popular edges and dominant matchings

Given a bipartite graph \(G = (A \cup B,E)\) with strict preference lists and given an edge \(e^* \in E\), we ask if there exists a popular matching in G that contains \(e^*\). We call this the popular edge problem. A matching M is popular if there is no matching \(M'\) such that the vertices that prefer \(M'\) to M outnumber those that prefer M to \(M'\). It is known that every stable matching is popular; however G may have no stable matching with the edge \(e^*\). In this paper we identify another natural subclass of popular matchings called “dominant matchings” and show that if there is a popular matching that contains the edge \(e^*\), then there is either a stable matching that contains \(e^*\) or a dominant matching that contains \(e^*\). This allows us to design a linear time algorithm for identifying the set of popular edges. When preference lists are complete, we show an \(O(n^3)\) algorithm to find a popular matching containing a given set of edges or report that none exists, where \(n = |A| + |B|\).     

Coloring Complete and Complete Bipartite Graphs from Random Lists

Assign to each vertex v of the complete graph \(K_n\) on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set \([n] = \{1,\dots , n\}\), where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as \(n \rightarrow \infty \)) of the existence of a proper coloring \(\varphi \) of \(K_n\), such that \(\varphi (v) \in L(v)\) for every vertex v of \(K_n\). We show that this property exhibits a sharp threshold at \(f(n) = \log n\). Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph \(K_{m,n}\) with parts of size m and n, respectively. We show that if \(m = o(\sqrt{n})\), \(f(n) \ge 2 \log n\), and L is a random (f(n), [n])-list assignment for the line graph of \(K_{m,n}\), then with probability tending to 1, as \(n \rightarrow \infty \), there is a proper coloring of the line graph of \(K_{m,n}\) with colors from the lists.     

2-Domination number of generalized Petersen graphs

Let \(G=(V,E)\) be a graph. A subset \(S\subseteq V\) is a k-dominating set of G if each vertex in \(V-S\) is adjacent to at least k vertices in S. The k-domination number of G is the cardinality of the smallest k-dominating set of G. In this paper, we shall prove that the 2-domination number of generalized Petersen graphs \(P(5k+1, 2)\) and \(P(5k+2, 2)\), for \(k>0\), is \(4k+2\) and \(4k+3\), respectively. This proves two conjectures due to Cheng (Ph.D. thesis, National Chiao Tung University, 2013). Moreover, we determine the exact 2-domination number of generalized Petersen graphs P(2k, k) and \(P(5k+4,3)\). Furthermore, we give a good lower and upper bounds on the 2-domination number of generalized Petersen graphs \(P(5k+1, 3), P(5k+2,3)\) and \(P(5k+3, 3).\)     

On the semistability of certain Lazarsfeld–Mukai bundles on abelian surfaces

Let \(X=\mathscr {J}(\widetilde{\mathscr {C}})\), the Jacobian of a genus 2 curve \(\widetilde{\mathscr {C}}\) over \({\mathbb {C}}\), and let Y be the associated Kummer surface. Consider an ample line bundle \(L=\mathscr {O}(m\widetilde{\mathscr {C}})\) on X for an even number m, and its descent to Y, say \(L'\). We show that any dominating component of \({\mathscr {W}}^1_{d}(|L'|)\) corresponds to \(\mu _{L'}\)-stable Lazarsfeld–Mukai bundles on Y. Further, for a smooth curve \(C\in |L|\) and a base-point free \(g^1_d\) on C, say (A, V), we study the \(\mu _L\)-semistability of the rank-2 Lazarsfeld–Mukai bundle associated to (C, (A, V)) on X. Under certain assumptions on C and the \(g^1_d\), we show that the above Lazarsfeld–Mukai bundles are \(\mu _L\)-semistable.     

2-Arc-transitive cyclic covers of $$K_{n,n}$$

In this paper, a complete classification is achieved of all the regular covers of the complete bipartite graphs \(K_{n,n}\) with cyclic covering transformation group, whose fibre-preserving automorphism group acts 2-arc-transitively. All these covers consist of one threefold covers of \(K_{6,6}\), one twofold cover of \(K_{12, 12}\) and one infinite family X(r, p) of p-fold covers of \(K_{p^r,p^r}\) with p a prime and r an integer such that \(p^r\ge 3\). This infinite family X(r, p) can be derived by a very simple and nice voltage assignment f as follows: \(X(r, p)=K_{p^r, p^r}\times _f \mathbb {Z}_p\), where \(K_{p^r, p^r}\) is a complete bipartite graph with the bipartition \(V=\{ \alpha \bigm |\alpha \in V(r,p)\}\cup \{ \alpha '\bigm |\alpha \in V(r,p)\}\) for the r-dimensional vector space V(r, p) over the field of order p and \(f_{\alpha ,\beta '}=\sum _{i=1}^ra_ib_i,\,\, \mathrm{for\,\,all}\,\,\alpha =(a_i)_r, \beta =(b_i)_r\in V(r,p)\).     

New upper bounds for parent-identifying codes and traceability codes

In the last two decades, parent-identifying codes and traceability codes are introduced to prevent copyrighted digital data from unauthorized use. They have important applications in the scenarios like digital fingerprinting and broadcast encryption schemes. A major open problem in this research area is to determine the upper bounds for the cardinalities of these codes. In this paper we will focus on this theme. Consider a code of length N which is defined over an alphabet of size q. Let \(M_{IPPC}(N,q,t)\) and \(M_{TA}(N,q,t)\) denote the maximal cardinalities of t-parent-identifying codes and t-traceability codes, respectively, where t is known as the strength of the codes. We show \(M_{IPPC}(N,q,t)\le rq^{\lceil N/(v-1)\rceil }+(v-1-r)q^{\lfloor N/(v-1)\rfloor }\), where \(v=\lfloor (t/2+1)^2\rfloor \), \(0\le r\le v-2\) and \(N\equiv r \mod (v-1)\). This new bound improves two previously known bounds of Blackburn, and Alon and Stav. On the other hand, \(M_{TA}(N,q,t)\) is still not known for almost all t. In 2010, Blackburn, Etzion and Ng asked whether \(M_{TA}(N,q,t)\le cq^{\lceil N/t^2\rceil }\) or not, where c is a constant depending only on N, and they have shown the only known validity of this bound for \(t=2\). By using some complicated combinatorial counting arguments, we prove this bound for \(t=3\). This is the first non-trivial upper bound in the literature for traceability codes with strength three.     

Erratum to: Abstract commensurability and quasi-isometry classification of hyperbolic surface group amalgams

A fundamental result by Gromov and Thurston asserts that, if M is a closed hyperbolic n-manifold, then the simplicial volume \(\Vert M\Vert \) of M is equal to \(\mathrm{Vol}(M)/v_n\), where \(v_n\) is a constant depending only on the dimension of M. The same result also holds for complete finite-volume hyperbolic manifolds without boundary, while Jungreis proved that the ratio \(\mathrm{Vol}(M)/\Vert M\Vert \) is strictly smaller than \(v_n\) if M is compact with nonempty geodesic boundary. We prove here a quantitative version of Jungreis’ result for \(n\ge 4\), which bounds from below the ratio \(\Vert M\Vert /\mathrm{Vol}(M)\) in terms of the ratio \(\mathrm{Vol}(\partial M)/\mathrm{Vol}(M)\). As a consequence, we show that, for \(n\ge 4\), a sequence \(\{M_i\}\) of compact hyperbolic n-manifolds with geodesic boundary satisfies \(\lim _i \mathrm{Vol}(M_i)/\Vert M_i\Vert =v_n\) if and only if \(\lim _i \mathrm{Vol}(\partial M_i)/\mathrm{Vol}(M_i)=0\). We also provide estimates of the simplicial volume of hyperbolic manifolds with geodesic boundary in dimension 3.     

The non-abelian tensor square of residually finite groups

Let m, n be positive integers and p a prime. We denote by \(\nu (G)\) an extension of the non-abelian tensor square \(G \otimes G\) by \(G \times G\). We prove that if G is a residually finite group satisfying some non-trivial identity \(f \equiv ~1\) and for every \(x,y \in G\) there exists a p-power \(q=q(x,y)\) such that \([x,y^{\varphi }]^q = 1\), then the derived subgroup \(\nu (G)'\) is locally finite (Theorem A). Moreover, we show that if G is a residually finite group in which for every \(x,y \in G\) there exists a p-power \(q=q(x,y)\) dividing \(p^m\) such that \([x,y^{\varphi }]^q\) is left n-Engel, then the non-abelian tensor square \(G \otimes G\) is locally virtually nilpotent (Theorem B).