A relation between the Laplacian and signless Laplacian eigenvalues of a graph

Let G be a graph of order n such that \(\sum_{i=0}^{n}(-1)^{i}a_{i}\lambda^{n-i}\) and \(\sum_{i=0}^{n}(-1)^{i}b_{i}\lambda^{n-i}\) are the characteristic polynomials of the signless Laplacian and the Laplacian matrices of G, respectively. We show that a _i ≥b _i for i=0,1,…,n. As a consequence, we prove that for any α, 0<α≤1, if q ₁,…,q _n and μ ₁,…,μ _n are the signless Laplacian and the Laplacian eigenvalues of G, respectively, then \(q_{1}^{\alpha}+\cdots+q_{n}^{\alpha}\geq\mu_{1}^{\alpha}+\cdots+\mu _{n}^{\alpha}\).     

On a vectorized version of a generalized Richardson extrapolation process

Let {x _m } be a vector sequence that satisfies

$$\boldsymbol{x}_{m}\sim \boldsymbol{s}+\sum\limits^{\infty}_{i=1}\alpha_{i} \boldsymbol{g}_{i}(m)\quad\text{as \(m\to\infty\)}, $$

s being the limit or antilimit of {x _m } and \(\{\boldsymbol {g}_{i}(m)\}^{\infty }_{i=1}\) being an asymptotic scale as m → ∞, in the sense that

$$\lim\limits_{m\to\infty}\frac{\|\boldsymbol{g}_{i+1}(m)\|}{\|\boldsymbol{g}_{i}(m)\|}=0,\quad i=1,2,\ldots. $$

The vector sequences \(\{\boldsymbol {g}_{i}(m)\}^{\infty }_{m=0}\), i = 1, 2,…, are known, as well as {x _m }. In this work, we analyze the convergence and convergence acceleration properties of a vectorized version of the generalized Richardson extrapolation process that is defined via the equations

$$\sum\limits^{k}_{i=1}\langle\boldsymbol{y},{\Delta}\boldsymbol{g}_{i}(m)\rangle\widetilde{\alpha}_{i}=\langle\boldsymbol{y},{\Delta}\boldsymbol{x}_{m}\rangle,\quad n\leq m\leq n+k-1;\quad \boldsymbol{s}_{n,k}=\boldsymbol{x}_{n}+\sum\limits^{k}_{i=1}\widetilde{\alpha}_{i}\boldsymbol{g}_{i}(n), $$

s _{n, k} being the approximation to s. Here, y is some nonzero vector, 〈? ,?〉 is an inner product, such that \(\langle \alpha \boldsymbol {a},\beta \boldsymbol {b}\rangle =\overline {\alpha }\beta \langle \boldsymbol {a},\boldsymbol {b}\rangle \), and Δx _m = x _{m + 1}? x _m and Δg _i (m) = g _i (m + 1)?g _i (m). By imposing a minimal number of reasonable additional conditions on the g _i (m), we show that the error s _{n, k} ? s has a full asymptotic expansion as n→∞. We also show that actual convergence acceleration takes place, and we provide a complete classification of it.

     

On Generalized Markoff-Hurwitz-type Equations over Finite Fields

Let N _q denote the number of solutions of the generalized Markoff-Hurwitz-type equation

$a_1x_1^{m_1}+a_2x_2^{m_2}+\cdots+a_nx_n^{m_n}=b\,x_1^{k_1}x_2^{k_2}\cdots x_n^{k_n}$

over the finite field \(\mathbb{F}_{q}\), where m _i ,k _i are positive integers\(,a_{i},b\in \mathbb{F}_{q}^{*}\) for i=1,…,n and n≥2. By introducing and applying augmented degree matrix, we show that if \(\gcd(\sum_{i=1}^{n}k_{i}m/m_{i}-m,q-1)=1\) where m=m ₁ ??? m _n then N _q =q ^n?1+(?1)^n?1. This partially solves one of Carlitz’s problems and generalizes as well as simplifies some results of Baoulina about these type equations.

     

