$$L^p$$-Analysis of the Hodge–Dirac Operator Associated with Witten Laplacians on Complete Riemannian Manifolds

We prove R-bisectoriality and boundedness of the \(H^\infty \)-functional calculus in \(L^p\) for all \(1<p<\infty \) for the Hodge–Dirac operator associated with Witten Laplacians on complete Riemannian manifolds with non-negative Bakry–Emery Ricci curvature on k-forms.     

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

Approximation algorithms for the robust facility leasing problem

In this paper, we consider the robust facility leasing problem (RFLE), which is a variant of the well-known facility leasing problem. In this problem, we are given a facility location set, a client location set of cardinality n, time periods \(\{1, 2, \ldots , T\}\) and a nonnegative integer \(q < n\). At each time period t, a subset of clients \(D_{t}\) arrives. There are K lease types for all facilities. Leasing a facility i of a type k at any time period s incurs a leasing cost \(f_i^{k}\) such that facility i is opened at time period s with a lease length \(l_k\). Each client in \(D_t\) can only be assigned to a facility whose open interval contains t. Assigning a client j to a facility i incurs a serving cost \(c_{ij}\). We want to lease some facilities to serve at least \(n-q\) clients such that the total cost including leasing and serving cost is minimized. Using the standard primal–dual technique, we present a 6-approximation algorithm for the RFLE. We further offer a refined 3-approximation algorithm by modifying the phase of constructing an integer primal feasible solution with a careful recognition on the leasing facilities.     

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

Harmonic <Emphasis Type="Italic">p</Emphasis>-forms on Hadamard manifolds with finite total curvature

In the present note, the geometric structures and topological properties of harmonic p-forms on a complete noncompact submanifold \(M^{n}(n\ge 4)\) immersed in Hadamard manifold \(N^{n+m}\) are discussed, where \(M^{n}\) and \(N^{n+m}\) are assumed to have flat normal bundle and pure curvature tensor, respectively. Firstly, under the assumption that \(M^{n}\) satisfies the \((\mathcal {P}_\rho )\) property (i.e., the weighted Poincaré inequality holds on \(M^{n}\)) and the \((p,n-p)\)-curvature of \(N^{n+m}\) is not less than a given negative constant, using Moser iteration, the space of all \(L^{2}\) harmonic p-forms on \(M^{n}\) is proven to have finite dimensions if \(M^{n}\) has finite total curvature. Furthermore, if the total curvature is small enough or \(M^{n}\) has at most Euclidean volume growth, two vanishing theorems are, respectively, established for harmonic p-forms. Note that the two vanishing theorems extend several previous results obtained by H. Z. Lin.     

Newly appointed editors

Let k be a field and \(k(x_0,\ldots ,x_{p-1})\) be the rational function field of p variables over k where p is a prime number. Suppose that \(G=\langle \sigma \rangle \simeq C_p\) acts on \(k(x_0,\ldots ,x_{p-1})\) by k-automorphisms defined as \(\sigma :x_0\mapsto x_1\mapsto \cdots \mapsto x_{p-1}\mapsto x_0\). Denote by P the set of all prime numbers and define \(P_0=\{p\in P:\mathbb {Q}(\zeta _{p-1})\) is of class number one\(\}\) where \(\zeta _n\) a primitive n-th root of unity in \(\mathbb {C}\) for a positive integer n; \(P_0\) is a finite set by Masley and Montgomery (J Reine Angew Math 286/287:248–256, 1976). Theorem. Let k be an algebraic number field and \(P_k=\{p\in P: p\) is ramified in \(k\}\). Then \(k(x_0,\ldots ,x_{p-1})^G\) is not stably rational over k for all \(p\in P\backslash (P_0\cup P_k)\).     

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.     

Subgroups of cyclic groups and values of the Riemann zeta function

Let k be a positive integer, x a large real number, and let \(C_n\) be the cyclic group of order n. For \(k\le n\le x\) we determine the mean average order of the subgroups of \(C_n\) generated by k distinct elements and we give asymptotic results of related averaging functions of the orders of subgroups of cyclic groups. The average order is expressed in terms of Jordan’s totient functions and Stirling numbers of the second kind. We have the following consequence. Let k and x be as above. For \(k\le n\le x\), the mean average proportion of \(C_n\) generated by k distinct elements approaches \(\zeta (k+2)/\zeta (k+1)\) as x grows, where \(\zeta (s)\) is the Riemann zeta function.     

Cliques in $$C_4$$-free graphs of large minimum degree

