Det‐extremal cubic bipartite graphs

Let G be a connected k–regular bipartite graph with bipartition V(G) = X ∪ Y and adjacency matrix A. We say G is det‐extremal if per (A) = |det(A)|. Det–extremal k–regular bipartite graphs exist only for k = 2 or 3. McCuaig has characterized the det‐extremal 3‐connected cubic bipartite graphs. We extend McCuaig's result by determining the structure of det‐extremal cubic bipartite graphs of connectivity two. We use our results to determine which numbers can occur as orders of det‐extremal connected cubic bipartite graphs, thus solving a problem due to H. Gropp. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 50–64, 2003     

Asymptotic Distribution of Extremes of Randomly Indexed Random Variables

Let {X _n} be a sequence of i.i.d. random variables and let {_k} be a sequence of random indexes. We study the problem of the existence of non-degenerated asymptotic distribution for min{X ₁,..., X _n}.     

Solution of the Ulam stability problem for Euler–Lagrange–Jensen k‐quintic mappings

In this paper, we are introducing pertinent Euler–Lagrange–Jensen type k‐quintic functional equations and investigate the ‘Ulam stability’ of these new k‐quintic functional mappings f:X→Y, where X is a real normed linear space and Y a real complete normed linear space. We also solve the Ulam stability problem for Euler–Lagrange–Jensen alternative k‐quintic mappings. Copyright © 2016 John Wiley & Sons, Ltd.     

Average‐case analyses of first fit and random fit bin packing

We prove that the First Fit bin packing algorithm is stable under the input distribution U{k−2, k} for all k≥3, settling an open question from the recent survey by Coffman, Garey, and Johnson [“Approximation algorithms for bin backing: A survey,” Approximation algorithms for NP‐hard problems, D. Hochbaum (Editor), PWS, Boston, 1996]. Our proof generalizes the multidimensional Markov chain analysis used by Kenyon, Sinclair, and Rabani to prove that Best Fit is also stable under these distributions [Proc Seventh Annual ACM‐SIAM Symposium on Discrete Algorithms, 1995, pp. 351–358]. Our proof is motivated by an analysis of Random Fit, a new simple packing algorithm related to First Fit, that is interesting in its own right. We show that Random Fit is stable under the input distributions U{k−2, k}, as well as present worst case bounds and some results on distributions U{k−1, k} and U{k, k} for Random Fit. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 240–259, 2000     

Tail and dependence behavior of levels that persist for a fixed period of time

This work emerges from a study of the extremal behavior of a daily maximum sea water levels series, {X _i } , presented in Draisma (Duration of extremes at sea. In: Parametric and semi-parametric methods in E. V. T., pp. 137–143. PhD thesis, Erasmus, University, 2001). In its approach, a new series, {Y _i }, is defined, consisting of water levels that persist for a fixed period of time. In this paper, we study the tail behavior of {Y _i } , in case {X _i } is independent and identically distributed (i.i.d.) and in case {X _i } is a max-autoregressive sequence (we will consider two different max-autoregressive processes), whose distribution function is in the Fréchet domain of attraction. We also determine Ledford and Tawn tail dependence index (Ledford and Tawn, Biometrika 83:169–187, 1996, J. R. Stat. Soc. B 59:475–499, 1997) and we analyze the asymptotic tail dependence of the random pair (Y _i , Y _i + m ), in all considered cases. According to Drees (Bernoulli 9:617–657, 2003), we obtain the limit behavior of the tail empirical quantile function associated with a random sample (Y ₁, Y ₂,...Y _n ) and hence the asymptotic normality of a class of estimators of the tail index that includes Hill estimator. Research partially supported by FCT/POCTI and POCI/FEDER.     

On the Extremal Behaviour of Generalised Periodic Sub-Sampled Moving Average Models with Regularly Varying Tails

