Multivariate weighted renewal functions

Let (X,Y),(X₁,Y₁),(X₂,Y₂),… denote independent positive random vectors with common distribution function F(x,y)=P(X?x,Y?y) with F(x,y)<1 for all x,y. Based on the X_i and the Y_j we construct the sum sequences and respectively. For a double sequence of weighting constants {b(n,m)} we associate a weighted renewal function G(x,y) defined as . The function G(x,y) can be expressed in terms of well-known renewal quantities. The main goal of this paper is to study asymptotic properties of G(x,y). In the one-dimensional case such results have been obtained among others by Omey and Teugels [Weighted renewal functions: a hierarchical approach, Adv. in Appl. Probab. 34 (2002) 394-415.] and Alsmeyer [Some relations between harmonic renewal measures and certain first passage times, Statist. Probab. Letters 12 (1991) 19-27; On generalized renewal measures and certain first passage times, Ann. Probab. 20 (1992) 1229-1247]. Here we prove a multivariate version of the elementary renewal theorem and moreover we obtain a rate of convergence result in this elementary renewal theorem. We close the paper with an application and some concluding remarks. For convenience we prove and formulate the results in the two-dimensional case only.     

An efficient condition for a graph to be Hamiltonian

Let G=(V,E) be a 2-connected simple graph and let d_G(u,v) denote the distance between two vertices u,v in G. In this paper, it is proved: if the inequality d_G(u)+d_G(v)?|V(G)|-1 holds for each pair of vertices u and v with d_G(u,v)=2, then G is Hamiltonian, unless G belongs to an exceptional class of graphs. The latter class is described in this paper. Our result implies the theorem of Ore [Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55]. However, it is not included in the theorem of Fan [New sufficient conditions for cycles in graph, J. Combin. Theory Ser. B 37 (1984) 221-227].     

Disproof of a conjecture in graph reconstruction theory

In his thesis [3] B. D. Thatte conjectured that ifG=G ₁,G ₂,...G _n is a sequence of finitely many simple connected graphs (isomorphic graphs may occur in the sequence) with the same number of vertices and edges then their shuffled edge deck uniquely determines the graph sequence (up to a permutation). In this paper we prove that there are such sequences of graphs with the same shuffled edge deck.This research was partially supported by Hungarian National Foundation of Scientific Research Grant no. 1812     

Limit theory for random coefficient first-order autoregressive process under martingale difference error sequence

Phillips and Magdalinos (2007) [1] gave the asymptotic theory for autoregressive time series with a root of the form ρ_n=1+c/k_n, where k_n is a deterministic sequence. In this paper, an extension to the more general case where the coefficients of an AR(1) model is a random variable and the error sequence is a sequence of martingale differences is discussed. A conditional least squares estimator of the autoregressive coefficient is derived and shown to be asymptotically normal. This extends the result of Phillips and Magdalinos (2007) [1] for stationary and near-stationary cases.     

On the number of limit cycles in small perturbations of a class of hyper-elliptic Hamiltonian systems with one nilpotent saddle

In this paper, we make a complete study on small perturbations of Hamiltonian vector field with a hyper-elliptic Hamiltonian of degree five, which is a Liénard system of the form x^′=y, y^′=Q₁(x)+εyQ₂(x) with Q₁ and Q₂ polynomials of degree respectively 4 and 3. It is shown that this system can undergo degenerated Hopf bifurcation and Poincaré bifurcation, which emerges at most three limit cycles in the plane for sufficiently small positive ε. And the limit cycles can encompass only an equilibrium inside, i.e. the configuration (3,0) of limit cycles can appear for some values of parameters, where (3,0) stands for three limit cycles surrounding an equilibrium and no limit cycles surrounding two equilibria.     

Graphs whose signless Laplacian spectral radius does not exceed the Hoffman limit value

For a graph matrix M, the Hoffman limit value H(M) is the limit (if it exists) of the largest eigenvalue (or, M-index, for short) of M(H_n), where the graph H_n is obtained by attaching a pendant edge to the cycle C_n-1 of length n-1. In spectral graph theory, M is usually either the adjacency matrix A or the Laplacian matrix L or the signless Laplacian matrix Q. The exact values of H(A) and H(L) were first determined by Hoffman and Guo, respectively. Since H_n is bipartite for odd n, we have H(Q)=H(L). All graphs whose A-index is not greater than H(A) were completely described in the literature. In the present paper, we determine all graphs whose Q-index does not exceed H(Q). The results obtained are determinant to describe all graphs whose L-index is not greater then H(L). This is done precisely in Wang et al. (in press) [21].     