A graph G is called \(C_4\)-free if it does not contain the cycle \(C_4\) as an induced subgraph. Hubenko, Solymosi and the first author proved (answering a question of Erd?s) a peculiar property of \(C_4\)-free graphs: \(C_4\)-free graphs with n vertices and average degree at least cn contain a complete subgraph (clique) of size at least \(c'n\) (with \(c'= 0.1c^2\)). We prove here better bounds \(\big ({c^2n\over 2+c}\) in general and \((c-1/3)n\) when \( c \le 0.733\big )\) from the stronger assumption that the \(C_4\)-free graphs have minimum degree at least cn. Our main result is a theorem for regular graphs, conjectured in the paper mentioned above: 2k-regular \(C_4\)-free graphs on \(4k+1\) vertices contain a clique of size \(k+1\). This is the best possible as shown by the kth power of the cycle \(C_{4k+1}\).     

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

Monochromatic Solutions for Multi-Term Unknowns

Given integers \(k\ge 2\), \(n \ge 2\), \(m \ge 2\) and \( a_1,a_2,\ldots ,a_m \in {\mathbb {Z}}{\backslash }{\{0\}}\), and let \(f(z)= \sum _{j=0}^{n}c_jz^j\) be a polynomial of integer coefficients with \(c_n>0\) and \((\sum _{i=1}^ma_i)|f(z)\) for some integer z. For a k-coloring of \([N]=\{1,2,\ldots ,N\}\), we say that there is a monochromatic solution of the equation \(a_1x_1+a_2x_2+\cdots +a_mx_m=f(z)\) if there exist pairwise distinct \(x_1,x_2,\ldots ,x_m\in [N]\) all of the same color such that the equation holds for some \(z\in \mathbb {Z}\). Problems of this type are often referred to as Ramsey-type problems. In this paper, it is shown that if \(a_i>0\) for \(1\le i\le m\), then there exists an integer \(N_0=N(k,m,n)\) such that for \(N\ge N_0\), each k-coloring of [N] contains a monochromatic solution \(x_1,x_2,\ldots ,x_m\) of the equation \(a_1x_1+a_2x_2+ \cdots +a_mx_m= f(z)\). Moreover, if n is odd and there are \(a_i\) and \(a_j\) such that \(a_ia_j<0\) for some \(1 \le i\ne j\le m\), then the assertion holds similarly.     

On the gaps between non-zero Fourier coefficients of cusp forms of higher weight

We show that if a modular cuspidal eigenform f of weight 2k is 2-adically close to an elliptic curve \(E/\mathbb {Q}\), which has a cyclic rational 4-isogeny, then n-th Fourier coefficient of f is non-zero in the short interval \((X, X + cX^{\frac{1}{4}})\) for all \(X \gg 0\) and for some \(c > 0\). We use this fact to produce non-CM cuspidal eigenforms f of level \(N>1\) and weight \(k > 2\) such that \(i_f(n) \ll n^{\frac{1}{4}}\) for all \(n \gg 0\).     

Critical vertices in k-connected digraphs

It is proved that every non-complete, finite digraph of connectivity number k has a fragment F containing at most k critical vertices. The following result is a direct consequence: every k-connected, finite digraph D of minimum out- and indegree at least \(2k+ m- 1\) for positive integers k, m has a subdigraph H of minimum outdegree or minimum indegree at least \(m-1\) such that \(D - x\) is k-connected for all \(x \in V(H)\). For \(m = 1\), this implies immediately the existence of a vertex of indegree or outdegree less than 2k in a k-critical, finite digraph, which was proved in Mader (J Comb Theory (B) 53:260–272, 1991).     

Spectral Properties of <Emphasis Type="Italic">k</Emphasis>-Quasi-<Emphasis Type="Italic">M</Emphasis>-hyponormal Operators

In this paper, we study the k-quasi-M-hyponormal operator and mainly prove that if T is a k-quasi-M-hyponormal operator, then \(\sigma _{ja}(T)\backslash \{0\}=\sigma _{a}(T)\backslash \{0\}\), and the spectrum is continuous on the class of all k-quasi-M-hyponormal operators; let \(d_{AB}\in B(B(H))\) denote either the generalized derivation \(\delta _{AB}= L_{A}-R_{B}\) or the elementary operator \(\Delta _{AB} =L_{A}R_{B}- I\), we show that if A and \(B^{*}\) are k-quasi-M-hyponormal operators, then \(d_{AB}\) is polaroid and generalized Weyl’s theorem holds for \(f(d_{AB})\), where f is an analytic function on \(\sigma (d_{AB})\) and f is not constant on each connected component of the open set U containing \(\sigma (d_{AB})\). In additon, we discuss the hyperinvariant subspace problem for k-quasi-M-hyponormal operators.     

