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

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.     

O n ( m n,n, m n,m) relative differe nce sets with $$\text {gcd}( m,n)=1$$gcd( m,n)=1

There has been much research on \((p^{a},p^{b},p^{a},p^{a-b})\) relative difference sets with p a prime, while there are only a few results on (mn, n, mn, m) relative difference sets with \(\text {gcd}(m,n)=1\). The non-existence results on (mn, n, mn, m) relative difference sets with \(\text {gcd}(m,n)=1\) have only been obtained for the following five cases: (1) \(m=p,\ n=q,\ p>q\); (2) \(m=pq,\ n=3,\ p,q>3\); (3) \(m=4,\ n=p\); (4) \(m=2\) and (5) \(n=p\), where p, q are distinct odd primes. For the existence results, there are only four constructions of semi-regular relative difference sets in groups of size not a prime power with the forbidden subgroup having size larger than 2. In this paper, we present some more non-existence results on (mn, n, mn, m) relative difference sets with \(\text {gcd}(m,n)=1\). In particular, our result is a generalization of the main result of Hiramine’s work (J Comb Theory Ser A 117(7):996–1003, 2010). Meanwhile, we give a construction of non-abelian (16q, q, 16q, 16) relative difference sets, where q is a prime power with \(q\equiv 1\pmod {4}\) and \(q>4.2\times 10^{8}\). This is the third known infinite classes of non-abelian semi-regular relative difference sets.     

A normal generating set for the Torelli group of a compact non-orientable surface

For a compact surface S, let \({\mathcal {I}}(S)\) denote the Torelli group of S. For a compact orientable surface \(\Sigma \), \({\mathcal {I}}(\Sigma )\) is generated by two types of mapping classes, called bounding simple closed curve maps (BSCC maps) and bounding pair maps (BP maps) (see Powell in Proc Am Math Soc 68:347–350, 1978; Putman in Geom Topol 11:829–865, 2007). For a non-orientable closed surface N, \({\mathcal {I}}(N)\) is generated by BSCC maps and BP maps (see Hirose and Kobayashi in Fund Math 238:29–51, 2017). In this paper, we give an explicit normal generating set for \({\mathcal {I}}(N_g^b)\), where \(N_g^b\) is a genus-g compact non-orientable surface with b boundary components for \(g\ge 4\) and \(b\ge 1\).     

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.     

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

Maximum scattered linear sets and MRD-codes

The rank of a scattered \({\mathbb F}_q\)-linear set of \({{\mathrm{{PG}}}}(r-1,q^n)\), rn even, is at most rn / 2 as it was proved by Blokhuis and Lavrauw. Existence results and explicit constructions were given for infinitely many values of r, n, q (rn even) for scattered \({\mathbb F}_q\)-linear sets of rank rn / 2. In this paper, we prove that the bound rn / 2 is sharp also in the remaining open cases. Recently Sheekey proved that scattered \({\mathbb F}_q\)-linear sets of \({{\mathrm{{PG}}}}(1,q^n)\) of maximum rank n yield \({\mathbb F}_q\)-linear MRD-codes with dimension 2n and minimum distance \(n-1\). We generalize this result and show that scattered \({\mathbb F}_q\)-linear sets of \({{\mathrm{{PG}}}}(r-1,q^n)\) of maximum rank rn / 2 yield \({\mathbb F}_q\)-linear MRD-codes with dimension rn and minimum distance \(n-1\).     

The primitive idempotents and weight distributions of irreducible constacyclic codes

Let \({\mathbb {F}}_q\) be a finite field with q elements such that \(l^v||(q^t-1)\) and \(\gcd (l,q(q-1))=1\), where l, t are primes and v is a positive integer. In this paper, we give all primitive idempotents in a ring \(\mathbb F_q[x]/\langle x^{l^m}-a\rangle \) for \(a\in {\mathbb {F}}_q^*\). Specially for \(t=2\), we give the weight distributions of all irreducible constacyclic codes and their dual codes of length \(l^m\) over \({\mathbb {F}}_q\).     

