Randomly Weighted Sums of Subexponential Random Variables with Application to Ruin Theory

Let {X _k , 1 k n} be n independent and real-valued random variables with common subexponential distribution function, and let {k, 1 k n} be other n random variables independent of {X _k , 1 k n} and satisfying a _k b for some 0 < a b < for all 1 k n. This paper proves that the asymptotic relations P (max_{1 m n k=1} ^m _k X _k > x) P (sum _k=1 ⁿ _k X _k > x) sum _k=1 ⁿ P ( _k X _k > x) hold as x . In doing so, no any assumption is made on the dependence structure of the sequence { _k , 1 k n}. An application to ruin theory is proposed.     

Spanning Trails Connecting Given Edges

Suppose that is the set of connected graphs such that a graph G if and only if G satisfies both (F1) if X is an edge cut of G with |X|3, then there exists a vertex v of degree |X| such that X consists of all the edges incident with v in G, and (F2) for every v of degree 3, v lies in a k-cycle of G, where 2k3.In this paper, we show that if G and (G)3, then for every pair of edges e,fE(G), G has a trail with initial edge e and final edge f which contains all vertices of G. This result extends several former results.     

An explicit calculation of the mean of the perimeter of the convex hull of a plane random walk

If (X _n ) _n ⁼¹ is a sequence of i.i.d. random variables in the Euclidean plane such that we compute the mean of the perimeter of theconvex hull ofX ₁++X _k; 0kn}.     

Connected and alternating vectors: Polyhedra and algorithms

Given a graphG = (V, E), leta ^S, S L, be the edge set incidence vectors of its nontrivial connected subgraphs.The extreme points of = {x R ^E: a^sx |V(S)| - |S|, S L} are shown to be integer 0/± 1 and characterized. They are the alternating vectorsb ^k, k K, ofG. WhenG is a tree, the extreme points ofB 0,b ^kx 1,k K} are shown to be the connected vectors ofG together with the origin. For the four LP's associated with andA, good algorithms are given and total dual integrality of andA proven.On leave from Swiss Federal Institute of Technology, Zurich.     

k-regular factors and semi-k-regular factors in bipartite graphs

LetG be a graph, andk1 an integer. LetU be a subset ofV(G), and letF be a spanning subgraph ofG such that deg _F (x)=k for allx V(G)–U. If deg _F (x)k for allxU, thenF is called an upper semi-k-regular factor with defect setU, and if deg _F (x)k for allxU, thenF is called a lower semi-k-regular factor with defect setU. Now letG=(X, Y;E(G)) be a bipartite graph with bipartition (X,Y) such that X=Yk+2. We prove the following two results.(1) Suppose that for each subsetU ₁X such that U ₁=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.(2) Suppose that for each subsetU ₁X such that U ₁=X–1/k+1,G has a lower semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=X–1/k+1,G has a lower semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.     

D λ -cycles in 3-cyclable graphs

Letk and be positive integers, andG a 2-connected graph of ordern with minimum degree and independence number. A cycleC ofG is called aD -cycle if every component ofG – V(C) has order smaller than. The graphG isk-cyclable if anyk vertices ofG lie on a common cycle. A previous result of the author is that if k 2, G isk-connected and every connected subgraphH ofG of order has at leastn +k ² + 1/k + 1 – vertices outsideH adjacent to at least one vertex ofH, thenG contains aD -cycle. Here it is conjectured that k-connected can be replaced by k-cyclable, and this is proved fork = 3. As a consequence it is shown that ifn 4 – 6, or ifG is triangle-free andn 8 – 10, thenG contains aD ₃-cycle orG , where denotes a well-known class of nonhamiltonian graphs of connectivity 2. As an analogue of a result of Nash-Williams it follows that ifn 4 – 6 and – 1, thenG is hamiltonian orG . The results are all best possible and compare favorably with recent results on hamiltonicity of graphs which are close to claw-free.     

Efficiency of Proximal Bundle Methods

We give efficiency estimates for proximal bundle methods for finding f_*min_Xf, where f and X are convex. We show that, for any accuracy <0, these methods find a point x^kX such that f(x^k)–f^* after at most k=O(1/³) objective and subgradient evaluations.     

Number of no nisomorphic subgraphs in an n-point graph

LetG(n) be the set of all nonoriented graphs with n enumerated points without loops or multiple lines, and let v_k(G) be the number of mutually nonisomorphic k-point subgraphs of G G(n). It is proved that at least |G(n)| (1–1/n) graphs G G(n) possess the following properties: a) for any k [6log₂n], where c=–c log₂c–(1–c)×log₂(1–c) and c>1/2, we havev _k(G) > C _n ^k (1–1/n²); b) for any k [cn + 5 log₂n] we havev _k(G) = C _n ^k . Hence almost all graphs G G(n) containv(G) 2ⁿ pairwise nonisomorphic subgraphs.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 263–273, March, 1971.     