Representation of normal bands as semigroups of <Emphasis Type="Italic">k</Emphasis>-bi-ideals of a semiring

Here we show that every normal band N can be embedded into the normal band \(\mathcal {B(S)}\) of all k-bi-ideals, the left part \(N/ \mathcal {R}\) of N into the left normal band \(\mathcal {R(S)}\) of all right k-ideals, the right part \(N/ \mathcal {L}\) of N into the right normal band \(\mathcal {L(S)}\) of all left k-ideals, and the greatest semilattice homomorphic image \(N/ \mathcal {J}\) of N into the semilattice of all k-ideals of a same k-regular and intra k-regular semiring S.     

Algorithms for positive semidefinite factorization

This paper considers the problem of positive semidefinite factorization (PSD factorization), a generalization of exact nonnegative matrix factorization. Given an m-by-n nonnegative matrix X and an integer k, the PSD factorization problem consists in finding, if possible, symmetric k-by-k positive semidefinite matrices \(\{A^1,\ldots ,A^m\}\) and \(\{B^1,\ldots ,B^n\}\) such that \(X_{i,j}=\text {trace}(A^iB^j)\) for \(i=1,\ldots ,m\), and \(j=1,\ldots ,n\). PSD factorization is NP-hard. In this work, we introduce several local optimization schemes to tackle this problem: a fast projected gradient method and two algorithms based on the coordinate descent framework. The main application of PSD factorization is the computation of semidefinite extensions, that is, the representations of polyhedrons as projections of spectrahedra, for which the matrix to be factorized is the slack matrix of the polyhedron. We compare the performance of our algorithms on this class of problems. In particular, we compute the PSD extensions of size \(k=1+ \lceil \log _2(n) \rceil \) for the regular n-gons when \(n=5\), 8 and 10. We also show how to generalize our algorithms to compute the square root rank (which is the size of the factors in a PSD factorization where all factor matrices \(A^i\) and \(B^j\) have rank one) and completely PSD factorizations (which is the special case where the input matrix is symmetric and equality \(A^i=B^i\) is required for all i).     

Packing Chromatic Number of Base-3 Sierpiński Graphs

The packing chromatic number \(\chi _{\rho }(G)\) of a graph G is the smallest integer k such that there exists a k-vertex coloring of G in which any two vertices receiving color i are at distance at least \(i+1\). Let \(S^n\) be the base-3 Sierpiński graph of dimension n. It is proved that \(\chi _{\rho }(S^1) = 3\), \(\chi _{\rho }(S^2) = 5\), \(\chi _{\rho }(S^3) = \chi _{\rho }(S^4) = 7\), and that \(8\le \chi _\rho (S^n) \le 9\) holds for any \(n\ge 5\).     

Complexities of normal bases constructed from Gauss periods

Let q be a power of a prime p, and let \(r=nk+1\) be a prime such that \(r\not \mid q\), where n and k are positive integers. Under a simple condition on q, r and k, a Gauss period of type (n, k) is a normal element of \({\mathbb {F}}_{q}^{n}\) over \({\mathbb {F}}_q\); the complexity of the resulting normal basis of \({\mathbb {F}}_{q}^{n}\) over \({\mathbb {F}}_q\) is denoted by C(n, k; p). Recent works determined C(n, k; p) for \(k\le 7\) and all qualified n and q. In this paper, we show that for any given \(k>0\), C(n, k; p) is given by an explicit formula except for finitely many primes \(r=nk+1\) and the exceptional primes are easily determined. Moreover, we describe an algorithm that allows one to compute C(n, k; p) for the exceptional primes \(r=nk+1\). Our numerical results cover C(n, k; p) for \(k\le 20\) and all qualified n and q.     

The distortion dimension of $$\mathbb $$-rank 1 lattices

Let \(X=G/K\) be a symmetric space of noncompact type and rank \(k\ge 2\). We prove that horospheres in X are Lipschitz \((k-2)\)-connected if their centers are not contained in a proper join factor of the spherical building of X at infinity. As a consequence, the distortion dimension of an irreducible \(\mathbb {Q}\)-rank-1 lattice \(\Gamma \) in a linear, semisimple Lie group G of \(\mathbb R\)-rank k is \(k-1\). That is, given \(m< k-1\), a Lipschitz m-sphere S in (a polyhedral complex quasi-isometric to) \(\Gamma \), and a \((m+1)\)-ball B in X (or G) filling S, there is a \((m+1)\)-ball \(B'\) in \(\Gamma \) filling S such that \({{\mathrm{vol}}}B'\sim {{\mathrm{vol}}}B\). In particular, such arithmetic lattices satisfy Euclidean isoperimetric inequalities up to dimension \(k-1\).