On the unlinking conjecture of independent polynomial functions

The celebrated U-conjecture states that under the N_n(0,I_n) distribution of the random vector X=(X₁,…,X_n) in Rⁿ, two polynomials P(X) and Q(X) are unlinkable if they are independent [see Kagan et al., Characterization Problems in Mathematical Statistics, Wiley, New York, 1973]. Some results have been established in this direction, although the original conjecture is yet to be proved in generality. Here, we demonstrate that the conjecture is true in an important special case of the above, where P and Q are convex nonnegative polynomials with P(0)=0.     

Zariski closure and the dimension of the Gaussian low of the product of random matrices. I

Summary We prove the Central Limit Theorem for products of i.i.d. random matrices. The main aim is to find the dimension of the corresponding Gaussian law. It turns out that ifG is the Zariski closure of a group generated by the support of the distribution of our matrices, and ifG is semi-simple, then the dimension of the Gaussian law is equal to the dimension of the diagonal part of Cartan decomposition ofG.In this article we present a detailed exposition of results announced in [GGu]. For reasons explained in the introduction, this part is devoted to the case ofSL(m, ) group. The general semi-simple Lie group will be considered in the second part of the work.The central limit theorem for products of independent random matrices is our main topic, and the results obtained complete to a large extent the general picture of the subject.The proofs rely on methods from two theories. One is the theory of asymptotic behaviour of products of random matrices itself. As usual, the existence of distinct Lyapunov exponents is the most important fact here. The other is the theory of algebraic groups. We want to point out that algebraic language and methods play a very important role in this paper.In fact, this mixture of methods has already been used for the study of Lyapunov exponents in [GM1, GM2, GR3]. We believe that it is impossible to avoid the algebraic approach if one aims to obtain complete and effective answers to natural problems arising in the theory of products of random matrices.In order also to present the general picture of the subject we describe several results which are well known. Some of these can be proven for stationary sequences of matrices, others are true also for infinite dimensional operators (see e.g. [BL, O, GM2, L, R]). But our main concern is with independent matrices, in which case very precise and constructive statements can be obtained.     

Discrete Morse theory for totally non-negative flag varieties

In a seminal 1994 paper Lusztig (1994) [26], Lusztig extended the theory of total positivity by introducing the totally non-negative part (G/P)_?0 of an arbitrary (generalized, partial) flag variety G/P. He referred to this space as a “remarkable polyhedral subspace”, and conjectured a decomposition into cells, which was subsequently proven by the first author Rietsch (1998) [33]. In Williams (2007) [40] the second author made the concrete conjecture that this cell decomposed space is the next best thing to a polyhedron, by conjecturing it to be a regular CW complex that is homeomorphic to a closed ball. In this article we use discrete Morse theory to prove this conjecture up to homotopy-equivalence. Explicitly, we prove that the boundaries of the cells are homotopic to spheres, and the closures of cells are contractible. The latter part generalizes a result of Lusztig's (1998) [28], that (G/P)_?0 - the closure of the top-dimensional cell - is contractible. Concerning our result on the boundaries of cells, even the special case that the boundary of the top-dimensional cell (G/P)_>0 is homotopic to a sphere, is new for all G/P other than projective space.     

Notes on paratopological groups

In this paper, we prove that if a remainder of a non-locally compact paratopological group G   has a _Gδ$G_{\delta }$-diagonal and every compact subset of G is first countable, then G   has a _Gδ$G_{\delta }$-diagonal of infinite rank. This improves a result of Chuan Liu and Shou Lin [Chuan Liu, Shou Lin, Generalized metric spaces with algebraic structure, Topology Appl. 157 (2010) 1966–1974]. We also construct an open continuous homomorphism f from a non-metrizable paratopological group G onto a metrizable topological group H such that the kernel of f is metrizable. This result gives a negative answer to an open problem posed in [A.V. Arhangel?skii, M. Tkachenko, Topological Groups and Related Structures, Atlantis Press, World Scientific, 2008].     

How many random edges make a graph hamiltonian?

A threshold for a graph propertyQ in the scale of random graph spacesG _n,p is ap-band across which the asymptotic probability ofQ jumps from 0 to 1. We locate a sharp threshold for the property of having a hamiltonian path.     

Fundamental solution for the Q-Laplacian and sharp Moser-Trudinger inequality in Carnot groups