Partial permutation decoding for binary linear and $$Z_4$$-linear Hadamard codes

In this paper, s-\({\text {PD}}\)-sets of minimum size \(s+1\) for partial permutation decoding for the binary linear Hadamard code \(H_m\) of length \(2^m\), for all \(m\ge 4\) and \(2 \le s \le \lfloor {\frac{2^m}{1+m}}\rfloor -1\), are constructed. Moreover, recursive constructions to obtain s-\({\text {PD}}\)-sets of size \(l\ge s+1\) for \(H_{m+1}\) of length \(2^{m+1}\), from an s-\({\text {PD}}\)-set of the same size for \(H_m\), are also described. These results are generalized to find s-\({\text {PD}}\)-sets for the \({\mathbb {Z}}_4\)-linear Hadamard codes \(H_{\gamma , \delta }\) of length \(2^m\), \(m=\gamma +2\delta -1\), which are binary Hadamard codes (not necessarily linear) obtained as the Gray map image of quaternary linear codes of type \(2^\gamma 4^\delta \). Specifically, s-PD-sets of minimum size \(s+1\) for \(H_{\gamma , \delta }\), for all \(\delta \ge 3\) and \(2\le s \le \lfloor {\frac{2^{2\delta -2}}{\delta }}\rfloor -1\), are constructed and recursive constructions are described.     

On homogeneous hypersurfaces in $${\mathbb {C}}^3$$

We consider a family \(M_t^n\), with \(n\geqslant 2\), \(t>1\), of real hypersurfaces in a complex affine n-dimensional quadric arising in connection with the classification of homogeneous compact simply connected real-analytic hypersurfaces in  \({\mathbb {C}}^n\) due to Morimoto and Nagano. To finalize their classification, one needs to resolve the problem of the embeddability of \(M_t^n\) in  \({\mathbb {C}}^n\) for \(n=3,7\). In our earlier article we showed that \(M_t^7\) is not embeddable in  \({\mathbb {C}}^7\) for every t and that \(M_t^3\) is embeddable in  \({\mathbb {C}}^3\) for all \(1<t<1+10^{-6}\). In the present paper, we improve on the latter result by showing that the embeddability of \(M_t^3\) in fact takes place for \(1<t<\sqrt{(2+\sqrt{2})/3}\). This is achieved by analyzing the explicit totally real embedding of the sphere \(S^3\) in \({\mathbb {C}}^3\) constructed by Ahern and Rudin. For \(t\geqslant {\sqrt{(2+\sqrt{2})/3}}\), the problem of the embeddability of \(M_t^3\) remains open.     

Relative Difference Sets and Hadamard Matrices from Perfect Quaternionic Arrays

Let \(G=\mathbf{C}_{n_1}\times \cdots \times \mathbf{C}_{n_m}\) be an abelian group of order \(n=n_1\dots n_m\), where each \(\mathbf{C}_{n_t}\) is cyclic of order \(n_t\). We present a correspondence between the (4n, 2, 4n, 2n)-relative difference sets in \(G\times Q_8\) relative to the centre \(Z(Q_8)\) and the perfect arrays of size \(n_1\times \dots \times n_m\) over the quaternionic alphabet \(Q_8\cup qQ_8\), where \(q=(1+i+j+k)/2\). In view of this connection, for \(m=2\) we introduce new families of relative difference sets in \(G\times Q_8\), as well as new families of Williamson and Ito Hadamard matrices with G-invariant components.     

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

Combinatorial constructions of optimal (<Emphasis Type="Italic">m</Emphasis>, <Emphasis Type="Italic">n</Emphasis>, 4, 2) optical orthogonal signature pattern codes