Let {X_k} be a stationary moving average sequence of the form X_k = _{j = – j}*Z_{k – j} where {Z_k} is an iid sequence of random variables with regularly varying tails, and the operator * denotes multiplication if Z_k is continuous and binomial thinning if Z_k is a non-negative integer-valued. Let be a strictly increasing sequence with a periodic pattern of the form g(k + I) = g(k) + M for some fixed integers I and M verifying 1 I M. Define Y_k = X_g(k) as the generalised periodic sub-sampled moving average sequence. In this work we look at the extremal properties of {Y_k}. In particular, we investigate the limiting distribution of the sample maxima and the corresponding extremal index. Motivation comes from the comparison of schemes for monitoring a variety of medical, finance, environmental, and social science data sets.AMS 2000 Subject Classification. 62–02, 60G70, 60G10Contract/grant sponsors: POCTI/33477/Mat/2000 and POSI/CPS/42069/2001 FCT plurianual funding.     

Iterative Pexider equation modulo a subset

Summary LetX, Y, Z be arbitrary nonempty sets,E be a nonempty subset ofZ ^z andK be a groupoid. Assume that {F _t} _{t K} Z ^X, {G _t} _{t K} Y ^X, {H _t} _{t K} Z ^Y are families of functions satisfying the functional equationF _st = k_(s,t) H_s G_t for (s, t) D(K), whereD(K) stands for the domain of the binary operation on the groupoidK andk _(s,t) E for (s, t) D(K). Conditions are established under which the equation can be reduced to the corresponding Cauchy equation. This paper generalizes some results from [4] and [1].     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001     

On the complexity of branch‐and‐bound search for random trees

Let T_n be a b‐ary tree of height n, which has independent, non‐negative, identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Consider the problem of finding the minimum leaf value of T_n. Assume that the edge random variable X is nondegenerate, has E {X^θ}<∞ for some θ>2, and satisfies bP{X=c}<1 where c is the leftmost point of the support of X. We analyze the performance of the standard branch‐and‐bound algorithm for this problem and prove that the number of nodes visited is in probability (β+o(1))ⁿ, where β∈(1, b) is a constant depending only on the distribution of the edge random variables. Explicit expressions for β are derived. We also show that any search algorithm must visit (β+o(1))ⁿ nodes with probability tending to 1, so branch‐and‐bound is asymptotically optimal where first‐order asymptotics are concerned. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14: 309–327, 1999     

Non‐Hermitian perturbations of Hermitian matrix‐sequences and applications to the spectral analysis of the numerical approximation of partial differential equations

This article concerns the spectral analysis of matrix‐sequences which can be written as a non‐Hermitian perturbation of a given Hermitian matrix‐sequence. The main result reads as follows. Suppose that for every n there is a Hermitian matrix X_n of size n and that {X_n}_n～_λf, that is, the matrix‐sequence {X_n}_n enjoys an asymptotic spectral distribution, in the Weyl sense, described by a Lebesgue measurable function f; if $\Vert Y_n{\Vert }_2=o(\sqrt{n})$ with ‖·‖₂ being the Schatten 2 norm, then {X_n+Y_n}_n～_λf. In a previous article by Leonid Golinskii and the second author, a similar result was proved, but under the technical restrictive assumption that the involved matrix‐sequences {X_n}_n and {Y_n}_n are uniformly bounded in spectral norm. Nevertheless, the result had a remarkable impact in the analysis of both spectral distribution and clustering of matrix‐sequences arising from various applications, including the numerical approximation of partial differential equations (PDEs) and the preconditioning of PDE discretization matrices. The new result considerably extends the spectral analysis tools provided by the former one, and in fact we are now allowed to analyze linear PDEs with (unbounded) variable coefficients, preconditioned matrix‐sequences, and so forth. A few selected applications are considered, extensive numerical experiments are discussed, and a further conjecture is illustrated at the end of the article.     

SLLN for Weighted Independent Identically Distributed Random Variables