Asymptotic behavior of the dwell time distribution for a random walk on a positive semi-axis

Let ₁, ₂, ... be a sequence of independent identically distributed random variables with zero means. We consider the functional _n = _k=o ⁿ (S _k ) where S₁=0, S_k= _i=1 ^k _i (k1) and(x)=1 for x0,(x) = 0 for x<0. It is readily seen that _n is the time spent by the random walk S_n, n0, on the positive semi-axis after n steps. For the simplest walk the asymptotics of the distribution P (_n = k) for n and k, as well as for k = O(n) and k/n<1, was studied in [1]. In this paper we obtain the asymptotic expansions in powers of n^–1 of the probabilities P(h_n = nx) and P(nx_{1 n} nx₂) for 0<₁, x = k/n ₂<1, 0<₁x₁2₂<1.Translated from Matematicheskie Zametki, Vol. 15, No. 4, pp. 613–620, April, 1974.The author wishes to thank B. A. Rogozin for valuable discussions in the course of his work.     

Non removable edges in 3-connected cubic graphs

LetG be a cyclicallyk-edge-connected cubic graph withk 3. Lete be an edge ofG. LetG be the cubic graph obtained fromG by deletinge and its end vertices. The edgee is said to bek-removable ifG is also cyclicallyk-edge-connected. Let us denote by S _k (G) the graph induced by thek-removable edges and by N _k (G) the graph induced by the non 3-removable edges ofG. In a previous paper [7], we have proved that N ₃(G) is empty if and only ifG is cyclically 4-edge connected and that if N ₃(G) is not empty then it is a forest containing at least three trees. Andersen, Fleischner and Jackson [1] and, independently, McCuaig [11] studied N ₄(G). Here, we study the structure of N _k (G) fork 5 and we give some constructions of graphs such thatN _k (G) = E(G). We note that the main result of this paper (Theorem 5) has been announced independently by McCuaig [11].

---

Résumé SoitG un graphe cubique cyliquementk-arête-connexe, aveck 3. Soite une arête deG et soitG le graphe cubique obtenu à partir deG en supprimante et ses extrémités. L'arêtee est ditek-suppressible siG est aussi cycliquementk-arête-connexe. Désignons par S _k (G) le graphe induit par les arêtesk-suppressibles et par N _k (G) celui induit par les arêtes nonk-suppressibles. Dans un précédent article [7], nous avons montré que N ₃(G) est vide si et seulement siG est cycliquement 4-arête-connexe et que si N ₃(G) n'est pas vide alors c'est une forêt possédant au moins trois arbres. Andersen, Fleischner and Jackson [1] et, indépendemment, McCuaig [11] ont étudié N ₄(G). Ici, nous étudions la structure de N _k (G) pourk 5 et nous donnons des constructions de graphes pour lesquelsN _k (G) = E(G). Nous signalons que le résultat principal de cet article (Théorème 5) a été annoncé indépendamment par McCuaig [11].

     

On the Movement of Transitive Permutation p-Groups

Let G be a transitive permutation group on a set and m a positive integer. If | – | m for every subset of and all g G, then || 2mp/(p – 1) where p is the least odd prime dividing |G|. It was shown by Mann and Praeger [13] that, for p = 3, the 3-groups G which attain this bound have exponent p. In this paper we will show a generalization of this result for any odd primes.AMS Subject Classification (2000), 20BXX     

On elementary equivalence and isomorphism of clone segments

The principal application of a general theorem proved here shows that for any choice 1mnp of integers there exist metric spacesX andY such that the initialk-segments of their clones of continuous maps coincide exactly whenkm, are isomorphic exactly whenkn, and are elementarily equivalent exactly whenkp.Dedicated to Prof. László Fuchs on the occasion of his 70th birthday     

Optimization of pressure control in a gas pipeline

We consider the synthesis of an approximate optimal control for a gas transport system when state information is acquired at the points X₁,...,x_n of the interval 0 x during the entire control period 0 t . This means that the functions (t, x₁),...,(t, x_n) characterizing the state of the controlled system at the points X₁,...,x_n are known. The approximate optimal control is determined using this information. We solve the control optimization problem which, for a given deviation of the approximate optimal control from the optimum, produces a minimum-information approximate optimal control, i.e., a control determined by a formula with the least number of points x_i, and establishes the location of these points.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 63, pp. 118–123, 1987.     

Subsets with Restricted Movement

Let G be a finite permutation group on a set with no fixed points in and let m and k be integers with 0 < m < k. For a finite subset of the movement of is defined as move() = max_gG| ^g \ |. Suppose further that G is not a 2-group and that p is the least odd prime dividing |G| and move() m for all k-element subsets of . Then either || k + m or k (7m – 5) / 2, || (9m – 3)/2. Moreover when || > k + m, then move() m for every subset of .     