Searching for a Best Least Absolute Deviations Solution of an Overdetermined System of Linear Equations Motivated by Searching for a Best Least Absolute Deviations Hyperplane on the Basis of Given Data

We consider the problem of searching for a best LAD-solution of an overdetermined system of linear equations Xa=z, X∈?^m×n, m≥n, \(\mathbf{a}\in \mathbb{R}^{n}, \mathbf {z}\in\mathbb{R}^{m}\). This problem is equivalent to the problem of determining a best LAD-hyperplane x?a ^T x, x∈? ⁿ on the basis of given data \((\mathbf{x}_{i},z_{i}), \mathbf{x}_{i}= (x_{1}^{(i)},\ldots,x_{n}^{(i)})^{T}\in \mathbb{R}^{n}, z_{i}\in\mathbb{R}, i=1,\ldots,m\), whereby the minimizing functional is of the form

$F(\mathbf{a})=\|\mathbf{z}-\mathbf{Xa}\|_1=\sum_{i=1}^m|z_i-\mathbf {a}^T\mathbf{x}_i|.$

An iterative procedure is constructed as a sequence of weighted median problems, which gives the solution in finitely many steps. A criterion of optimality follows from the fact that the minimizing functional F is convex, and therefore the point a ^?∈? ⁿ is the point of a global minimum of the functional F if and only if 0∈?F(a ^?).

Motivation for the construction of the algorithm was found in a geometrically visible algorithm for determining a best LAD-plane (x,y)?αx+βy, passing through the origin of the coordinate system, on the basis of the data (x _i ,y _i ,z _i ),i=1,…,m.     

Moderate deviation principle for <Emphasis Type="Italic">m</Emphasis>-dependent random variables<Superscript>*</Superscript>

Let {X _n }_n?≥?1 be a sequence of strictly stationary m-dependent random variableswith EX₁ = 0 and \( \mathrm{E}{X}_1^2<\infty \), and let (b _n ) be an increasing sequence of positive numbers such that b _n ?↑?∞ and \( {b}_n/\sqrt{n}\downarrow 0\kern0.5em \mathrm{as}\kern0.5em n\to \infty \). We establish a moderate deviation principle of \( {\left({b}_n\sqrt{n}\right)}^{-1}{\sum}_{i=1}^n{X}_i \) under the condition

$$ \underset{n\to \infty }{\lim \sup}\frac{1}{b_n^2}\log \left[n\mathbf{P}\left(\left|{X}_1\right|>{b}_n\sqrt{n}\right)\right]=-\infty, $$

which is weaker than the classical exponential integrability condition. The results in the present paper weaken the assumptions of Chen [5] and extend partially the results of Eichelsbacher and Löwe [10].     

Entropy numbers and interpolation

This paper settles a long-standing question by showing that in certain circumstances the entropy numbers of a map do not behave well under real interpolation. To do this, lemmas of combinatorial type are established and used to obtain lower bounds for the entropy numbers of a particular diagonal map acting between Lorentz sequence spaces. These lower bounds contradict the estimates from above that would be obtained if the behaviour of entropy numbers under real interpolation was as good as conjectured. The paper also provides sharp two-sided estimates of the entropy number e _n (T) of diagonal operators \({T:l_{p}\rightarrow l_{q}, T(\left( a_{k}\right)_{k=1}^{\infty}) = (( \lambda_{k}a_{k}) _{k=1}^{\infty}) ,}\) where 0 < p < q ≤ ∞ and \({\{\lambda _{i}\}_{i=1}^{\infty}}\) is a non-increasing sequence of non-negative numbers with λ _i  = λ _n for all i ≤ n.     

Generalizations of Schöbi’s Tetrahedral Dissection