For any sequence {a _k } with sup for some q>1, we prove that converges to 0 a.s. for every {X _n } i.i.d. with E(|X ₁|)< and E(X ₁)=0; the result is no longer true for q=1, not even for the class of i.i.d. with X ₁ bounded. We also show that if {a _k } is a typical output of a strictly stationary sequence with finite absolute first moment, then for every i.i.d. sequence {X _n { with finite absolute pth moment for some p> 1, converges a.s.     

UNIFORM ESTIMATE ON FINITE TIME RUIN PROBABILITIES WITH RANDOM INTEREST RATE

We consider a discrete time risk model in which the net payout (insurance risk) {Xk,k=1,2,···} are assumed to take real values and belong to the heavy-tailed class L ∩ D and the discount factors (financial risk) {Yk,k=1,2,···} concentrate on [θ,L],where 0 θ 1,L∞,{Xk,k=1,2,···},and {Yk, k=1,2,···} are assumed to be mutually independent. We investigate the asymptotic behavior of the ruin probability within a finite time horizon as the initial capital tends to infinity, and figure out that the convergence holds uniformly for all n ≥ 1, which is different from Tang Q H and Tsitsiashvili G (Adv Appl Prob, 2004, 36: 1278–1299).     

Special moments

In this article, we show that a linear combination of n independent, unbiased Bernoulli random variables {X_k} can match the first 2n moments of a random variable Y which is uniform on an interval. More generally, for each p2, each X_k can be uniform on an arithmetic progression of length p. All values of lie in the range of Y, and their ordering as real numbers coincides with dictionary order on the vector (X₁,…,X_n). The construction involves the roots of truncated q-exponential series. It applies to a construction in numerical cubature using error-correcting codes [G. Kuperberg, Numerical cubature using error-correcting codes, arXiv:math.NA/0402047]. For example, when n=2 and p=2, the values of are the 4-point Chebyshev quadrature formula.     

Extreme Shock Models

The standard assumptions in shock models are that the failure (of the system) is related either to the cumulative effect of a (large) number of shocks or that failure is caused by a shock which is larger than a certain critical level. The present paper is devoted to the second kind. Here the standard setting is that the shocks X_k, k 1, and the times between the shocks Y_k, k 1, are independent, identically distributed random vectors (X_k, Y_k), k 1. In particular, X_k and Y_k may well be dependent (the typical case). The main object of interest is the time to failure, T_(t), where T_n = _kn Y_k and (t) is the first exceedance time, viz. the first time that X_k > t. We derive moment relations and asymptotic distributions of T_(t) as t increases in such a way that P{X₁} > t} tends to 0. A final section discusses some extensions; more general events of failure, the non-i.i.d. case, and point process convergence for a particular case.     

Differential Forms and Smoothness of Quotients by Reductive Groups

Let :XY be a good quotient of a smooth variety X by a reductive algebraic group G and 1k dim (Y) an integer. We prove that if, locally, any invariant horizontal differential k-form on X (resp. any regular differential k-form on Y) is a Kähler differential form on Y then codim(Y _sing)>k+1. We also prove that the dualizing sheaf on Y is the sheaf of invariant horizontal dim(Y)-forms.     

Sur la convergence uniforme presque complète dans l'estimation de la densité spectrale d'un processus à temps continu après échantillonnage du temps

Let $\text{X={X(t)}}{}_{\mathrm{<mtext>t\in </mtext><mtext>R</mtext>}}$ be a continuous-time strictly stationary and strongly mixing process. In this paper, we prove in the setting of spectral density estimation, at first, under some hard conditions on the spectral density φ_X (because of aliasing phenomenon), the uniformly complete convergence of the spectral density estimate from periodic sampling. Afterwards, to overcome aliasing, we consider the sampled process $\text{{X(t}{}_{\mathrm{n}}\text{)}}{}_{\mathrm{<mtext>n\in </mtext><mtext>Z</mtext>}}$, where {t_n} is a stationary point process independent from X. The uniform complete convergence of the spectral estimate based on the discrete time observations {X(t_k),t_k} is also obtained. The convergence rates are also established. To cite this article: M. Rachdi, C. R. Acad. Sci. Paris, Ser. I 337 (2003).     

Strongly consistent estimators of k-th order regression curves and rates of convergence

Summary Let X and Y be two jointly distributed real valued random variables, and let the conditional distribution of X given Y be either in a Lebesgue exponential family or in a discrete exponential family. Let r_k be the k-th order regression curve of Y on X. Let X _n=(X ₁,..., X_n) be a random sample of size n on X. For a subset S of the real line R, statistics based on X_n are exhibited and sufficient conditions are given under which is close to O(n ^–1/2) with probability one. To obtain this result, with uf (u known and f unknown) denoting the unconditional (on y) density of X, the problem of estimating r _k (·) is reduced to the one of estimating f ^(k) (·)/f(·) if the density is wrt the Lebesgue measure on R and f ^(k) is the k-th order derivative of f; and to the one of estimating f(·+k)/f(·) if the density is wrt the counting measure on a countable subset of R.     

The Picard iteration and its application

The convergence behavior of the Picard iteration X_k+1=AX_k+B and the weighted case Y_k=X_k/b_k is investigated. It is shown that the convergence of both these iterations is related to the so-called effective spectrum of A with respect to some matrix. As an application of our convergence results we discuss the convergence behavior of a sequence of scaled triangular matrices {D^NT^N }.     

Self‐converse Mendelsohn designs with block size 4 and 5

A (v, k, λ)‐Mendelsohn design(X, ℬ︁) is called self‐converse if there is an isomorphic mapping ƒ from (X, ℬ︁) to (X, ℬ︁⁻¹), where ℬ︁⁻¹ = {B⁻¹ = 〈x_k, x_k−1,…,x₂, x₁〉: B = 〈x₁, x₂,…,x_k−1, x_k〉 ϵ ℬ︁}. In this paper, we give the existence spectrum for self‐converse (v, 4, 1)– and (v, 5, 1)– Mendelsohn designs. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 411–418, 2000     

Approximation Numbers of Operators on Normed Linear Spaces

In [1], B?ttcher et. al. showed that if T is a bounded linear operator on a separable Hilbert space H, {e_j}_j=1^￥H, \{e_{j}\}_{j=1}^{\infty} is an orthonormal basis of H and P_n is the orthogonal projection onto the span of {e_j}_j=1ⁿ\{e_{j}\}_{j=1}^{n}, then for each k ? \mathbbNk \in {\mathbb{N}}, the sequence {s_k(P_nTP_n)}\{s_{k}(P_{n}TP_{n})\} converges to s_k(T), where for a bounded operator A on H, s_k(A) denotes the kth approximation number of A, that is, s_k(A) is the distance from A to the set of all bounded linear operators of rank at most k − 1. In this paper we extend the above result to more general cases. In particular, we prove that if T is a bounded linear operator from a separable normed linear space X to a reflexive Banach space Y and if {P_n} and {Q_n} are sequences of bounded linear operators on X and Y, respectively, such that ||P_n|| ||Q_n|| ￡ 1\|P_n\| \|Q_n\| \leq 1 for all n ? \mathbbNn \in {\mathbb{N}} and {Q_nTP_n} converges to T under the weak operator topology, then {s_k(Q_nTP_n)}\{s_{k}(Q_{n}TP_{n})\} converges to s_k(T). We also obtain a similar result for the case of any normed linear space Y which is the dual of some separable normed linear space. For compact operators, we give this convergence of s_k(Q_nTP_n)s_{k}(Q_{n}TP_{n}) to s_k(T) with separability assumptions on X and the dual of Y. Counter examples are given to show that the results do not hold if additional assumptions on the space Y are removed. Under separability assumptions on X and Y, we also show that if there exist sequences of bounded linear operators {P_n} and {Q_n} on X and Y respectively such that (i) Q_nTP_nQ_{n}TP_{n} is compact, (ii) ||P_n|| ||Q_n|| ￡ 1\|P_{n}\| \|Q_{n}\| \leq 1 and (iii) {Q_nTP_n}\{Q_{n}TP_{n}\} converges to T in the weak operator topology, then {s_k(Q_nTP_n)}\{s_k(Q_{n}TP_{n})\} converges to s_k(T) if and only if s_k(T) = s_k(T￠)s_{k}(T) = s_{k}(T^\prime). This leads to a generalization of a result of Hutton [3], proved for compact operators between normed linear spaces.