An infinite dimensional analogue of the Albeverio-Röckner's theorem on Fukushima's conjecture

LetX be the solution of the SDE:dX _t = (X _t)dB _t +b(X _t)dt, with andb C _b (R) such that >0 for some constant , andB a real Brownian motion. Let be the law ofX onE=C([0, 1],R) andk E* – {0}, whereE* is the topological dual space ofE. Consider the classical form: _k (u, v)=u / kv / kd, whereu andv are smooth functions onE. We prove that, if _k is closable for anyk in a dense subset ofE* and if the smooth functions are contained in the domain of the generator of the closure of _k , must be a constant function.     

Logarithms and imaginary powers of closed linear operators

The imaginary powersA ^it of a closed linear operatorA, with inverse, in a Banach spaceX are considered as aC ₀-group {exp(itlogA);t R} of bounded linear operators onX, with generatori logA. Here logA is defined as the closure of log(1+A) – log(1+A ^–1). LetA be a linearm-sectorial operator of typeS(tan ), 0(/2), in a Hilbert spaceX. That is, |Im(Au, u)| (tan )Re(Au, u) foru D(A). Then ±ilog(1+A) ism-accretive inX andilog(1+A) is the generator of aC ₀-group {(1+A) ^it ;t R} of bounded imaginary powers, satisfying the estimate (1+A) ^it exp(|t|),t R. In particular, ifA is invertible, then ±ilogA ism-accretive inX, where logA is exactly given by logA=log(1+A)–log(1+A ^–1), and {A ^it;t R} forms aC ₀-group onX, with the estimate A ^it exp(|t|),t R. This yields a slight improvement of the Heinz-Kato inequality.     

The Product of Independent Random Variables with Regularly Varying Tails

A distribution is said to have regularly varying tail with index – (0) if lim _x(kx,)/(x,)=k ^– for each k>0. Let X and Y be independent positive random variables with distributions and , respecitvely. The distribution of product XY is called Mellin–Stieltjes convolution (MS convolution) of and . It is known that D() (the class of distributions on (0,) that have regularly varying tails with index –) is closed under MS convolution. This paper deals with decomposition problem of distributions in D() related to MS convolution. A representation of a regularly varying function F of the following form is investigated: F(x)= _k=0 ^n–1 b _k f(a ^k x), where f is a measurable function and a and b _k (k=1,...,n–1) are real constants. A criterion is given for these constants in order that f be regularly varying. This criterion is applicable to show that there exist two distributions and such that neither nor belongs to D() (>0) and their MS convolution belongs to D().     

Strong consistency of the mean on randomly deleted sets

Suppose 0t ₁<t ₂<... are fixed points in time. At timet _k , a unit with magnitudeX _k and lifetimeL _k enters a population or is placed into a system. Suppose that theX _k 's are i.i.d. withEX ₁=, theL _k 's are i.i.d., and that theX _k 's andL _k 's are independent. In this paper we find conditions under which the continuous time process Avr{X _k :t _k t<t _k +L _k } is almost surely convergent to . We also demonstrate the sharpness of these conditions.     

Sur certaines algèbres associées à une mesure de Guelfand

Let be a Guelfand measure (cf. [A, B]) on a locally compact groupG DenoteL ₁ (G)=*L ₁(G)* the commutative Banach algebra associated to . We show thatL ₁ (G) is semi-simple and give a characterization of the closed ideals ofL ₁ (G). Using the -spherical Fourier transform, we characterize all linear bounded operators inL ₁ (G) which are invariants by -translations (i.e. such that ¹(( _x f) )=( _x ((f)) for eachxG andfL ₁ (G); where _x f(y)=f(xy); x,y G). WhenG is compact, we study the algebraL ₁ (G) and obtain results analogous to ones obtained for the commutative case: we show thatL ₁ (G) is regular, all closed sets of its Guelfand spectrum are sets of synthesis and establish theorems of harmonic synthesis for functions inL _p (G) (p=1,2 or +).

     

Convex independent sets and 7-holes in restricted planar point sets

For a finite setA of points in the plane, letq(A) denote the ratio of the maximum distance of any pair of points ofA to the minimum distance of any pair of points ofA. Fork>0 letc (k) denote the largest integerc such that any setA ofk points in general position in the plane, satisfying for fixed , contains at leastc convex independent points. We determine the exact asymptotic behavior ofc (k), proving that there are two positive constants=(), such thatk ^1/3c (k)k ^1/3. To establish the upper bound ofc (k) we construct a set, which also solves (affirmatively) the problem of Alonet al. [1] about the existence of a setA ofk points in general position without a 7-hole (i.e., vertices of a convex 7-gon containing no other points fromA), satisfying . The construction uses Horton sets, which generalize sets without 7-holes constructed by Horton and which have some interesting properties.