Optical orthogonal signature pattern codes (OOSPCs) play an important role in a novel type of optical code division multiple access (OCDMA) network for 2-dimensional image transmission. There is a one-to-one correspondence between an \((m, n, w, \lambda )\)-OOSPC and a \((\lambda +1)\)-(mn, w, 1) packing design admitting a point-regular automorphism group isomorphic to \({\mathbb {Z}}_m\times {\mathbb {Z}}_n\). In 2010, Sawa gave the first infinite class of (m, n, 4, 2)-OOSPCs by using S-cyclic Steiner quadruple systems. In this paper, we use various combinatorial designs such as strictly \({\mathbb {Z}}_m\times {\mathbb {Z}}_n\)-invariant s-fan designs, strictly \({\mathbb {Z}}_m\times {\mathbb {Z}}_n\)-invariant G-designs and rotational Steiner quadruple systems to present some constructions for (m, n, 4, 2)-OOSPCs. As a consequence, our new constructions yield more infinite families of optimal (m, n, 4, 2)-OOSPCs. Especially, we see that in some cases an optimal (m, n, 4, 2)-OOSPC can not achieve the Johnson bound. We also use Witt’s inversive planes to obtain optimal \((p, p, p+1, 2)\)-OOSPCs for all primes \(p\ge 3\).     

On the sumsets of exceptional units in $$\mathbb {Z}_n$$

Let R be a commutative ring with \(1\in R\) and \(R^{*}\) be the multiplicative group of its units. In 1969, Nagell introduced the concept of an exceptional unit, namely a unit u such that \(1-u\) is also a unit. Let \({\mathbb {Z}}_n\) be the ring of residue classes modulo n. In this paper, given an integer \(k\ge 2\), we obtain an exact formula for the number of ways to represent each element of \( \mathbb {Z}_n\) as the sum of k exceptional units. This generalizes a recent result of J. W. Sander for the case \(k=2\).     

Semigroups of rectangular matrices under a sandwich operation

Let \({\mathcal {M}}_{mn}={\mathcal {M}}_{mn}({\mathbb {F}})\) denote the set of all \(m\times n\) matrices over a field \({\mathbb {F}}\), and fix some \(n\times m\) matrix \(A\in {\mathcal {M}}_{nm}\). An associative operation \(\star \) may be defined on \({\mathcal {M}}_{mn}\) by \(X\star Y=XAY\) for all \(X,Y\in {\mathcal {M}}_{mn}\), and the resulting sandwich semigroup is denoted \({\mathcal {M}}_{mn}^A={\mathcal {M}}_{mn}^A({\mathbb {F}})\). These semigroups are closely related to Munn rings, which are fundamental tools in the representation theory of finite semigroups. We study \({\mathcal {M}}_{mn}^A\) as well as its subsemigroups \(\hbox {Reg}({\mathcal {M}}_{mn}^A)\) and \({\mathcal {E}}_{mn}^A\) (consisting of all regular elements and products of idempotents, respectively), and the ideals of \(\hbox {Reg}({\mathcal {M}}_{mn}^A)\). Among other results, we characterise the regular elements; determine Green’s relations and preorders; calculate the minimal number of matrices (or idempotent matrices, if applicable) required to generate each semigroup we consider; and classify the isomorphisms between finite sandwich semigroups \({\mathcal {M}}_{mn}^A({\mathbb {F}}_1)\) and \({\mathcal {M}}_{kl}^B({\mathbb {F}}_2)\). Along the way, we develop a general theory of sandwich semigroups in a suitably defined class of partial semigroups related to Ehresmann-style “arrows only” categories; we hope this framework will be useful in studies of sandwich semigroups in other categories. We note that all our results have applications to the variants \({\mathcal {M}}_n^A\) of the full linear monoid \({\mathcal {M}}_n\) (in the case \(m=n\)), and to certain semigroups of linear transformations of restricted range or kernel (in the case that \(\hbox {rank}(A)\) is equal to one of m, n).     

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.     

On commutator of generalized Aluthge transformations and Fuglede–Putnam theorem