Let v ₁,…,v _n be unit vectors in ? ⁿ such that v _i ?v _j =?w for i≠j, where \(-1. The points ∑ _i=1 ⁿ λ _i v _i (1≥λ ₁≥???≥λ _n ≥0) form a “Hill-simplex of the first type,” denoted by \(\mathcal {Q}_{n}(w)\). It was shown by Hadwiger in 1951 that \(\mathcal {Q}_{n}(w)\) is equidissectable with a cube. In 1985, Schöbi gave a three-piece dissection of \(\mathcal {Q}_{3}(w)\) into a triangular prism \(c\mathcal {Q}_{2}(\frac{1}{2})\times I\), where I denotes an interval and \(c=\sqrt{2(w+1)/3}\). In this paper, we generalize Schöbi’s dissection to an n-piece dissection of \(\mathcal {Q}_{n}(w)\) into a prism \(c\mathcal {Q}_{n-1}(\frac{1}{n-1})\times I\), where \(c=\sqrt{(n-1)(w+1)/n}\). Iterating this process leads to a dissection of \(\mathcal {Q}_{n}(w)\) into an n-dimensional rectangular parallelepiped (or “brick”) using at most n! pieces. The complexity of computing the map from \(\mathcal {Q}_{n}(w)\) to the brick is O(n ²). A second generalization of Schöbi’s dissection is given which applies specifically in ?⁴. The results have applications to source coding and to constant-weight binary codes.     

A Refinement of the Kolmogorov–Marcinkiewicz–Zygmund Strong Law of Large Numbers

Let {X _n ; n≥1} be a sequence of independent copies of a real-valued random variable X and set S _n =X ₁+???+X _n , n≥1. This paper is devoted to a refinement of the classical Kolmogorov–Marcinkiewicz–Zygmund strong law of large numbers. We show that for 0<p<2,

$\sum_{n=1}^{\infty}\frac{1}{n}\biggl(\frac{|S_{n}|}{n^{1/p}}\biggr)<\infty\quad \mbox{almost surely}$

if and only if

$\begin{cases}\mathbb{E}|X|^{p}<\infty &; \mbox{if }0 < p < 1,\\\mathbb{E}X=0,\ \sum_{n=1}^{\infty}\frac{|\mathbb{E}XI\{|X|\leq n\}|}{n}<\infty,\mbox{ and }\\\sum_{n=1}^{\infty}\frac{\int_{\min\{u_{n},n\}}^{n}\mathbb{P}(|X|>t)\,dt}{n}<\infty &; \mbox{if }p = 1,\\\mathbb{E}X=0\mbox{ and }\int_{0}^{\infty}\mathbb{P}^{1/p}(|X|>t)\,dt<\infty,&;\mbox{if }1 < p < 2,\end{cases}$

where \(u_{n}=\inf \{t:~\mathbb{P}(|X|>t)<\frac{1}{n}\}\), n≥1. Versions of the above result in a Banach space setting are also presented. To establish these results, we invoke the remarkable Hoffmann-Jørgensen (Stud. Math. 52:159–186, 1974) inequality to obtain some general results for sums of the form \(\sum_{n=1}^{\infty}a_{n}\|\sum_{i=1}^{n}V_{i}\|\) (where {V _n ; n≥1} is a sequence of independent Banach-space-valued random variables, and a _n ≥0, n≥1), which may be of independent interest, but which we apply to \(\sum_{n=1}^{\infty}\frac{1}{n}(\frac{|S_{n}|}{n^{1/p}})\).

     

Relative Tor Functors for Level Modules with Respect to a Semidualizing Bimodule

Let R and S be rings and _S C _R a semidualizing bimodule. We investigate the relative Tor functors \(\text {Tor}_{i}^{\mathcal {M}\mathcal {L}_{C}}(-,-)\) defined via C-level resolutions, and these functors are exactly the relative Tor functors \(\text {Tor}_{i}^{\mathcal {M}\mathcal {F}_{C}}(-,-)\) defined by Salimi, Sather-Wagstaff, Tavasoli and Yassemi provided that S = R is a commutative Noetherian ring. Vanishing of these functors characterizes the finiteness of \(\mathcal {L}_{C}(S)\)-projective dimension. Applications go in two directions. The first is to characterize when every S-module has a monic (or epic) C-level precover (or preenvelope). The second is to give some criteria for the isomorphism \(\text {Tor}_{i}^{\mathcal {M}\mathcal {L}_{C}}(-,-)\cong \text {Tor}_{i}^{\mathcal {M}\mathcal {F}_{C}}(-,-)\) between the bifunctors.     

Inflation of Finite Lattices Along All-or-nothing Sets

We introduce a new generalization of Alan Day’s doubling construction. For ordered sets \(\mathcal {L}\) and \(\mathcal {K}\) and a subset \(E \subseteq \ \leq _{\mathcal {L}}\) we define the ordered set \(\mathcal {L} \star _{E} \mathcal {K}\) arising from inflation of \(\mathcal {L}\) along E by \(\mathcal {K}\). Under the restriction that \(\mathcal {L}\) and \(\mathcal {K}\) are finite lattices, we find those subsets \(E \subseteq \ \leq _{\mathcal {L}}\) such that the ordered set \(\mathcal {L} \star _{E} \mathcal {K}\) is a lattice. Finite lattices that can be constructed in this way are classified in terms of their congruence lattices.A finite lattice is binary cut-through codable if and only if there exists a 0?1 spanning chain \(\left \{\theta _{i}\colon 0 \leq i \leq n \right \}\) in \(Con(\mathcal {L})\) such that the cardinality of the largest block of ?? _i /?? _i?1 is 2 for every i with 1≤i≤n. These are exactly the lattices that can be constructed by inflation from the 1-element lattice using only the 2-element lattice. We investigate the structure of binary cut-through codable lattices and describe an infinite class of lattices that generate binary cut-through codable varieties.     

Asymptotic distribution of critical values

We study the asymptotic distribution of the critical values of f _n as n goes to infinity. Let X be a closed manifold and \({f:X \times X \to \mathbb{R}}\) be a smooth function. Define \({f_n : X^{n+1} \to \mathbb{R}}\) by \({f_n(x_1, \ldots, x_{n+1}) := \frac{1}{n}\sum f(x_i, x_{i+1})}\) .     

Asymptotic Analysis for Random Walks with Nonidentically Distributed Jumps Having Finite Variance

Let ξ₁,ξ₂,... be independent random variables with distributions F₁F₂,... in a triangular array scheme (F _i may depend on some parameter). Assume that Eξ _i = 0, Eξ _i ² < ∞, and put \(S_n = \sum {_{i = 1}^n \;} \xi _i ,\;\overline S _n = \max _{k \leqslant n} S_k\). Assuming further that some regularly varying functions majorize or minorize the “averaged” distribution \(F = \frac{1}{n}\sum {_{i = 1}^n F_i }\), we find upper and lower bounds for the probabilities P(S _n > x) and \(P(\bar S_n > x)\). We also study the asymptotics of these probabilities and of the probabilities that a trajectory {S _k } crosses the remote boundary {g(k)}; that is, the asymptotics of P(max_k≤n(S _k ? g(k)) > 0). The case n = ∞ is not excluded. We also estimate the distribution of the first crossing time.     

Orthogonal Polynomials Associated with Equilibrium Measures on $\mathbb {R}$

Let K be a non-polar compact subset of \(\mathbb {R}\) and μ _K denote the equilibrium measure of K. Furthermore, let P _n (?;μ _K ) be the n-th monic orthogonal polynomial for μ _K . It is shown that \(\|P_{n}\left (\cdot ; \mu _{K}\right )\|_{L^{2}(\mu _{K})}\), the Hilbert norm of P _n (?;μ _K ) in L ²(μ _K ), is bounded below by Cap(K) ⁿ for each \(n\in \mathbb {N}\). A sufficient condition is given for\(\left (\|P_{n}\left (\cdot ;\mu _{K}\right )\|_{L^{2}(\mu _{K})}/\text {Cap}(K)^{n}\right )_{n=1}^{\infty }\) to be unbounded. More detailed results are presented for sets which are union of finitely many intervals.     

Geometric Realizations of Lusztig’s Symmetries of Symmetrizable Quantum Groups

Let U be the quantum group and f be the Lusztig’s algebra associated with a symmetrizable generalized Cartan matrix. The algebra f can be viewed as the positive part of U. Lusztig introduced some symmetries T _i on U for all i ∈ I. Since T _i (f) is not contained in f, Lusztig considered two subalgebras _i f and ⁱ f of f for any i ∈ I, where _i f={x ∈ f | T _i (x) ∈ f} and \({^{i}\mathbf {f}}=\{x\in \mathbf {f}\,\,|\,\,T^{-1}_{i}(x)\in \mathbf {f}\}\). The restriction of T _i on _i f is also denoted by \(T_{i}:{_{i}\mathbf {f}}\rightarrow {^{i}\mathbf {f}}\). The geometric realization of f and its canonical basis are introduced by Lusztig via some semisimple complexes on the variety consisting of representations of the corresponding quiver. When the generalized Cartan matrix is symmetric, Xiao and Zhao gave geometric realizations of Lusztig’s symmetries in the sense of Lusztig. In this paper, we shall generalize this result and give geometric realizations of _i f, ⁱ f and \(T_{i}:{_{i}\mathbf {f}}\rightarrow {^{i}\mathbf {f}}\) by using the language ’quiver with automorphism’ introduced by Lusztig.     

Minimal polynomial and reduced rank extrapolation methods are related

Minimal Polynomial Extrapolation (MPE) and Reduced Rank Extrapolation (RRE) are two polynomial methods used for accelerating the convergence of sequences of vectors {x _m }. They are applied successfully in conjunction with fixed-point iterative schemes in the solution of large and sparse systems of linear and nonlinear equations in different disciplines of science and engineering. Both methods produce approximations s _k to the limit or antilimit of {x _m } that are of the form \(\boldsymbol {s}_{k}={\sum }^{k}_{i=0}\gamma _{i}\boldsymbol {x}_{i}\) with \({\sum }^{k}_{i=0}\gamma _{i}=1\), for some scalars γ _i . The way the two methods are derived suggests that they might, somehow, be related to each other; this has not been explored so far, however. In this work, we tackle this issue and show that the vectors \(\boldsymbol {s}_{k}^{\textit {{\tiny {MPE}}}}\) and \(\boldsymbol {s}_{k}^{\textit {{\tiny {RRE}}}}\) produced by the two methods are related in more than one way, and independently of the way the x _m are generated. One of our results states that RRE stagnates, in the sense that \(\boldsymbol {s}_{k}^{\textit {{\tiny {RRE}}}}=\boldsymbol {s}_{k-1}^{\textit {{\tiny {RRE}}}}\), if and only if \(\boldsymbol {s}_{k}^{\textit {{\tiny {MPE}}}}\) does not exist. Another result states that, when \(\boldsymbol {s}_{k}^{\textit {{\tiny {MPE}}}}\) exists, there holds

$$\mu_{k}\boldsymbol{s}_{k}^{\textit{{\tiny{RRE}}}}=\mu_{k-1}\boldsymbol{s}_{k-1}^{\textit{{\tiny{RRE}}}}+ \nu_{k}\boldsymbol{s}_{k}^{\textit{{\tiny{MPE}}}}\quad \text{with}\quad \mu_{k}=\mu_{k-1}+\nu_{k}, $$

for some positive scalars μ _k , μ _k?1, and ν _k that depend only on \(\boldsymbol {s}_{k}^{\textit {{\tiny {RRE}}}}\), \(\boldsymbol {s}_{k-1}^{\textit {{\tiny {RRE}}}}\), and \(\boldsymbol {s}_{k}^{\textit {{\tiny {MPE}}}}\), respectively. Our results are valid when MPE and RRE are defined in any weighted inner product and the norm induced by it. They also contain as special cases the known results pertaining to the connection between the method of Arnoldi and the method of generalized minimal residuals, two important Krylov subspace methods for solving nonsingular linear systems.

     

On the exceptional sets in Sylvester expansions*

For any x ?? (0, 1], let the series \( {\sum}_{n=1}^{\infty }1/{d}_n(x) \) be the Sylvester expansion of x, where {d _j (x),?j?≥?1} is a sequence of positive integers satisfying d₁(x)?≥?2 and d_j?+?1(x)?≥?d _j (x)(d _j (x)???1)?+?1 for j?≥?1. Suppose ? : ? → ?⁺ is a function satisfying ?(n+1) – ? (n) → ∞ as n → ∞. In this paper, we consider the set

$$ E\left(\phi \right)=\left\{x\kern0.5em \in \left(0,1\right]:\kern0.5em \underset{n\to \infty }{\lim}\frac{\log {d}_n(x)-{\sum}_{j=1}^{n-1}\log {d}_j(x)}{\phi (n)}=1\right\} $$

and quantify the size of the set in the sense of Hausdorff dimension. As applications, for any β > 1 and γ > 0, we get the Hausdorff dimension of the set \( \left\{x\in \kern1em \left(0,1\right]:\kern0.5em {\lim}_{n\to \infty}\left(\log {d}_n(x)-{\sum}_{j=1}^{n-1}\log {d}_j(x)\right)/{n}^{\beta }=\upgamma \right\}, \) and for any τ > 1 and η > 0, we get a lower bound of the Hausdorff dimension of the set \( \left\{x\kern0.5em \in \kern0.5em \left(0,1\right]:\kern1em {\lim}_{n\to \infty}\left(\log {d}_n(x)-{\sum}_{j=1}^{n-1}\log {d}_j(x)\right)/{\tau}^n=\eta \right\}. \)     

Some Hecke algebra products and corresponding random walks

Let i=1+q+???+q ^i?1. For certain sequences (r ₁,…,r _l ) of positive integers, we show that in the Hecke algebra ? _n (q) of the symmetric group \(\mathfrak{S}_{n}\), the product \((1+\boldsymbol{r}_{\boldsymbol{1}}T_{r_{1}})\cdots (1+\boldsymbol{r}_{\boldsymbol{l}}T_{r_{l}})\) has a simple explicit expansion in terms of the standard basis {T _w }. An interpretation is given in terms of random walks on \(\mathfrak{S}_{n}\).     

Congruences modulo 16, 32, and 64 for Andrews’s singular overpartitions

In a recent work, Andrews gave a definition of combinatorial objects which he called singular overpartitions and proved that these singular overpartitions, which depend on two parameters k and i, can be enumerated by the function \(\overline{C}_{k,i}(n) \) which denotes the number of overpartitions of n in which no part is divisible by k and only parts \(\equiv \pm i \ (\mathrm{mod}\ k)\) may be overlined. Andrews, Chen, Hirschhorn and Sellers, and Ahmed and Baruah discovered numerous congruences modulo 2, 3, 4, 8, and 9 for \(\overline{C}_{3,1}(n)\). In this paper, we prove a number of congruences modulo 16, 32, and 64 for \(\overline{C}_{3,1}(n)\).     

Theorems on Large Deviations for Randomly Indexed Sum of Weighted Random Variables

In this paper, we consider a random variable \(Z_{t}=\sum_{i=1}^{N_{t}}a_{i}X_{i}\), where \(X, X_{1}, X_{2}, \ldots\) are independent identically distributed random variables with mean E X=μ and variance D X=σ ²>0. It is assumed that Z ₀=0, 0≤a _i <∞, and N _t , t≥0 is a non-negative integer-valued random variable independent of X _i , i=1,2,…?. The paper is devoted to the analysis of accuracy of the standard normal approximation to the sum \(\tilde{Z}_{t}=(\mathbf{D}Z_{t})^{-1/2}(Z_{t}-\mathbf{E}Z_{t})\), large deviation theorems in the Cramer and power Linnik zones, and exponential inequalities for \(\mathbf{P}(\tilde{Z}_{t}\geq x)\).     

Refined Self-normalized Large Deviations for Independent Random Variables

Let X ₁,X ₂,…?, be independent random variables with EX _i =0 and write \(S_{n}=\sum_{i=1}^{n}X_{i}\) and \(V_{n}^{2}=\sum_{i=1}^{n}X_{i}^{2}\). This paper provides new refined results on the Cramér-type large deviation for the so-called self-normalized sum S _n /V _n . The major techniques used to derive these new findings are different from those used previously.