Accelerating the cubic regularization of Newton’s method on convex problems

In this paper we propose an accelerated version of the cubic regularization of Newton’s method (Nesterov and Polyak, in Math Program 108(1): 177–205, 2006). The original version, used for minimizing a convex function with Lipschitz-continuous Hessian, guarantees a global rate of convergence of order \(O\big({1 \over k^2}\big)\), where k is the iteration counter. Our modified version converges for the same problem class with order \(O\big({1 \over k^3}\big)\), keeping the complexity of each iteration unchanged. We study the complexity of both schemes on different classes of convex problems. In particular, we argue that for the second-order schemes, the class of non-degenerate problems is different from the standard class.     

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

Non-triviality conditions for integer-valued polynomial rings on algebras

Let D be a commutative domain with field of fractions K and let A be a torsion-free D-algebra such that \(A \cap K = D\). The ring of integer-valued polynomials on A with coefficients in K is \( Int _K(A) = \{f \in K[X] \mid f(A) \subseteq A\}\), which generalizes the classic ring \( Int (D) = \{f \in K[X] \mid f(D) \subseteq D\}\) of integer-valued polynomials on D. The condition on \(A \cap K\) implies that \(D[X] \subseteq Int _K(A) \subseteq Int (D)\), and we say that \( Int _K(A)\) is nontrivial if \( Int _K(A) \ne D[X]\). For any integral domain D, we prove that if A is finitely generated as a D-module, then \( Int _K(A)\) is nontrivial if and only if \( Int (D)\) is nontrivial. When A is not necessarily finitely generated but D is Dedekind, we provide necessary and sufficient conditions for \( Int _K(A)\) to be nontrivial. These conditions also allow us to prove that, for D Dedekind, the domain \( Int _K(A)\) has Krull dimension 2.     

Convergence rates of moment-sum-of-squares hierarchies for volume approximation of semialgebraic sets

Moment-sum-of-squares hierarchies of semidefinite programs can be used to approximate the volume of a given compact basic semialgebraic set K. The idea consists of approximating from above the indicator function of K with a sequence of polynomials of increasing degree d, so that the integrals of these polynomials generate a convergence sequence of upper bounds on the volume of K. Under certain assumptions, we show that the asymptotic rate of this convergence is at least \(O(1{/}\log \log d)\) in general and \(O(1 / \log d)\) provided that the semialgebraic set is defined by a single inequality.     

Regularity of powers of bipartite graphs

Let G be a finite simple graph and I(G) denote the corresponding edge ideal. For all \(s \ge 1\), we obtain upper bounds for \({\text {reg}}(I(G)^s)\) for bipartite graphs. We then compare the properties of G and \(G'\), where \(G'\) is the graph associated with the polarization of the ideal \((I(G)^{s+1} : e_1\cdots e_s)\), where \(e_1,\cdots , e_s\) are edges of G. Using these results, we explicitly compute \({\text {reg}}(I(G)^s)\) for several subclasses of bipartite graphs.     

On the eigenvalues and spectral radius of starlike trees

Let \(k\ge 1\) and \(n_1,\ldots ,n_k\ge 1\) be some integers. Let \(S(n_1,\ldots ,n_k)\) be a tree T such that T has a vertex v of degree k and \(T{\setminus } v\) is the disjoint union of the paths \(P_{n_1},\ldots ,P_{n_k}\), that is \(T{\setminus } v\cong P_{n_1}\cup \cdots \cup P_{n_k}\) so that every neighbor of v in T has degree one or two. The tree \(S(n_1,\ldots ,n_k)\) is called starlike tree, a tree with exactly one vertex of degree greater than two, if \(k\ge 3\). In this paper we obtain the eigenvalues of starlike trees. We find some bounds for the largest eigenvalue (for the spectral radius) of starlike trees. In particular we prove that if \(k\ge 4\) and \(n_1,\ldots ,n_k\ge 2\), then \(\frac{k-1}{\sqrt{k-2}}<\lambda _1(S(n_1,\ldots ,n_k))<\frac{k}{\sqrt{k-1}}\), where \(\lambda _1(T)\) is the largest eigenvalue of T. Finally we characterize all starlike trees that all of whose eigenvalues are in the interval \((-2,2)\).     

Line complexity asymptotics of polynomial cellular automata

Cellular automata are discrete dynamical systems that consist of patterns of symbols on a grid, which change according to a locally determined transition rule. In this paper, we will consider cellular automata that arise from polynomial transition rules, where the symbols are integers modulo some prime p. We consider the asymptotic behavior of the line complexity sequence \(a_T(k)\), which counts, for each k, the number of coefficient strings of length k that occur in the automaton. We begin with the modulo 2 case. For a polynomial \(T(x)=c_0+c_1x+\dots +c_nx^n\) with \(c_0,c_n\ne ~0\), we construct odd and even parts of the polynomial from the strings \(0c_1c_3c_5\cdots c_{1+2\lfloor (n-1)/2\rfloor }\) and \(c_0c_2c_4\cdots c_{2\lfloor n/2\rfloor }\), respectively. We prove that \(a_T(k)\) satisfies recursions of a specific form if the odd and even parts of T are relatively prime. We also define the order of such a recursion and show that the property of “having a recursion of some order” is preserved when the transition rule is raised to a positive integer power. Extending to a more general setting, we consider an abstract generating function \(\phi (z)=\sum _{k=1}^\infty \alpha (k)z^k\) which satisfies a functional equation relating \(\phi (z)\) and \(\phi (z^p)\). We show that there is a continuous, piecewise quadratic function f on [1 / p, 1] for which \(\lim _{k\rightarrow \infty }(\alpha (k)/k^2-~f(p^{-\langle \log _p k\rangle })) = 0\) (here \(\langle y\rangle =y-\lfloor y\rfloor \)). We use this result to show that for certain positive integer sequences \(s_k(x)\rightarrow \infty \) with a parameter \(x\in [1/p,1]\), the ratio \(\alpha (s_k(x))/s_k(x)^2\) tends to f(x), and that the limit superior and inferior of \(\alpha (k)/k^2\) are given by the extremal values of f.     

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.     

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