For a general Carnot group G with homogeneous dimension Q we prove the existence of a fundamental solution of the Q-Laplacian u_Q and a constant a_Q>0 such that exp(−a_Qu_Q) is a homogeneous norm on G. This implies a representation formula for smooth functions on G which is used to prove the sharp Carnot group version of the celebrated Moser-Trudinger inequality.     

On the roots of independence polynomials of almost all very well-covered graphs

If s_k denotes the number of stable sets of cardinality k in graph G, and α(G) is the size of a maximum stable set, then is the independence polynomial of G [I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Math. 24 (1983) 97-106]. A graph G is very well-covered [O. Favaron, Very well-covered graphs, Discrete Math. 42 (1982) 177-187] if it has no isolated vertices, its order equals 2α(G) and it is well-covered, i.e., all its maximal independent sets are of the same size [M.D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91-98]. For instance, appending a single pendant edge to each vertex of G yields a very well-covered graph, which we denote by G^*. Under certain conditions, any well-covered graph equals G^* for some G [A. Finbow, B. Hartnell, R.J. Nowakowski, A characterization of well-covered graphs of girth 5 or greater, J. Combin. Theory Ser B 57 (1993) 44-68].The root of the smallest modulus of the independence polynomial of any graph is real [J.I. Brown, K. Dilcher, R.J. Nowakowski, Roots of independence polynomials of well-covered graphs, J. Algebraic Combin. 11 (2000) 197-210]. The location of the roots of the independence polynomial in the complex plane, and the multiplicity of the root of the smallest modulus are investigated in a number of articles.In this paper we establish formulae connecting the coefficients of I(G;x) and I(G^*;x), which allow us to show that the number of roots of I(G;x) is equal to the number of roots of I(G^*;x) different from -1, which appears as a root of multiplicity α(G^*)-α(G) for I(G^*;x). We also prove that the real roots of I(G^*;x) are in [-1,-1/2α(G^*)), while for a general graph of order n we show that its roots lie in |z|>1/(2n-1).Hoede and Li [Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994) 219-228] posed the problem of finding graphs that can be uniquely defined by their clique polynomials (clique-unique graphs). Stevanovic [Clique polynomials of threshold graphs, Univ. Beograd Publ. Elektrotehn. Fac., Ser. Mat. 8 (1997) 84-87] proved that threshold graphs are clique-unique. Here, we demonstrate that the independence polynomial distinguishes well-covered spiders among well-covered trees.     

Proof of conjecture involving the second largest signless Laplacian eigenvalue and the index of graphs

Let G = (V, E) be a simple graph. Denote by D(G) the diagonal matrix of its vertex degrees and by A(G) its adjacency matrix. Then the signless Laplacian matrix of G is Q(G) = D(G) + A(G). In [5], Cvetkovi? et al. have given the following conjecture involving the second largest signless Laplacian eigenvalue (q₂) and the index (λ₁) of graph G (see also Aouchiche and Hansen [1]):

     

Limit distribution of a roundoff error

Let [X] and {X} be the integer and the fractional parts of a random variable X. The conditional distribution function F_n(x)=P({X}≤x|[X]=n) for an integer n is investigated. F_n for a large n is regarded as the distribution of a roundoff error in an extremal event. For most well-known continuous distributions, it is shown that F_n converges as n→∞ and three types of limit distributions appear as the limit distribution according to the tail behavior of F.     

The asymptotic distribution of weighted empirical distribution functions

Let G_n denote the empirical distribution based on n independent uniform (0, 1) random variables. The asymptotic distribution of the supremum of weighted discrepancies between G_n(u) and u of the forms 6w_v(u)D_n(u)6 and 6w_v(G_n(u))D_n(u)6, where D_n(u) = G_n(u)?u, w_v(u) = (u(1?u))^?1+v and 0 ? v < $\text{1}\text{2}$ is obtained. Goodness-of-fit tests based on these statistics are shown to be asymptotically sensitive only in the extreme tails of a distribution, which is exactly where such statistics that use a weight function w_v with $\text{1}\text{2}$ ? v ? 1 are insensitive. For this reason weighted discrepancies which use the weight function w_v with 0 ? v < $\text{1}\text{2}$ are potentially applicable in the construction of confidence contours for the extreme tails of a distribution.     

Sandwiching random graphs: universality between random graph models

The goal of this paper is to establish a connection between two classical models of random graphs: the random graph G(n,p) and the random regular graph G_d(n). This connection appears to be very useful in deriving properties of one model from the other and explains why many graph invariants are universal. In particular, one obtains one-line proofs of several highly non-trivial and recent results on G_d(n).