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.     

Families of conditionally approximately convex functions

Let \((G,+)\) be an Abelian topological group, which is also a \(T_{0}\)-space and a Baire space simultaneously, D be an open connected subset of G and \(\alpha : D-D \rightarrow {\mathbb R}\) be a function continuous at zero and such that \(\alpha (0)=0\). We show that if \((f_n)\) is a sequence of continuous functions \(f_n : D \rightarrow {\mathbb R}\) such that \(f_n(z) \le \frac{1}{2} f_n(x)+\frac{1}{2}f(y)+\alpha (x-y)\) for \(n\in {\mathbb N}\) and \(x,y,z\in D\) such that \(2z=x+y\) and if \((f_n)\) is pointwise convergent [bounded] then it is convergent uniformly on compact subsets of D [in the case when G is additionally a separable space, it contains a subsequence which is convergent on compact subsets of D].     

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

New optical orthogonal signature pattern codes with maximum collision parameter 2 and weight 4

Optical orthogonal signature pattern codes (OOSPCs) play an important role in a novel type of optical code-division multiple-access 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 an automorphism group isomorphic to \(\mathbb {Z}_m\times \mathbb {Z}_n\). In 2010, Sawa gave a construction of an (m, n, 4, 2)-OOSPC from a one-factor of Köhler graph of \(\mathbb {Z}_m\times \mathbb {Z}_n\) which contains a unique element of order 2. In this paper, we study the existence of one-factor of Köhler graph of \(\mathbb {Z}_m\times \mathbb {Z}_n\) having three elements of order 2. It is proved that there is a one-factor in the Köhler graph of \(\mathbb {Z}_{2^{\epsilon }p}\times \mathbb {Z}_{2^{\epsilon '}}\) relative to the Sylow 2-subgroup if there is an S-cyclic Steiner quadruple system of order 2p, where \(p\equiv 5\pmod {12}\) is a prime and \(1\le \epsilon ,\epsilon '\le 2\). Using this one-factor, we construct a strictly \(\mathbb {Z}_{2^{\epsilon }p}\times \mathbb {Z}_{2^{\epsilon '}}\)-invariant regular \(G^*(p,2^{\epsilon +\epsilon '},4,3)\) relative to the Sylow 2-subgroup. By using the known S-cyclic SQS(2p) and a recursive construction for strictly \(\mathbb {Z}_{m}\times \mathbb {Z}_{n}\)-invariant regular G-designs, we construct more strictly \(\mathbb {Z}_{m}\times \mathbb {Z}_{n}\)-invariant 3-(mn, 4, 1) packing designs. Consequently, there is an optimal \((2^{\epsilon }m,2^{\epsilon '}n,4,2)\)-OOSPC for any \(\epsilon ,\epsilon '\in \{0,1,2\}\) with \(\epsilon +\epsilon '>0\) and an optimal (6m, 6n, 4, 2)-OOSPC where m, n are odd integers whose all prime divisors from the set \(\{p\equiv 5\pmod {12}:p\) is a prime, \(p<\)1,500,000}.     

Levi Extension Theorems for Meromorphic Functions of Weak Type in Infinite Dimension

The aim of paper is to give some results, that prepare for studying the problem on cross theorems for separately \((\cdot , W)\)-meromorphic functions. Some general versions of extension theorem of Levi type are extended to the classes of meromorphic functions f on \(D \times (\Delta _r {\setminus } \overline{\Delta })\) with values in a locally convex space F. Here, the function f is assumed that, for each \(z \in D_*,\) the function \(f_z = f(z, \cdot )\) has a (F, W)-meromorphic extension to \(\Delta _r,\) where F is either a locally (or sequentially) complete locally convex space or a Fréchet space, the space \(W \subseteq F'\) is separating (or determines boundedness), \(\Delta _r = \{\lambda \in {\mathbb C}: |\lambda | < r\}\) with \(r > 1, \Delta = \Delta _1\) and D is either a domain in \({\mathbb C}^n\) or a balanced domain in a Fréchet space containing a non-pluripolar balanced convex compact subset, \(D_*\) is dense in D.     

Heinz mean curvature estimates in warped product spaces $$M\times _{e^{\psi }}N$$

If a graph submanifold (x, f(x)) of a Riemannian warped product space \((M^m\times _{e^{\psi }}N^n,\tilde{g}=g+ e^{2\psi }h)\) is immersed with parallel mean curvature H, then we obtain a Heinz-type estimation of the mean curvature. Namely, on each compact domain D of M, \(m\Vert H\Vert \le \frac{A_{\psi }(\partial D)}{V_{\psi }(D)}\) holds, where \(A_{\psi }(\partial D)\) and \(V_{\psi }(D)\) are the \({\psi }\)-weighted area and volume, respectively. In particular, \(H=0\) if (M, g) has zero-weighted Cheeger constant, a concept recently introduced by Impera et al. (Height estimates for killing graphs. arXiv:1612.01257, 2016). This generalizes the known cases \(n=1\) or \(\psi =0\). We also conclude minimality using a closed calibration, assuming \((M,g_*)\) is complete where \(g_*=g+e^{2\psi }f^*h\), and for some constants \(\alpha \ge \delta \ge 0\), \(C_1>0\) and \(\beta \in [0,1)\), \(\Vert \nabla ^*\psi \Vert ^2_{g_*}\le \delta \), \(\mathrm {Ricci}_{\psi ,g_*}\ge \alpha \), and \({\mathrm{det}}_g(g_*)\le C_1 r^{2\beta }\) holds when \(r\rightarrow +\infty \), where r(x) is the distance function on \((M,g_*)\) from some fixed point. Both results rely on expressing the squared norm of the mean curvature as a weighted divergence of a suitable vector field.     

On Riesz Transforms Characterization of <Emphasis Type="Italic">H</Emphasis><Superscript>1</Superscript> Spaces Associated with Some Schrödinger Operators

Let \(\mathcal Lf(x)=-\Delta f (x)+V(x)f(x)\), V?≥?0, \(V\in L^1_{loc}(\mathbb R^d)\), be a non-negative self-adjoint Schrödinger operator on \(\mathbb R^d\). We say that an L ¹-function f is an element of the Hardy space \(H^1_{\mathcal L}\) if the maximal function

$ \mathcal M_{\mathcal L} f(x)=\sup\limits_{t>0}|e^{-t\mathcal L} f(x)| $

belongs to \(L^1(\mathbb R^d)\). We prove that under certain assumptions on V the space \(H^1_{\mathcal L}\) is also characterized by the Riesz transforms \(R_j=\frac{\partial}{\partial x_j}\mathcal L^{-1\slash 2}\), j?=?1,...,d, associated with \(\mathcal L\). As an example of such a potential V one can take any V?≥?0, \(V\in L^1_{loc}\), in one dimension.

     

Fractional Differentiability for Solutions of Nonlinear Elliptic Equations

We study nonlinear elliptic equations in divergence form

$$\text {div }{\mathcal A}(x,Du)=\text {div } G.$$

When \({\mathcal A}\) has linear growth in D u, and assuming that \(x\mapsto {\mathcal A}(x,\xi )\) enjoys \(B^{\alpha }_{\frac {n}\alpha , q}\) smoothness, local well-posedness is found in \(B^{\alpha }_{p,q}\) for certain values of \(p\in [2,\frac {n}{\alpha })\) and \(q\in [1,\infty ]\). In the particular case \({\mathcal A}(x,\xi )=A(x)\xi \), G = 0 and \(A\in B^{\alpha }_{\frac {n}\alpha ,q}\), \(1\leq q\leq \infty \), we obtain \(Du\in B^{\alpha }_{p,q}\) for each \(p<\frac {n}\alpha \). Our main tool in the proof is a more general result, that holds also if \({\mathcal A}\) has growth s?1 in D u, 2 ≤ s ≤ n, and asserts local well-posedness in L ^q for each q > s, provided that \(x\mapsto {\mathcal A}(x,\xi )\) satisfies a locally uniform VMO condition.

     

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

Characterization of the Gamma semigroup

The Gamma semigroup with parameter \(b>0\) on \(L^p(\mathbb R^+)\) is defined by

$$\begin{aligned} W_b(t)f(x)=\frac{1}{\Gamma (t)}\int _0^x(x-y)^{t-1}e^{-b(x-y)}f(y)\,dy. \end{aligned}$$

Let S denote the multiplication operator \(f(x)\rightarrow xf(x)\) with maximal domain D(S) in \(L^p(\mathbb R^+)\). The bounded operator V on \(L^p(\mathbb R^+)\) is S-Volterra if D(S) is V-invariant and \([S,V]=V^2\) on D(S). For \(1<p<\infty \), we characterize the Gamma semigroup as the unique regular semigroup \(V(\cdot )\) on \(L^p(\mathbb R^+)\) with imaginary type less than \(\pi \), such that V(1) is S-Volterra and \(V(1)u^b=Su^b\), where \(u^b(x):=e^{-bx}\).

     

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.     

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

Lengths of words in transformation semigroups generated by digraphs

Given a simple digraph D on n vertices (with \(n\ge 2\)), there is a natural construction of a semigroup of transformations \(\langle D\rangle \). For any edge (a, b) of D, let \(a\rightarrow b\) be the idempotent of rank \(n-1\) mapping a to b and fixing all vertices other than a; then, define \(\langle D\rangle \) to be the semigroup generated by \(a \rightarrow b\) for all \((a,b) \in E(D)\). For \(\alpha \in \langle D\rangle \), let \(\ell (D,\alpha )\) be the minimal length of a word in E(D) expressing \(\alpha \). It is well known that the semigroup \(\mathrm {Sing}_n\) of all transformations of rank at most \(n-1\) is generated by its idempotents of rank \(n-1\). When \(D=K_n\) is the complete undirected graph, Howie and Iwahori, independently, obtained a formula to calculate \(\ell (K_n,\alpha )\), for any \(\alpha \in \langle K_n\rangle = \mathrm {Sing}_n\); however, no analogous non-trivial results are known when \(D \ne K_n\). In this paper, we characterise all simple digraphs D such that either \(\ell (D,\alpha )\) is equal to Howie–Iwahori’s formula for all \(\alpha \in \langle D\rangle \), or \(\ell (D,\alpha ) = n - \mathrm {fix}(\alpha )\) for all \(\alpha \in \langle D\rangle \), or \(\ell (D,\alpha ) = n - \mathrm {rk}(\alpha )\) for all \(\alpha \in \langle D\rangle \). We also obtain bounds for \(\ell (D,\alpha )\) when D is an acyclic digraph or a strong tournament (the latter case corresponds to a smallest generating set of idempotents of rank \(n-1\) of \(\mathrm {Sing}_n\)). We finish the paper with a list of conjectures and open problems.     

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

Analytic sets and extension of holomorphic maps of positive codimension

Let D, \(D'\) be arbitrary domains in \({\mathbb C}^n\) and \({\mathbb C}^N\) respectively, \(1<n\le N\), both possibly unbounded and \(M \subseteq \partial D\), \(M'\subseteq \partial D'\) be open pieces of the boundaries. Suppose that \(\partial D\) is smooth real-analytic and minimal in an open neighborhood of \({\bar{M}}\) and \(\partial D'\) is smooth real-algebraic and minimal in an open neighborhood of \({\bar{M}'}\). Let \(f: D\rightarrow D'\) be a holomorphic mapping such that the cluster set \(\mathrm{cl}_{f}(M)\) does not intersect \(D'\). It is proved that if the cluster set \(\mathrm{cl}_{f}(p)\) of some point \(p\in M\) contains some point \(q\in M'\) and the graph of f extends as an analytic set to a neighborhood of \((p, q)\in {\mathbb {C}}^n \times {\mathbb C}^N\), then f extends as a holomorphic map to a dense subset of some neighborhood of p. If in addition, \(M =\partial D\), \(M'=\partial D'\) and \(M'\) is compact, then f extends holomorphically across an open dense subset of \(\partial D\).     

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.     

Couplings of Brownian Motions of Deterministic Distance in Model Spaces of Constant Curvature

We consider the model space \(\mathbb {M}^{n}_{K}\) of constant curvature K and dimension \(n\ge 1\) (Euclidean space for \(K=0\), sphere for \(K>0\) and hyperbolic space for \(K<0\)), and we show that given a function \(\rho :[0,\infty )\rightarrow [0, \infty )\) with \(\rho (0)=\mathrm {dist}(x,y)\) there exists a coadapted coupling (X(t), Y(t)) of Brownian motions on \(\mathbb {M}^{n}_{K}\) starting at (x, y) such that \(\rho (t)=\mathrm {dist}(X(t),Y(t))\) for every \(t\ge 0\) if and only if \(\rho \) is continuous and satisfies for almost every \(t\ge 0\) the differential inequality

$$\begin{aligned} -(n-1)\sqrt{K}\tan \left( \tfrac{\sqrt{K}\rho (t)}{2}\right) \le \rho '(t)\le -(n-1)\sqrt{K}\tan \left( \tfrac{\sqrt{K}\rho (t)}{2}\right) +\tfrac{2(n-1)\sqrt{K}}{\sin (\sqrt{K}\rho (t))}. \end{aligned}$$

In other words, we characterize all coadapted couplings of Brownian motions on the model space \(\mathbb {M}^{n}_{K}\) for which the distance between the processes is deterministic. In addition, the construction of the coupling is explicit for every choice of \(\rho \) satisfying the above hypotheses.

     

Closed range and nonclosed range adjointable operators on Hilbert $$C^*$$-modules

In this paper, we show that for a positive operator A on a Hilbert \(C^*\)-module \( \mathscr {E} \), the range \( \mathscr {R}(A) \) of A is closed if and only if \( \mathscr {R}(A^\alpha ) \) is closed for all \(\alpha \in (0,1)\cup (1,+\,\infty )\), and this occurs if and only if \( \mathscr {R}(A)=\mathscr {R}(A^\alpha ) \) for all \(\alpha \in (0,1)\cup (1,+\,\infty )\). As an application, we prove that for an adjontable operator A if \(\mathscr {R}(A)\) is nonclosed, then \(\dim \left( \overline{\mathscr {R}(A)}/\mathscr {R}(A)\right) =+\,\infty \). Finally, we show that for an adjointable operator A if \( \overline{\mathscr {R}(A^*) } \) is orthogonally complemented in \( \mathscr {E} \), then under certain coditions there exists an idempotent C and a unique operator X such that \( XAX=X, AXA=CA, AX=C \) and \( XA=P_{A^*} \), where \( P_{A^*} \) is the orthogonal projection of \( \mathscr {E} \) onto \( \overline{\mathscr {R}(A^*)}\).     

A geometric approach to alternating <Emphasis Type="Italic">k</Emphasis>-linear forms

Denote by \({{\mathcal {G}}}_k(V)\) the Grassmannian of the k-subspaces of a vector space V over a field \({\mathbb {K}}\). There is a natural correspondence between hyperplanes H of \({\mathcal {G}}_k(V)\) and alternating k-linear forms on V defined up to a scalar multiple. Given a hyperplane H of \({{\mathcal {G}}_k}(V)\), we define a subspace \(R^{\uparrow }(H)\) of \({{\mathcal {G}}_{k-1}}(V)\) whose elements are the \((k-1)\)-subspaces A such that all k-spaces containing A belong to H. When \(n-k\) is even, \(R^{\uparrow }(H)\) might be empty; when \(n-k\) is odd, each element of \({\mathcal {G}}_{k-2}(V)\) is contained in at least one element of \(R^{\uparrow }(H)\). In the present paper, we investigate several properties of \(R^{\uparrow }(H)\), settle some open problems and propose a conjecture.     

Multiplicity Results for the Fractional Laplacian in Expanding Domains

In this paper, we establish a multiplicity result of nontrivial weak solutions for the problem \((-\Delta )^{\alpha } u +u= h(u)\)    in \(\Omega _{\lambda }\), \(u=0\)    on \(\partial \Omega _{\lambda }\), where \(\Omega _{\lambda }=\lambda \Omega \), \(\Omega \) is a smooth and bounded domain in \({\mathbb {R}}^N, N>2\alpha \), \(\lambda \) is a positive parameter, \(\alpha \in (0,1)\), \((-\Delta )^{\alpha }\) is the fractional Laplacian and the nonlinear term h(u) has subcritical growth. We use minimax methods, the Ljusternick–Schnirelmann and Morse theories to get multiplicity results depending on the topology of \(\Omega \).