Let \(A=U|A|\) be the polar decomposition of A on a complex Hilbert space \({\mathscr {H}}\) and \(0<s,t\). Then \({\widetilde{A}}_{s, t}=|A|^sU|A|^t\) and \({\widetilde{A}}_{s, t}^{(*)}=|A^*|^sU|A^*|^t\) are called the generalized Aluthge transformation and generalized \(*\)-Aluthge transformation of A, respectively. A pair (A, B) of operators is said to have the Fuglede–Putnam property (breifly, the FP-property) if \(AX=XB\) implies \(A^*X=XB^*\) for every operator X. We prove that if (A, B) has the FP-property, then \(({\widetilde{A}}_{s, t},{\widetilde{B}}_{s, t})\) and \((({\widetilde{A}}_{s, t})^{*},({\widetilde{B}}_{s, t})^{*})\) has the FP-property for every \(s,t>0\) with \(s+t=1\). Also, we prove that \(({\widetilde{A}}_{s, t},{\widetilde{B}}_{s, t})\) has the FP-property if and only if \((({\widetilde{A}}_{s, t})^{*},({\widetilde{B}}_{s, t})^{*})\) has the FP-property, where A, B are invertible and \( 0 < s, t \) with \( s + t =1\). Moreover, we prove that if \(0 < s, t\) and \({\widetilde{A}}_{s, t}\) is positive and invertible, then \(\left\| {\widetilde{A}}_{s, t}X-X{\widetilde{A}}_{s, t}\right\| \le \left\| A\right\| ^{2t}\left\| ({\widetilde{A}}_{s, t})^{-1}\right\| \left\| X\right\| \) for every operator X. Also, if \( 0 <s, t\) and X is positive, then \(\left\| |{\widetilde{A}}_{s, t}|^{2r} X-X|{\widetilde{A}}_{s, t}|^{2r}\right\| \le \frac{1}{2}\left\| |A|\right\| ^{2r}\left\| X\right\| \) for every \(r>0\).     

On decomposability of Multilinear sets

We consider the Multilinear set \({\mathcal {S}}\) defined as the set of binary points (x, y) satisfying a collection of multilinear equations of the form \(y_I = \prod _{i \in I} x_i\), \(I \in {\mathcal {I}}\), where \({\mathcal {I}}\) denotes a family of subsets of \(\{1,\ldots , n\}\) of cardinality at least two. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. A great simplification in studying the facial structure of the convex hull of the Multilinear set is possible when \({\mathcal {S}}\) is decomposable into simpler Multilinear sets \({\mathcal {S}}_j\), \(j \in J\); namely, the convex hull of \({\mathcal {S}}\) can be obtained by convexifying each \({\mathcal {S}}_j\), separately. In this paper, we study the decomposability properties of Multilinear sets. Utilizing an equivalent hypergraph representation for Multilinear sets, we derive necessary and sufficient conditions under which \({\mathcal {S}}\) is decomposable into \({\mathcal {S}}_j\), \(j \in J\), based on the structure of pair-wise intersection hypergraphs. Our characterizations unify and extend the existing decomposability results for the Boolean quadric polytope. Finally, we propose a polynomial-time algorithm to optimally decompose a Multilinear set into simpler subsets. Our proposed algorithm can be easily incorporated in branch-and-cut based global solvers as a preprocessing step for cut generation.     

Construction of a (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">n</Emphasis>)-visual cryptography scheme

In this paper we give an explicit construction of basis matrices for a (k, n)-visual cryptography scheme \((k,n){\hbox {-}}\mathrm{VCS}\) for integers k and n with \(2\le k \le n\). In balanced VCS every set of participants with equal cardinality has same relative contrast. The VCS constructed in this paper is a balanced \((k,n){\hbox {-}}\mathrm{VCS}\) for general k. Also we obtain a formula for pixel expansion and relative contrast. We also prove that our construction gives optimal contrast and minimum pixel expansion when \(k=n\) and \(n-1\).