A note on alternating projections for ill-posed semidefinite feasibility problems

We observe that Sturm’s error bounds readily imply that for semidefinite feasibility problems, the method of alternating projections converges at a rate of \(\mathcal {O}\Big (k^{-\frac{1}{2^{d+1}-2}}\Big )\), where d is the singularity degree of the problem—the minimal number of facial reduction iterations needed to induce Slater’s condition. Consequently, for almost all such problems (in the sense of Lebesgue measure), alternating projections converge at a worst-case rate of \(\mathcal {O}\Big (\frac{1}{\sqrt{k}}\Big )\).     

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

Relationships Between the 2-Metric Dimension and the 2-Adjacency Dimension in the Lexicographic Product of Graphs

Given a connected simple graph \(G=(V(G),E(G))\), a set \(S\subseteq V(G)\) is said to be a 2-metric generator for G if and only if for any pair of different vertices \(u,v\in V(G)\), there exist at least two vertices \(w_1,w_2\in S\) such that \(d_G(u,w_i)\ne d_G(v,w_i)\), for every \(i\in \{1,2\}\), where \(d_G(x,y)\) is the length of a shortest path between x and y. The minimum cardinality of a 2-metric generator is the 2-metric dimension of G, denoted by \(\dim _2(G)\). The metric \(d_{G,2}: V(G)\times V(G)\longmapsto {\mathbb {N}}\cup \{0\}\) is defined as \(d_{G,2}(x,y)=\min \{d_G(x,y),2\}\). Now, a set \(S\subseteq V(G)\) is a 2-adjacency generator for G, if for every two vertices \(x,y\in V(G)\) there exist at least two vertices \(w_1,w_2\in S\), such that \(d_{G,2}(x,w_i)\ne d_{G,2}(y,w_i)\) for every \(i\in \{1,2\}\). The minimum cardinality of a 2-adjacency generator is the 2-adjacency dimension of G, denoted by \({\mathrm {adim}}_2(G)\). In this article, we obtain closed formulae for the 2-metric dimension of the lexicographic product \(G\circ H\) of two graphs G and H. Specifically, we show that \(\dim _2(G\circ H)=n\cdot {\mathrm {adim}}_2(H)+f(G,H),\) where \(f(G,H)\ge 0\), and determine all the possible values of f(G, H).     

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.     

The first moment of central values of symmetric square <Emphasis Type="Italic">L</Emphasis>-functions in the weight aspect

We establish an asymptotic formula with arbitrary power saving for the first moment of the symmetric square L-functions \(L(s,\mathrm{sym}^2f)\) at \(s=\frac{1}{2}\) for \(f\in \mathcal {H}_k\) as even \(k\rightarrow \infty \), where \(\mathcal {H}_k\) is an orthogonal basis of weight-k Hecke eigen cusp forms for \(SL(2,\mathbb {Z})\). The approach taken allows us to extract two secondary main terms from the best-known error term \(O(k^{-\frac{1}{2}})\). Moreover, our result exhibits a connection between the symmetric square L-functions and quadratic fields, which is the main theme of Zagier’s work Modular forms whose coefficients involve zeta-functions of quadratic fields in 1977.     

On the L1-convergence and behavior of coefficients of Fourier–Vilenkin series

In this paper, we prove the following statement that is true for both bounded and some type of unbounded Vilenkin systems: for any \( \varepsilon \in (0,1)\), there exists a measurable set \(E\subset [0,1)\) of measure bigger than \(1-\varepsilon \) such that for any function \(f \in L^{1}[0,1)\), it is possible to find a function \(g\in L^{1}[0,1)\) coinciding with f on E, Fourier series of g with respect to Vilenkin system are convergent in \(L^{1}\)-norm and the absolute values of non zero Fourier coefficients of g are monotonically decreasing.     

Structure theorem of the generator of a norm continuous completely positive semigroup: an alternative proof using Bures distance

Here we present an alternative proof using Bures distance that the generator L of a norm continuous completely positive semigroup acting on a \(C^*\)-algebra \({\mathcal {B}}\subset \mathcal B(H)\) has the form \( L(b) = \Psi (b) + k^*b+bk\), \(b\in {\mathcal {B}}\) for some completely positive map \(\Psi :{\mathcal {B}}\rightarrow {\mathcal {B}}(H)\) and \(k\in {\mathcal {B}}(H)\).     

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.     

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

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.