Susceptibility of random graphs with given vertex degrees (2009)
We study the susceptibility, i.e., the mean cluster size, in random graphs with given vertex degrees. We show, under weak assumptions, that the susceptibility converges to the expected cluster size...
A functional combinatorial central limit theorem (2009)
Barbour, Andrew D; Universitat Zurich; A.d.barbour@math.uzh.ch, Janson, Svante; Uppsala Universitet; Svante.Janson@math.uu.se
The paper establishes a functional version of the Hoeffding combinatorial central limit theorem. First, a pre-limiting Gaussian process approximation is defined, and is shown to be at a distance of...
On covering by translates of a set (2009)
Bollobas, Bela, Janson, Svante, Riordan, Oliver
In this paper we study the minimal number of translates of an arbitrary subset $S$ of a group $G$ needed to cover the group, and related notions of the efficiency of such coverings. We focus mainly...
Geoffrey Grimmett, Svante Janson
Abstract. We study a random even subgraph of a finite graph G with a general edge-weight p ∈ (0, 1). We demonstrate how it may be obtained from a certain random-cluster measure on G, and we propose...
Standard representation of multivariate functions on a general probability space (2009)
Janson, Svante; Uppsala University; Svante.janson@math.uu.se
It is well-known that a random variable, i.e. a function defined on a probability space, with values in a Borel space, can be represented on the special probability space consisting of the unit...
Threshold graph limits and random threshold graphs (2009)
Diaconis, Persi, Holmes, Susan, Janson, Svante
We study the limit theory of large threshold graphs and apply this to a variety of models for random threshold graphs. The results give a nice set of examples for the emerging theory of graph limits.
The Mahonian probability distribution on words is asymptotically normal (2009)
Canfield, E. Rodney, Janson, Svante, Zeilberger, Doron
The Mahonian statistic is the number of inversions in a permutation of a multiset with $a_i$ elements of type $i$, $1\le i\le m$. The counting function for this statistic is the $q$ analog of the...
On the number of perfect matchings in random lifts (2009)
Greenhill, Catherine, Janson, Svante, Rucinski, Andrzej
Let G be a fixed connected multigraph with no loops. A random n-lift of G is obtained by replacing each vertex of G by a set of n vertices (where these sets are pairwise disjoint) and replacing each...
A functional combinatorial central limit theorem (2009)
Barbour, A. D., Janson, Svante
The paper establishes a functional version of the Hoeffding combinatorial central limit theorem. First, a pre-limiting Gaussian process approximation is defined, and is shown to be at a distance of...
Quasi-random graphs and graph limits (2009)
We use the theory of graph limits to study several quasi-random properties, mainly dealing with various versions of hereditary subgraph counts. The main idea is to transfer the properties of...
Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs (2009)
Janson, Svante, Rucinski, Andrzej
General upper tail estimates are given for counting edges in a random induced subhypergraph of a fixed hypergraph H, with an easy proof by estimating the moments. As an application we consider the...
Large cliques in a power-law random graph (2009)
Janson, Svante, Łuczak, Tomasz, Norros, Ilkka
We study the size of the largest clique $\omega(G(n,\alpha))$ in a random graph $G(n,\alpha)$ on $n$ vertices which has power-law degree distribution with exponent $\alpha$. We show that for `flat'...
Duality in inhomogeneous random graphs, and the cut metric (2009)
Janson, Svante, Riordan, Oliver
The classical random graph model $G(n,\lambda/n)$ satisfies a `duality principle', in that removing the giant component from a supercritical instance of the model leaves (essentially) a subcritical...
Susceptibility in inhomogeneous random graphs (2009)
Janson, Svante, Riordan, Oliver
We study the susceptibility, i.e., the mean size of the component containing a random vertex, in a general model of inhomogeneous random graphs. This is one of the fundamental quantities associated...
Asymptotic Normality of Statistics on Permutation Tableaux (2009)
Hitczenko, Pawel, Janson, Svante
In this paper we use a probabilistic approach to derive the expressions for the characteristic functions of basic statistics defined on permutation tableaux. Since our expressions are exact, we can...
Zeros of Sections of the Binomial Expansion (2009)
Janson, Svante, Norfolk, Timothy S.
We examine the asymptotic behaviour of the zeros of sections of the binomial expansion. That is, we consider the distribution of zeros of $\displaystyle B_{r,n}(z) = \sum_{k=0}^r {n \choose k} z^k$,...
Hwang, Hsien-Kuei, Janson, Svante
By a suitable shifting-the-mean parametrization at the Dirichlet series level and Delange's Tauberian theorems, we show that the number of factors in random ordered factorizations of integers is...
On the spread of supercritical random graphs (2009)
Addario-Berry, Louigi, Janson, Svante, McDiarmid, Colin
The spread of a connected graph G was introduced by Alon Boppana and Spencer (1998) and measures how tightly connected the graph is. It is defined as the maximum over all Lipschitz functions f on...
Graphs where every k-subset of vertices is an identifying set (2009)
Gravier, Sylvain, Janson, Svante, Laihonen, Tero, Ranto, Sanna
Let $G=(V,E)$ be an undirected graph without loops and multiple edges. A subset $C\subseteq V$ is called \emph{identifying} if for every vertex $x\in V$ the intersection of $C$ and the closed...
Poset limits and exchangeable random posets (2009)
We develop a theory of limits of finite posets in close analogy to the recent theory of graph limits. In particular, we study representations of the limits by functions of two variables on a...
On percolation in random graphs with given vertex degrees (2009)
Janson, Svante; Uppsala University; Svante.janson@math.uu.se
We study the random graph obtained by random deletion of vertices or edges from a random graph with given vertex degrees. A simple trick of exploding vertices instead of deleting them, enables us to...
The cut metric, random graphs, and branching processes (2009)
Bollobas, Bela, Janson, Svante, Riordan, Oliver
In this paper we study the component structure of random graphs with independence between the edges. Under mild assumptions, we determine whether there is a giant component, and find its asymptotic...
Distances between pairs of vertices and vertical profile in conditioned Galton--Watson trees (2008)
We consider a conditioned Galton-Watson tree and prove an estimate of the number of pairs of vertices with a given distance, or, equivalently, the number of paths of a given length. We give two...
On vertex, edge, and vertex-edge random graphs (2008)
Beer, Elizabeth, Fill, James Allen, Janson, Svante, Scheinerman, Edward R.
We consider three classes of random graphs: edge random graphs, vertex random graphs, and vertex-edge random graphs. Edge random graphs are Erdos-Renyi random graphs, vertex random graphs are...
S:intro secA GRAPH LIMITS AND EXCHANGEABLE RANDOM GRAPHS (2008)
Abstract. We develop a clear connection between deFinetti’s theorem for exchangeable arrays (work of Aldous–Hoover–Kallenberg) and the emerging area of graph limits (work of Lovász and many...
Sparse random graphs with clustering (2008)
Bollobas, Bela, Janson, Svante, Riordan, Oliver
In 2007 we introduced a general model of sparse random graphs with independence between the edges. The aim of this paper is to present an extension of this model in which the edges are far from...
Susceptibility in subcritical random graphs (2008)
Janson, Svante, Luczak, Malwina J.
We study the evolution of the susceptibility in the subcritical random graph $G(n,p)$ as $n$ tends to infinity. We obtain precise asymptotics of its expectation and variance, and show it obeys a law...
Generalized Stirling permutations, families of increasing trees and urn models (2008)
Janson, Svante, Kuba, Markus, Panholzer, Alois
Bona [2007+] studied the distribution of ascents, plateaux and descents in the class of Stirling permutations, introduced by Gessel and Stanley [1978]. Recently, Janson [2008+] showed the connection...
On the size of identifying codes in binary hypercubes (2008)
Janson, Svante, Laihonen, Tero
We consider identifying codes in binary Hamming spaces F^n, i.e., in binary hypercubes. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. Currently, the...
On percolation in random graphs with given vertex degrees (2008)
We study the random graph obtained by random deletion of vertices or edges from a random graph with given vertex degrees. A simple trick of exploding vertices instead of deleting them, enables us to...
Olivier François, Svante Janson, Michael Blum, Olivier François, Pavillon Taillefer, ...
The mean, variance and limiting distribution of two statistics sensitive to
Singularity analysis of Hadamard products (2008)
Nevin Kapur, Featuring Jim Fill, Svante Janson
Limiting distributions for additive functionals on
Partial Fillup and Search Time in LC Tries ∗ (2008)
Svante Janson, Wojciech Szpankowski
Andersson and Nilsson introduced in 1993 a levelcompressed trie (in short: LC trie) in which a full subtree of a node is compressed to a single node of degree being the size of the subtree. Recent...
The phase transition in a uniformly grown random graph has infinite order, Random Struct. Alg (2008)
Béla Bollobás, Svante Janson, Oliver Riordan
graph has infinite order
Catherine Greenhill, Jeong Han Kim, Svante Janson, Nicholas C. Wormald
The space of permutation pseudographs is a probabilistic model of 2-regular pseudographs on n vertices, where a pseudograph is produced by choosing a permutation σ of {1, 2,..., n} uniformly at...
Rainbow hamilton cycles in random regular graphs (2008)
Svante Janson, Nicholas Wormald
Abstract. A rainbow subgraph of an edge-coloured graph has all edges of distinct colours. A random d-regular graph with d even, and having edges coloured randomly with d/2 of each of n colours, has a...
Plane recursive trees, Stirling permutations and an urn model (2008)
We exploit a bijection between plane recursive trees and Stirling permutations; this yields the equivalence of some results previously proven separately by different methods for the two types of...
Connectedness in graph limits (2008)
We define direct sums and a corresponding notion of connectedness for graph limits. Every graph limit has a unique decomposition as a direct sum of connected components. As is well-known, graph...
Asymptotic equivalence and contiguity of some random graphs (2008)
We show that asymptotic equivalence, in a strong form, holds between two random graph models with slightly differing edge probabilities under substantially weaker conditions than what might naively...
Convergence of some leader election algorithms (2008)
Janson, Svante, Lavault, Christian, Louchard, Guy
We start with a set of n players. With some probability P(n,k), we kill n-k players; the other ones stay alive, and we repeat with them. What is the distribution of the number X_n of phases (or...
James Allen Fill, Svante Janson
This appendix to [2] contains a proof of the improved estimates in Remark 7.3 of that paper for the moment generating function of the (normalized) number of comparisons in Quicksort.
James Allen Fill, Svante Janson
Quicksort, fixed point, characteristic function, smoothing transformation, domain of attraction, coupling, integral equation. The limiting distribution µ of the normalized number of key comparisons...
COMPLEX INTERPOLATION OF COMPACT OPERATORS MAPPING INTO THE COUPLE (F L ∞ , F L ∞ 1). (2008)
Abstract. If (A0, A1) and (B0, B1) are Banach couples and a linear operator
Mireille Bousquet-mélou, Svante Janson
It has been known for a few years that the occupation measure of several models of embedded trees converges, after a suitable normalization, to the random measure called ISE (Integrated SuperBrownian...
APPENDIX TO RANDOM CUTTING AND RECORDS IN DETERMINISTIC AND RANDOM TREES (2008)
This is an appendix to [3], and we use the notation there. In particular, if T is a rooted tree, X(T) denotes the random number of (edge) cuttings needed to destroy the tree completely, or...
DISMANTLING SPARSE RANDOM GRAPHS (2008)
Svante Janson, Andrew Thomason
Abstract. We consider the number of vertices that must be removed from a graph G in order that the remaining subgraph has no component with more than k vertices. Our principal observation is that, if...
Superreplication of options on several underlying assets (2008)
Abstract. It is well-known that prices of options on one underlying asset decay with time and are convex in the underlying asset if the contract function is convex. Here, options on several...
Abstract. We study a point process describing the asymptotic behavior of sizes of the largest components of the random graph G(n, p) in the critical window, that is, for p = n −1 + λn −4/3,...
Monotonicity, asymptotic normality and vertex degrees in random graphs (2008)
We exploit a result by Nerman which shows that conditional limit theorems hold when a certain monotonicity condition is satisfied. Our main result is an application to vertex degrees in random...
THE INTEGRAL OF THE SUPREMUM PROCESS OF BROWNIAN MOTION (2008)
Svante Janson, Niclas Petersson
Abstract. In this paper we study the integral of the supremum process of standard Brownian motion. We present an explicit formula for the moments of the integral (or area) A(T), covered by the...
On the asymptotic joint distribution of height and width in random trees (2008)
Abstract. It has been known for a long time that the height and width of a random labelled rooted tree, or of any other conditioned Galton– Watson tree, after suitable normalizations converge to...
GROWTH OF COMPONENTS IN RANDOM GRAPHS (2008)
Abstract. The creation and growth of components of a given complexity in a random graph process are studied. In particular, the expected number and total size of all such components is found. It...
Permutation pseudographs and contiguity (2008)
Catherine Greenhill, Jeong Han Kim, Svante Janson, Nicholas C. Wormald
The space of permutation pseudographs is a probabilistic model of 2-regular pseudographs on n vertices, where a pseudograph is produced by choosing a permutation σ of {1, 2,..., n} uniformly at...
Rademacher chaos: tail estimates vs limit theorems (2008)
Abstract. We study Rademacher chaos indexed by a sparse set which has a fractional combinatorial dimension. We obtain tail estimates for finite sums and a normal limit theorem as the size tends to...
The size of random fragmentation trees (2008)
Svante Janson, Ralph Neininger
Abstract. We study a random fragmentation process and its associated ran-dom tree. The process has earlier been studied by Dean and Majumdar [7], who found a phase transition: the number of...
James Allen Fill, Svante Janson
The limiting distribution of the normalized number of comparisons used by Quicksort to sort an array of n numbers is known to be the unique fixed point with zero mean of a certain distributional...
INHOMOGENEOUS RANDOM GRAPHS (2008)
One of the most studied random graphs is G(n, p), which has n vertices that can be taken as the integers 1,..., n, and where each pair of vertices is connected by an edge with probability p,...
Cycles and unicyclic components in random graphs (2008)
Abstract. The sizes of the cycles and unicyclic components in the random graph G(n, n/2 ± s), where n 2/3 ≪ s ≪ n, are studied using the language of point processes. This refines several earlier...
Rainbow hamilton cycles in random regular graphs (2008)
Svante Janson, Nicholas Wormald
Abstract. A rainbow subgraph of an edge-coloured graph has all edges of distinct colours. A random d-regular graph with d even, and having edges coloured randomly with d/2 of each of n colours, has a...
Rademacher chaos: tail estimates vs limit theorems (2008)
Abstract. We study Rademacher chaos indexed by a sparse set which has a fractional combinatorial dimension. We obtain tail estimates for finite sums and a normal limit theorem as the size tends to...
The phase transition in a uniformly grown random graph has infinite order, Random Struct. Alg (2008)
Béla Bollobás, Svante Janson, Oliver Riordan
The aim of this paper is to study the emergence of the giant component in the uniformly grown random graph Gn(c), 0 < c < 1, the graph on the set [n] = {1, 2,..., n} in which each possible edge...
Abstract. We study the space requirements of a sorting algorithm where only items that at the end will be adjacent are kept together. This is equivalent to the following combinatorial problem:...
Volatility time and properties of option prices (2008)
Abstract. We use a notion of stochastic time, here called volatility time, to show convexity of option prices in the underlying asset if the contract function is convex as well as continuity and...
THE INTEGRAL OF THE SUPREMUM PROCESS OF BROWNIAN MOTION (2008)
Svante Janson, Niclas Petersson, Svante Janson, Niclas Petersson
Abstract. In this paper we study the integral of the supremum process of standard Brownian motion. We present an explicit formula for the moments of the integral (or area) A(T), covered by the...
THE FIRST EIGENVALUE OF RANDOM GRAPHS (2008)
Abstract. We extend a result by Füredi and Komlós and show that the first eigenvalue of a random graph is asymptotically normal, both for Gn,p and Gn,m, provided np ≥ n δ or m/n ≥ n δ for...
MONOTONICITY, ASYMPTOTIC NORMALITY AND VERTEX DEGREES IN RANDOM GRAPHS (2008)
Abstract. We exploit a result by Nerman which shows that conditional limit theorems hold when a certain monotonicity condition is satisfied. Our main result is an application to vertex degrees in...
Superreplication of options on several underlying assets (2008)
Erik Ekström, Svante Janson, Johan Tysk
Abstract. We investigate when a hedger who over-estimates the volatility will superreplicate a convex claim on several underlying assets. It is shown that the classical Black and Scholes model is the...
Volatility time and properties of option prices (2008)
Abstract. We use a notion of stochastic time, here called volatility time, to show convexity of option prices in the underlying asset if the contract function is convex as well as continuity and...
Cycles and unicyclic components in random graphs (2008)
Abstract. The sizes of the cycles and unicyclic components in the random graph G(n, n/2 ± s), where n 2/3 ≪ s ≪ n, are studied using the language of point processes. This refines several earlier...
Abstract. For certain random variables that arise as limits of functionals of random finite trees, we obtain precise asymptotics for the logarithm of the right-hand tail. Our results are based on the...
On a random graph related to quantum theory (2008)
Abstract. We show that a random graph studied by Ioffe and Levit is an example of an inhomogeneous random graph of the type studied by Bollobás, Janson and Riordan, which enables us to give a new,...
INDIVIDUAL DISPLACEMENTS IN HASHING WITH COALESCED CHAINS (2008)
Abstract. We study the asymptotic distribution of the displacements in hashing with coalesced chains, for both late-insertion and early-insertion. Asymptotic formulas for means and variances follow....
FEYNMAN-KAC FORMULAS FOR BLACK-SCHOLES TYPE OPERATORS (2008)
Abstract. There are many references showing that a classical solution to the Black–Scholes equation is a stochastic solution. However, it is the converse of this theorem which is most relevant in...
THE NUMBER OF BIT COMPARISONS USED BY QUICKSORT: AN AVERAGE-CASE ANALYSIS (2008)
Abstract. The analyses of many algorithms and data structures (such as digital search trees) for searching and sorting are based on the representation of the keys involved as bit strings and so count...
Complex interpolation of compact operators. An update (2008)
Abstract. After 41 years it is still not known whether an operator acting on a Banach pair and which acts compactly on one or both of the “endpoint ” spaces also acts compactly on the complex...
Geoffrey Grimmett, Svante Janson
Abstract. Pick n points independently at random in R2, according to a prescribed probability measure µ, and let ∆n 1 ≤ ∆n 2 ≤... be the areas of the �n � triangles 3 thus formed, in...
Branching processes, and random-cluster measures on trees (2008)
Geoffrey Grimmett, Svante Janson
Abstract. Random-cluster measures on infinite regular trees are studied in conjunction with a general type of ‘boundary condition’, namely an equivalence relation on the set of infinite paths of...
STANDARD REPRESENTATION OF MULTIVARIATE FUNCTIONS ON A GENERAL PROBABILITY SPACE (2008)
Abstract. It is well-known that a random variable, i.e. a function defined on a probability space, with values in a Borel space, can be represented on the special probability space consisting of the...
Abstract. We study the space requirements of a sorting algorithm where only items that at the end will be adjacent are kept together. This is equivalent to the following combinatorial problem:...
In the article “The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph ” by Janson [6] it is shown that the minimal weight Wn of a spanning tree...
James Allen Fill, Svante Janson
The limiting distribution of the normalized number of comparisons used by Quicksort to sort an array of n numbers is known to be the unique fixed point with zero mean of a certain distributional...
A functional limit theorem for the profile of search trees (2008)
Michael Drmota, Tu Wien, Svante Janson, Ralph Neininger
We study the profile Xn,k of random search trees including binary search trees and m-ary search trees. Our main result is a functional limit theorem of the normalized profile Xn,k / E Xn,k for k =...
THE LARGEST COMPONENT IN A SUBCRITICAL RANDOM GRAPH WITH A POWER LAW DEGREE DISTRIBUTION (2008)
Abstract. It is shown that in a subcritical random graph with given vertex degrees satifying a power law degree distribution with exponent γ> 3, the largest component is of order n 1/(γ−1)....
On Certain Quotients Of Hardy Spaces (2008)
.08> \Gamma1!j!1 H p(\Omega j ), thus \Pi p is the linear space of all functions which are holomorphic in some\Omega j and belong to H p there, with two functions identified if they coincide on...
On Complex Hypercontractivity (2008)
. We give a new proof of a hypercontractivity theorem for the Mehler transform with a complex parameter, earlier proved by Weissler [15] and Epperson [4]. The proof uses stochastic integrals and Ito...
Symptotic normality of the k-core in random graphs (2008)
Janson, Svante, Luczak, Malwina J.
Svante and Malwina J.
Convergence of some leader election algorithms (2008)
Svante Janson, Christian Lavault, Guy Louchard
We start with a set of n players. With some probability P(n,k), we kill n-k players; the other ones stay alive, and we repeat with them. What is the distribution of the number X n of phases (or...
Standard representation of multivariate functions on a general probability space (2007)
It is well-known that a random variable, i.e., a function defined on a probability space, with values in a Borel space, can be represented on the special probability space consisting of the unit...
Tail estimates for the Brownian excursion area and other Brownian areas (2007)
Janson, Svante; Uppsala University; Svante.janson@math.uu.se, Louchard, Guy; ULB; Louchard@ulb.ac.be
Brownian areas are considered in this paper: the Brownian excursion area, the Brownian bridge area, the Brownian motion area, the Brownian meander area, the Brownian double meander area, the positive...
Graph limits and exchangeable random graphs (2007)
Diaconis, Persi, Janson, Svante
We develop a clear connection between deFinetti's theorem for exchangeable arrays (work of Aldous--Hoover--Kallenberg) and the emerging area of graph limits (work of Lovasz and many coauthors). Along...
Random graphs with forbidden vertex degrees (2007)
Grimmett, Geoffrey, Janson, Svante
We study the random graph G_{n,\lambda/n} conditioned on the event that all vertex degrees lie in some given subset S of the non-negative integers. Subject to a certain hypothesis on S, the empirical...
1 a given integer. Let further (2007)
Svante Janson, Andrzej Rucinski
Let # be a finite index set and k
James Allen Fill, Svante Janson
The limiting distribution of the normalized number of comparisons used by Quicksort to sort an array of n numbers is known to be the unique fixed point with zero mean of a certain distributional...
Interpolation Of Subcouples And Quotient Couples (2007)
. We extend recent results by Pisier on K-subcouples, i.e. subcouples of an interpolation couple that preserve the K-functional (up to constants) and corresponding notions for quotient couples....
Hamilton Cycles In A Random Tournament (2007)
. The number of Hamilton cycles in a random tournament is asymptotically normally distributed. 1. Introduction A tournament on n vertices is a directed graph obtained by orienting each edge of the...
Tightness and Weak Convergence for Jump Processes (2007)
The aim of this note is to extend tightness criteria for random measures and simple point processes to processes with general jump distributions. AMS (1991) Subject Classification: 60F17, 60G50,...
The Second Moment Method, Conditioning And Approximation (2007)
The second moment method has been fruitfully combined with conditioning by several authors, for example Robinson and Wormald [7], [8] and Frieze and Janson [2]. We try to give a general exposition of...
Complex Method Interpolation Defined Using A Half-Plane Or Full Disc (2007)
this paper is to show that, in general, these questions have a negative answer, even if we suppose X 1 ` X 0 . This is done by an explicit counter example. Section 1 contains some definitions and an...
On the space Q p and its dyadic counterpart (2007)
. We define a dyadic counterpart Q d p of Q p , and study some relations between Q p and Q d p . For example, a function on T belongs to Q p if and only if (almost) all its translates belong to Q d p...
James Allen Fill, Svante Janson
The analyses of many algorithms and data structures (such as digital search trees) for searching and sorting are based on the representation of the keys involved as bit strings and so count the...
Svante Janson, Elchanan Mossel
reconstruction on trees is determined by the second eigenvalue
Volatility time and properties of option prices (2007)
Abstract. We use a notion of stochastic time, here called volatility time, to show convexity of option prices in the underlying asset if the contract function is convex as well as continuity and...
On generalized random railways (2007)
Hans Garmo, Svante Janson, Karo Ński
Abstract. We consider a random generalized railway defined as a random 3-regular multigraph where some vertices are regarded as switches not allowing traffic between any pair of attached edges. It is...
James Allen Fill, Svante Janson
This appendix to [2] contains a proof of the improved estimates in Remark 7.3 of that paper for the moment generating function of the (normalized) number of comparisons in Quicksort.
James Allen Fill, Svante Janson
The number of comparisons Xn used by Quicksort to sort an array of n distinct numbers has mean µn of order n log n and standard deviation of order n. Using different methods, Régnier and Rösler...
Random Dyadic Tilings of the Unit Square (2007)
Svante Janson, Dana R, Joel Spencer
A “dyadic rectangle ” is a set of the form R = [a2 −s, (a+1)2 −s]×[b2 −t, (b+1)2 −t], where s and t are non-negative integers. A dyadic tiling is a tiling of the unit square with dyadic...
Volatility time and properties of option prices (2007)
Abstract. We use a notion of stochastic time to show convexity of option prices in the underlying asset if the contract function is convex as well as continuity and monotonicity of the option price...
James Allen Fill, Svante Janson
The limiting distribution of the normalized number of comparisons used by Quicksort to sort an array of n numbers is known to be the unique xed point with zero mean of a certain distributional...
Random Dyadic Tilings of the Unit Square (2007)
Svante Janson, Dana R, Joel Spencer
A "dyadic rectangle " is a set of the form R = [a2-s, (a+1)2-s][b2-t, (b+1)2-t], where s and t are non-negative integers. A dyadic tiling is a tiling of the unit square with dyadic...
Quicksort Asymptotics, Svante Janson
The number of comparisons X n used by Quicksort to sort an array of n distinct numbers has mean n of order n log n and standard deviation of order n. Using di#erent methods, Regnier and Rosler each...
AND PERFECT MATCHINGS IN A RANDOM GRAPH (2007)
Abstract. The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph Gnm are shown to be asymptotically normal if m is neither too large nor too small. At the lower limit...
Volatility time and properties of option prices (2007)
Abstract. We use a notion of stochastic time to show convexity of option prices in the underlying asset if the contract function is convex as well as continuity and monotonicity of the option price...
James Allen Fill, Svante Janson
This appendix to [2] contains a proof of the improved estimates in Remark 7.3 of that paper for the moment generating function of the (normalized) number of comparisons in Quicksort.
Quicksort, fixed point, characteristic function, smoothing transformation, domain of attraction, coupling, integral equation. The limiting distribution of the normalized number of key comparisons...
Superreplication of options on several underlying assets (2007)
Abstract. It is well-known that prices of options on one underlying asset decay with time and are convex in the underlying asset if the contract function is convex. Here, options on several...
Quicksort Asymptotics, Svante Janson
The number of comparisons X n used by Quicksort to sort an array of n distinct numbers has mean n of order n log n and standard deviation of order n. Using di#erent methods, Regnier and Rosler each...
Permutation Pseudographs and Contiguity (2007)
Catherine Greenhill, Svante Janson, Jeong Han Kim, Nicholas C. Wormald
The space of permutation pseudographs is a probabilistic model of 2-regular pseudographs on n vertices, where a pseudograph is produced by choosing a permutation of f1; 2; : : : ; ng uniformly at...
Geoffrey Grimmett, Svante Janson
Pick n points independently at random in R , according to a prescribed probability measure , and let # . . . be the areas of the triangles thus formed, in non-decreasing order. If is absolutely...
Cycles and Unicyclic Components in Random Graphs (2007)
The sizes of the cycles and unicyclic components in the random graph G(n, n/2 ± s), where n^2/3 << s << n, are studied using the language of point processes....
Grimmett, Geoffrey, Janson, Svante
We study a random even subgraph of a finite graph $G$ with a general edge-weight $p\in(0,1)$. We demonstrate how it may be obtained from a certain random-cluster measure on $G$, and we propose a...
Dismantling sparse random graphs (2007)
Janson, Svante, Thomason, Andrew
We consider the number of vertices that must be removed from a graph G in order that the remaining subgraph has no component with more than k vertices. Our principal observation is that, if G is a...
The largest component in a subcritical random graph with a power law degree distribution (2007)
It is shown that in a subcritical random graph with given vertex degrees satisfying a power law degree distribution with exponent $\gamma>3$, the largest component is of order $n^{1/(\gamma-1)}$....
A new approach to the giant component problem (2007)
Janson, Svante, Luczak, Malwina
We study the largest component of a random (multi)graph on n vertices with a given degree sequence. We let n tend to infinity. Then, under some regularity conditions on the degree sequences, we give...
The integral of the supremum process of Brownian motion (2007)
Janson, Svante, Petersson, Niclas
In this paper we study the integral of the supremum process of standard Brownian motion. We present an explicit formula for the moments of the integral (or area) A(T), covered by the process in the...
Tail estimates for the Brownian excursion area and other Brownian areas (2007)
Several Brownian areas are considered in this paper: the Brownian excursion area, the Brownian bridge area, the Brownian motion area, the Brownian meander area, the Brownian double meander area, the...
The center of mass of the ISE and the Wiener index of trees (2007)
Janson, Svante, Chassaing, Philippe
We derive the distribution of the center of mass $S$ of the integrated superBrownian excursion (ISE) {from} the asymptotic distribution of the Wiener index for simple trees. Equivalently, this is the...
Brownian excursion area, Wright's constants in graph enumeration, and other Brownian areas (2007)
This survey is a collection of various results and formulas by different authors on the areas (integrals) of five related processes, viz.\spacefactor =1000 Brownian motion, bridge, excursion, meander...
Blum, Michael G. B., François, Olivier, Janson, Svante
For two decades, the Colless index has been the most frequently used statistic for assessing the balance of phylogenetic trees. In this article, this statistic is studied under the Yule and uniform...
Line-of-sight percolation (2007)
Bollobas, Bela, Janson, Svante, Riordan, Oliver
Given $\omega\ge 1$, let $Z^2_{(\omega)}$ be the graph with vertex set $Z^2$ in which two vertices are joined if they agree in one coordinate and differ by at most $\omega$ in the other. (Thus...
Graphs with specified degree distributions, simple epidemics and local vaccination strategies (2007)
Britton, Tom, Janson, Svante, Martin-Lof, Anders
Consider a random graph, having a pre-specified degree distribution F but other than that being uniformly distributed, describing the social structure (friendship) in a large community. Suppose one...
We study the space requirements of a sorting algorithm where only items that at the end will be adjacent are kept together. This is equivalent to the following combinatorial problem: Consider a...
Fill, James Allen, Janson, Svante
For certain random variables that arise as limits of functionals of random finite trees, we obtain precise asymptotics for the logarithm of the right-hand tail. Our results are based on the facts (i)...
Graphs with specified degree distributions, simple epidemics and local vaccination strategies (2007)
Tom Britton, Svante Janson, Martin-l Öf
Abstract. Consider a random graph, having a pre-specified degree distribution F but other than that being uniformly distributed, describing the social structure (friendship) in a large community....
Line-of-sight percolation (2007)
Béla Bollobás, Svante Janson, Oliver Riordan
Given ω ≥ 1, let Z 2 (ω) be the graph with vertex set Z 2 in which two vertices are joined if they agree in one coordinate and differ by at most ω in the other. (Thus Z 2 (1) is precisely Z 2.)...
Tail estimates for the Brownian excursion area and other Brownian areas (2007)
Abstract. Several Brownian areas are considered in this paper: the Brownian excursion area, the Brownian bridge area, the Brownian motion area, the Brownian meander area, the Brownian double meander...
Random even graphs and the Ising model (2007)
Geoffrey Grimmett, Svante Janson
We explore the relationship between the Ising model with inverse temperature β, the q = 2 random-cluster model with edge-parameter p = 1 − e −2β, and the random even subgraph with...
Graph limits and exchangeable random graphs (2007)
Abstract. We develop a clear connection between deFinetti’s theorem for exchangeable arrays (work of Aldous–Hoover–Kallenberg) and the emerging area of graph limits (work of Lovász and many...
Random even graphs and the Ising model (2007)
Geoffrey Grimmett, Svante Janson
We explore the relationship between the Ising model with inverse temperature β, the q = 2 random-cluster model with edge-parameter p = 1 − e −2β, and the random even subgraph with...
Random graphs with forbidden vertex degrees (2007)
Geoffrey Grimmett, Svante Janson
Abstract. We study the random graph Gn,λ/n conditioned on the event that all vertex degrees lie in some given subset S of the nonnegative integers. Subject to a certain hypothesis on S, the...
Random graphs with forbidden vertex degrees (2007)
Geoffrey Grimmett, Svante Janson
Abstract. We study the random graph Gn,λ/n conditioned on the event that all vertex degrees lie in some given subset S of the nonnegative integers. Subject to a certain hypothesis on S, the...
A new approach to the giant component problem (2007)
Abstract. We study the largest component of a random (multi)graph on n vertices with a given degree sequence. We let n → ∞. Then, under some regularity conditions on the degree sequences, we give...
Asymptotic normality of the $k$-core in random graphs (2006)
Janson, Svante, Luczak, Malwina J.
We study the $k$-core of a random (multi)graph on $n$ vertices with a given degree sequence. In our previous paper [Random Structures Algorithms 30 (2007) 50--62] we used properties of empirical...
Blum, Michael G. B., François, Olivier, Janson, Svante
For two decades, the Colless index has been the most frequently used statistic for assessing the balance of phylogenetic trees. In this article, this statistic is studied under the Yule and uniform...
The probability that a random multigraph is simple (2006)
Consider a random multigraph G* with given vertex degrees d_1,...,d_n, contructed by the configuration model. We show that, asymptotically for a sequence of such multigraphs with the number of edges...
A functional limit theorem for the profile of search trees (2006)
Drmota, Michael, Janson, Svante, Neininger, Ralph
We study the profile $X_{n,k}$ of random search trees including binary search trees and $m$-ary search trees. Our main result is a functional limit theorem of the normalized profile...
Rounding of continuous random variables and oscillatory asymptotics (2006)
We study the characteristic function and moments of the integer-valued random variable ⌊X+α⌋, where X is a continuous random variables. The results can be regarded as exact versions of...
The density of the ISE and local limit laws for embedded trees (2006)
Bousquet-Mélou, Mireille, Janson, Svante
It has been known for a few years that the occupation measure of several models of embedded trees converges, after a suitable normalization, to the random measure called ISE (integrated SuperBrownian...
Cwikel, Michael, Janson, Svante
If (A_0,A_1) and (B_0,B_1) are Banach couples and a linear operator T from A_0 + A_1 to B_0 + B_1 maps A_0 compactly into B_0 and maps A_1 boundedly into B_1, does T necessarily also map [A_0,A_1]_s...
On a random graph related to quantum theory (2006)
We show that a random graph studied by Ioffe and Levit is an example of an inhomogeneous random graph of the type studied by Bollobas, Janson and Riordan, which enables us to give a new, simple,...
Monotonicity, asymptotic normality and vertex degrees in random graphs (2006)
We exploit a result by Nerman which shows that conditional limit theorems hold when a certain monotonicity condition is satisfied. Our main result is an application to vertex degrees in random...
Local limit theorems for finite and infinite urn models (2006)
Hwang, Hsien-Kuei, Janson, Svante
Local limit theorems are derived for the number of occupied urns in general finite and infinite urn models under the minimum condition that the variance tends to infinity. Our results represent an...
Conditioned Galton-Watson trees do not grow (2006)
An example is given which shows that, in general, conditioned Galton-Watson trees cannot be obtained by adding vertices one by one, as has been shown in a special case by Luczak and Winkler.
The density of the ISE and local limit laws for embedded trees (2006)
Bousquet-Mélou, Mireille, Janson, Svante
It has been known for a few years that the occupation measure of several models of embedded trees converges, after a suitable normalization, to the random measure called ISE (Integrated SuperBrownian...
The density of the ISE and local limit laws for embedded trees (2006)
Bousquet-Mélou, Mireille, Janson, Svante
It has been known for a few years that the occupation measure of several models of embedded trees converges, after a suitable normalization, to the random measure called ISE (Integrated SuperBrownian...
A simple solution to the k-core problem (2006)
Janson, Svante, Luczak, Malwina J.
We study the k-core of a random (multi)graph on n vertices with a given degree sequence. We let n ! 1. Then, under some regularity conditions on the degree sequences, we give conditions on the...
Conditioned Galton-Watson trees do not grow (2006)
An example is given which shows that, in general, conditioned Galton–Watson trees cannot be obtained by adding vertices one by one, while this can be done in some important but special cases, as...
Rounding of continuous random variables and oscillatory (2006)
We study the characteristic function and moments of the integer-valued random variable ⌊X + α⌋,whereX is a continuous random variables. The results can be regarded as exact versions of...
Random cutting and records in deterministic and random trees (2006)
Abstract. We study random cutting down of a rooted tree and show that the number of cuts is equal (in distribution) to the number of records in the tree when edges (or vertices) are assigned random...
Hsien-kuei Hwang, Svante Janson
Local limit theorems are derived for the number of occupied urns in general finite and infinite urn models under the minimum condition that the variance tends to infinity. Our results represent an...
Asymptotic normality of the k-core in random graphs (2006)
Abstract. We study the k-core of a random (multi)graph on n vertices with a given degree sequence. In our previous paper [18] we used properties of empirical distributions of independent random...
CONDITIONED GALTON–WATSON TREES DO NOT (2006)
Abstract. An example is given which shows that, in general, conditioned Galton–Watson trees cannot be obtained by adding vertices one by one, as has been shown in a special case by Luczak and...
Spread-out percolation in R d (2006)
Béla Bollobás, Svante Janson, Oliver Riordan
Fix d ≥ 2, and let X be either Z d or the points of a Poisson process in R d of intensity 1. Given parameters r and p, join each pair of points of X within distance r independently with probability...
Rounding of continuous random variables and oscillatory (2006)
Abstract. We study the characteristic function and moments of the integer-valued random variable ⌊X+α⌋, where X is a continuous random variable. The results can be regarded as exact versions of...
The probability that a random multigraph is simple (2006)
Abstract. Consider a random multigraph G ∗ with given vertex degrees d1,..., dn, contructed by the configuration model. We show that, asymptotically for a sequence of such multigraphs with the...
Olivier François, Svante Janson
For two decades, the Colless index has been the most frequently used statistic for assessing the balance of phylogenetic trees. In this article, this statistic is studied under the Yule and uniform...
The phase transition in inhomogeneous random graphs (2006)
B Éla Bollobás, Svante Janson, Oliver Riordan
Abstract. The ‘classical ’ random graph models, in particular G(n, p), are ‘homogeneous’, in the sense that the degrees (for example) tend to be concentrated around a typical value. Many...
The density of the ISE and local limit laws for embedded trees (2006)
It has been known for a few years that the occupation measure of several models of embedded trees converges, after a suitable normalization, to the random measure called ISE (integrated SuperBrownian...
Partial fillup and search time in LC tries (2005)
Janson, Svante, Szpankowski, Wojciech
Andersson and Nilsson introduced in 1993 a level-compressed trie (in short: LC trie) in which a full subtree of a node is compressed to a single node of degree being the size of the subtree. Recent...
Congruence properties of depths in some random trees (2005)
Consider a random recusive tree with n vertices. We show that the number of vertices with even depth is asymptotically normal as n tends to infinty. The same is true for the number of vertices of...
The density of the ISE and local limit laws for embedded trees (2005)
Bousquet-Mélou, Mireille, Janson, Svante
It has been known for a few years that the occupation measure of several models of embedded trees converges, after a suitable normalization, to the random measure called ISE (Integrated SuperBrownian...
The density of the ISE and local limit laws for embedded trees (2005)
Bousquet-Mélou, Mireille, Janson, Svante
It has been known for a few years that the occupation measure of several models of embedded trees converges, after a suitable normalization, to the random measure called ISE (Integrated SuperBrownian...
The density of the ISE and local limit laws for embedded trees (2005)
Bousquet-Mélou, Mireille, Janson, Svante
It has been known for a few years that the occupation measure of several models of embedded trees converges, after a suitable normalization, to the random measure called ISE (Integrated SuperBrownian...
The density of the ISE and local limit laws for embedded trees (2005)
Bousquet-Mélou, Mireille, Janson, Svante
It has been known for a few years that the occupation measure of several models of embedded trees converges, after a suitable normalization, to the random measure called ISE (Integrated SuperBrownian...
Rounding of continuous random variables and oscillatory asymptotics (2005)
We study the characteristic function and moments of the integer-valued random variable $\lfloor X+\alpha\rfloor$, where $X$ is a continuous random variables. The results can be regarded as exact...
A simple solution to the k-core problem (2005)
Janson, Svante, Luczak, Malwina
We study the k-core of a random (multi)graph on n vertices with a given degree sequence. We let n tend to infinity. Then, under some regularity conditions on the degree sequences, we give conditions...
Spread-out percolation in R^d (2005)
Bollobas, Bela, Janson, Svante, Riordan, Oliver
Let $X$ be either $Z^d$ or the points of a Poisson process in $R^d$ of intensity 1. Given parameters $r$ and $p$, join each pair of points of $X$ within distance $r$ independently with probability...
Rainbow Hamilton cycles in random regular graphs (2005)
Janson, Svante, Wormald, Nicholas
A rainbow subgraph of an edge-coloured graph has all edges of distinct colours. A random d-regular graph with d even, and having edges coloured randomly with d/2 of each of n colours, has a rainbow...
We study a point process describing the asymptotic behavior of sizes of the largest components of the random graph G(n,p) in the critical window p=n^{-1}+lambda n^{-4/3}. In particular, we show that...
The phase transition in inhomogeneous random graphs (2005)
Bollobas, Bela, Janson, Svante, Riordan, Oliver
We introduce a very general model of an inhomogenous random graph with independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling...
Superreplication of options on several underlying assets (2005)
Ekström, Erik, Janson, Svante, Tysk, Johan
We investigate the conditions on a hedger, who overestimates the (time- and level-dependent) volatility, to superreplicate a convex claim on several underlying assets. It is shown that the classic...
Individual displacements in hashing with coalesced chains (2005)
We study the asymptotic distribution of the displacements in hashing with coalesced chains, for both late-insertion and early-insertion. Asymptotic formulas for means and variances follow. The method...
Superreplication of options on several underlying assets (2005)
Ekström, Erik, Janson, Svante, Tysk, Johan
We investigate the conditions on a hedger, who overestimates the (time- and level-dependent) volatility, to superreplicate a convex claim on several underlying assets. It is shown that the classic...
Asymptotic degree distribution in random recursive trees (2005)
Abstract. The distributions of vertex degrees in random recursive trees and random plane recursive trees are shown to be asymptotically normal. Formulas are given for the asymptotic variances and...
Convergence of coined quantum walks in R d (2005)
Alex D. Gottlieb, Svante Janson, Petra F. Scudo
Coined quantum walks may be interpreted as the motion in position space of a quantum particle with a spin degree of freedom; the dynamics are determined by iterating a unitary transformation which is...
Partial Fillup and Search Time in LC Tries (2005)
Svante Janson, Wojciech Szpankowski
Andersson and Nilsson introduced in 1993 a level-compressed trie (in short: LC trie) in which a full subtree of a node is compressed to a single node of degree being the size of the subtree. Recent...
Individual displacements for linear probing hashing with different insertion policies (2005)
Abstract. We study the distribution of the individual displacements in hashing with linear probing for three different versions: First Come, Last Come and Robin Hood. Asymptotic distributions and...
Congruence properties of depths in some random trees Preprint arXiv:math.PR/0509471 (2005)
Abstract. Consider a random recursive tree with n vertices. We show that the number of vertices with even depth is asymptotically normal as n → ∞. The same is true for the number of vertices of...
Limit theorems for triangular urn schemes. Probab. Theory Related Fields (2005)
Abstract. We study a generalized Pólya urn with balls of two colours and a triangular replacement matrix; the urn is not required to be balanced. We prove limit theorems describing the asymptotic...
Asymptotic degree distribution in random recursive trees (2005)
Abstract. The distributions of vertex degrees in random recursive trees and random plane recursive trees are shown to be asymptotically normal. Formulas are given for the asymptotic variances and...
Convergence of coined quantum walks in R d (2005)
Alex D. Gottlieb, Svante Janson, Petra F. Scudo
Coined quantum walks may be interpreted as the motion in position space of a quantum particle with a spin degree of freedom; the dynamics are determined by iterating a unitary transformation which is...
A simple solution to the k-core problem (2005)
Abstract. We study the k-core of a random (multi)graph on n vertices with a given degree sequence. We let n → ∞. Then, under some regularity conditions on the degree sequences, we give conditions...
Congruence properties of depths in some random trees Preprint arXiv:math.PR/0509471 (2005)
Abstract. Consider a random recursive tree with n vertices. We show that the number of vertices with even depth is asymptotically normal as n → ∞. The same is true for the number of vertices of...
Individual Displacements for Linear Probing Hashing with Different Insertion Policies (2005)
We study the distribution of the individual displacements in hashing with linear probing for three different versions: First Come, Last Come and Robin Hood. Asymptotic distributions and their moments...
The Center of Mass of the ISE and the Wiener Index of Trees (2004)
Janson, Svante; Uppsala University; Svante.janson@math.uu.se, Chassaing, Philippe; Institut Elie Cartan; Chassain@iecn.u-nancy.fr
We derive the distribution of the center of mass S of the integrated superBrownian excursion (ISE) from the asymptotic distribution of the Wiener index for simple trees. Equivalently, this is the...
Branching Processes, and Random-Cluster Measures on Trees (2004)
Grimmett, Geoffrey, Janson, Svante
Random-cluster measures on infinite regular trees are studied in conjunction with a general type of `boundary condition', namely an equivalence relation on the set of infinite paths of the tree. The...
Robust reconstruction on trees is determined by the second eigenvalue (2004)
Janson, Svante, Mossel, Elchanan
Consider a Markov chain on an infinite tree T=(V,E) rooted at ρ. In such a chain, once the initial root state σ({ρ}) is chosen, each vertex iteratively chooses its state from the one of its parent...
Robust reconstruction on trees is determined by the second eigenvalue (2004)
Janson, Svante, Mossel, Elchanan
Consider a Markov chain on an infinite tree T=(V,E) rooted at \rho. In such a chain, once the initial root state \sigma(\rho) is chosen, each vertex iteratively chooses its state from the one of its...
Convergence of coined quantum walks on d-dimensional Euclidean space (2004)
Gottlieb, Alex D., Janson, Svante, Scudo, Petra F.
Coined quantum walks may be interpreted as the motion in position space of a quantum particle with a spin degree of freedom; the dynamics are determined by iterating a unitary transformation which is...
Large deviations for sums of partly dependent random variables (2004)
Abstract. We use and extend a method by Hoeffding to obtain strong large deviation bounds for sums of dependent random variables with suitable dependency structure. The method is based on breaking up...
Preservation of convexity of solutions to parabolic equations (2004)
Abstract. In the present paper we find necessary and sufficient conditions on the coefficients of a parabolic equation for convexity to be preserved. A parabolic equation is said to preserve...
Upper tails for subgraph counts in random graphs (2004)
Svante Janson, Krzysztof Oleszkiewicz, Ruci Ński
Abstract. Let G be a fixed graph and let XG be the number of copies of G contained in the random graph G(n, p). We prove exponential bounds on the upper tail of XG which are best possible up to a...
Abstract. A functional limit theorem is proved for multitype continuous time Markov branching processes. As consequences, we obtain limit theorems for the branching process stopped by some stopping...
On Average Sequence Complexity (2004)
Svante Janson, Stefano Lonardi, Wojciech Szpankowski
In this paper we study the average behavior of the number of distinct substrings in a text of size n over an alphabet of cardinality k. This quantity is called the complexity index and it captures...
Abstract. A functional limit theorem is proved for multitype continuous time Markov branching processes. As consequences, we obtain limit theorems for the branching process stopped by some stopping...
Convergence of coined quantum walks on Rd (2004)
Alex D. Gottlieb, Svante Janson, Petra F. Scudo
Abstract Coined quantum walks may be interpreted as the motion in position space of a quantum particlewith a spin degree of freedom; the dynamics are determined by iterating a unitary transformation...
Convergence of coined quantum walks on Rd (2004)
Alex D. Gottlieb, Svante Janson, Petra F. Scudo
Abstract Coined quantum walks may be interpreted as the motion in position space of a quantum particlewith a spin degree of freedom; the dynamics are determined by iterating a unitary transformation...
Preservation of convexity of solutions to parabolic equations (2004)
Abstract. In the present paper we find necessary and sufficient conditions on the coefficients of a parabolic equation for convexity to be preserved. A parabolic equation is said to preserve...
Large deviations for sums of partly dependent random variables (2004)
Abstract. We use and extend a method by Hoeffding to obtain strong large deviation bounds for sums of dependent random variables with suitable dependency structure. The method is based on breaking up...
Random records and cuttings in complete binary trees (2004)
Abstract. We study the number of records in a complete binary tree with randomly labeled vertices or edges. Equivalently, we may study the number of random cuttings required to eliminate a complete...
One-sided interval trees (2004)
Abstract. We give an alternative treatment and extension of some results of Itoh and Mahmoud on one-sided interval trees. The proofs are based on renewal theory, including a case with mixed...
Preservation of Convexity of Solutions to Parabolic Equations (2004)
In the present paper we find necessary and sufficient conditions on the coefficients of a parabolic equation for convexity to be preserved. A parabolic equation is said to preserve convexity if given...
Weak limits for quantum random walks (2003)
Grimmett, Geoffrey, Janson, Svante, Scudo, Petra
We formulate and prove a general weak limit theorem for quantum random walks in one and more dimensions. With $X_n$ denoting position at time $n$, we show that $X_n/n$ converges weakly as $n \to...
The center of mass of the ISE and the Wiener index of trees (2003)
Janson, Svante, Chassaing, Philippe
We derive the distribution of the center of mass $S$ of the integrated superBrownian excursion (ISE) {from} the asymptotic distribution of the Wiener index for simple trees. Equivalently, this is the...
Volatility time and properties of option prices (2003)
We use a notion of stochastic time, here called volatility time, to show convexity of option prices in the underlying asset if the contract function is convex as well as continuity and monotonicity...
The center of mass of the ISE and the Wiener index of trees (2003)
Janson, Svante, Chassaing, Philippe
We derive the distribution of the center of mass $S$ of the integrated superBrownian excursion (ISE) {from} the asymptotic distribution of the Wiener index for simple trees. Equivalently, this is the...
The center of mass of the ISE and the Wiener index of trees (2003)
Janson, Svante, Chassaing, Philippe
We derive the distribution of the center of mass $S$ of the integrated superBrownian excursion (ISE) {from} the asymptotic distribution of the Wiener index for simple trees. Equivalently, this is the...
The Wiener index of simply generated random trees (2003)
Abstract. Asymptotics are obtained for the mean, variance and higher moments as well as for the distribution of the Wiener index of a random tree from a simply generated family (or, equivalently, a...
The Wiener index of simply generated random trees (2003)
Abstract. Asymptotics are obtained for the mean, variance and higher moments as well as for the distribution of the Wiener index of a random tree from a simply generated family (or, equivalently, a...
Rademacher Chaos: Tail Estimates vs Limit Theorems (2003)
We study Rademacher chaos indexed by a sparse set which has a fractional combinatorial dimension. We obtain tail estimates for nite sums and a normal limit theorem as the size tends to in nity. The...
QUICKSORT WITH UNRELIABLE COMPARISONS: A PROBABILISTIC ANALYSIS (2003)
Laurent Alonso, Philippe Chassaing, Florent Gillet, Svante Janson, Edward M. Reingold, René Schott
Abstract. We provide a probabilistic analysis of the output of Quicksort when comparisons can err. 1.
Grimmett, Geoffrey, Janson, Svante
Pick n points independently at random in R^2, according to a prescribed probability measure mu, and let D^n_1 infinity to a Poisson process with a constant intensity c(mu). This result, and related...
Ideals in a forest, one-way infinite binary trees and the contraction method (2002)
Abstract. The analysis of an algorithm by Koda and Ruskey for listing ideals in a forest poset leads to a study of random binary trees and their limits as infinite random binary trees. The...
Ideals in a forest, one-way infinite binary trees and the contraction method (2002)
Abstract. The analysis of an algorithm by Koda and Ruskey for listing ideals in a forest poset leads to a study of random binary trees and their limits as innite random binary trees. The...
Ideals in a forest, one-way infinite binary trees and the contraction method (2002)
Abstract. The analysis of an algorithm by Koda and Ruskey for listing ideals in a forest poset leads to a study of random binary trees and their limits as infinite random binary trees. The...
James Allen Fill, Svante Janson
The number of comparisons Xn used by Quicksort to sort an array of n distinct numbers has mean µn of order n log n and standard deviation of order n. Using different methods, Régnier and Rösler...
Svante Janson, Elchanan Mossel
reconstruction on trees is determined by the second eigenvalue
Random Dyadic Tilings of the Unit Square (2002)
Svante Janson, Dana R, Joel Spencer
A “dyadic rectangle ” is a set of the form R = [a2 −s, (a+1)2 −s]×[b2 −t, (b+1)2 −t], where s and t are non-negative integers. A dyadic tiling is a tiling of the unit square with dyadic...
Geoffrey Grimmett, Svante Janson
Pick n points independently at random in R , according to a prescribed probability measure , and let 2 : : : be the areas of the triangles thus formed, in non-decreasing order. If is absolutely...
James Allen Fill, Svante Janson
The number of comparisons Xn used by Quicksort to sort an array of n distinct numbers has mean µn of order n log n and standard deviation of order n. Using different methods, Régnier and Rösler...
Random Dyadic Tilings of the Unit Square (2002)
Svante Janson, Dana Randall, Dana R, Joel Spencer
A "dyadic rectangle" is a set of the form R = [a2 -s , (a+1)2 -s ][b2 -t , (b+1)2 -t ], where s and t are non-negative integers. A dyadic tiling is a tiling of the unit square with dyadic...
The infamous upper tail (2002)
Svante Janson, Andrzej Ruciń Ski
ABSTRACT: Let �be afinite index set and k�1agiven integer. Let further ��[�] �k bean arbitrary family of kelement subsets of �. Consider a(binomial) random subset � p of �, where p...
Chassaing, Philippe, Janson, Svante
We describe a Vervaat-like path transformation for the reflected Brownian bridge conditioned on its local time at 0: up to random shifts, this process equals the two processes constructed froma...
Moment convergence in conditional limit theorems (2001)
Consider a sum ∑1NYi of random variables conditioned on a given value of the sum ∑1NXi of some other variables, where Xi and Yi are dependent but the pairs (Xi,Yi) form an i.i.d.\ sequence. We...
Approximating the limiting Quicksort distribution (2001)
Fill, James Allen, Janson, Svante
The limiting distribution of the normalized number of comparisons used by Quicksort to sort an array of n numbers is known to be the unique fixed point with zero mean of a certain distributional...
Fill, James Allen, Janson, Svante
The number of comparisons X_n used by Quicksort to sort an array of n distinct numbers has mean mu_n of order n log n and standard deviation of order n. Using different methods, Regnier and Roesler...
Approximating the Limiting Quicksort Distribution (2001)
James Allen Fill, Svante Janson
The limiting distribution of the normalized number of comparisons used by Quicksort to sort an array of n numbers is known to be the unique xed point with zero mean of a certain distributional...
Remarks to Random Dyadic Tilings of the Unit Square (2001)
The note is informal, and not intended for publication. 1 Number of edges in the graph T n Let en be the number of edges in the graph Tn (see Section 2 and Problem 2.8). Thus e0 = 0, e1 = 1, e2 =...
Random Dyadic Tilings of the Unit Square (2001)
Svante Janson, Dana R, Joel Spencer
A “dyadic rectangle ” is a set of the form R = [a2 −s, (a+1)2 −s]×[b2 −t, (b+1)2 −t], where s and t are non-negative integers. A dyadic tiling is a tiling of the unit square with dyadic...
Moment convergence in conditional limit theorems (2001)
Abstract. Consider a sum � N 1 Yi of random variables conditioned on a given value of the sum � N 1 Xi of some other variables, where Xi and Yi are dependent but the pairs (Xi, Yi) form an i.i.d....
The Infamous Upper Tail (2001)
Svante Janson, Andrzej Rucinski
Let be a nite index set and k 1 a given integer. Let further S [] be an arbitrary family of k element subsets of . Consider a (binomial) random subset p of , where p = (p i : i 2 ) and a random...
Brownian bridge conditioned on its local time at 0
A Characterization of the Set of Fixed Points of the Quicksort Transformation (2000)
Fill, James Allen; The Johns Hopkins University; Jimfill@jhu.edu, Janson, Svante; Uppsala University; Svante.janson@math.uu.se
The limiting distribution m of the normalized number of key comparisons required by the Quicksort sorting algorithm is known to be the unique fixed point of a certain distributional transformation T...
Smoothness and decay properties of the limiting Quicksort density function (2000)
Fill, James Allen, Janson, Svante
Using Fourier analysis, we prove that the limiting distribution of the standardized random number of comparisons used by Quicksort to sort an array of n numbers has an everywhere positive and...
A characterization of the set of fixed points of the Quicksort transformation (2000)
Fill, James Allen, Janson, Svante
The limiting distribution \mu of the normalized number of key comparisons required by the Quicksort sorting algorithm is known to be the unique fixed point of a certain distributional transformation...
The deletion method for upper tail estimates (2000)
Abstract. We present a new method to show concentration of the upper tail of random variables that can be written as sums of variables with plenty of independence. We compare our method with the...
Smoothness and Decay Properties of the Limiting Quicksort Density Function (2000)
James Allen Fill, Svante Janson
Using Fourier analysis, we prove that the limiting distribution of the standardized random number of comparisons used by Quicksort to sort an array of n numbers has an everywhere positive and...
Asymptotic Distribution For The Cost Of Linear Probing Hashing (2000)
. We study moments and asymptotic distributions of the construction cost, measured as the total displacement, for hash tables using linear probing. Four different methods are employed for different...
Approximations of the Limiting Quicksort Distribution (2000)
James Allen Fill, Svante Janson, This Is, A Draft
THIS IS A DRAFT. Date. June 30, 2000. 1 Research supported by NSF grant DMS--9803780, and by the Acheson J. Duncan Fund for the Advancement of Research in Statistics. 1 1 Introduction and summary The...
Tensors And Differential Forms (2000)
Introduction The purpose of these notes is to give a quick course on tensors in general differentiable manifolds, as a complement to standard textbooks. Most proofs are quite straightforward, and are...
Growth Of Components In Random Graphs (2000)
. The creation and growth of components of a given complexity in a random graph process are studied. In particular, the expected number and total size of all such components is found. It follows that...
Moment Convergence In Conditional Limit Theorems (2000)
. Consider a sum P N 1 Y i of random variables conditioned on a given value of the sum P N 1 X i of some other variables, where X i and Y i are dependent but the pairs (X i ; Y i ) form an i.i.d....
A Characterization of the Set of Fixed Points of the Quicksort Transformation (2000)
James Allen Fill, Svante Janson
The limiting distribution of the normalized number of key comparisons required by the Quicksort sorting algorithm is known to be the unique fixed point of a certain distributional transformation T...
Smoothness and Decay Properties of the Limiting Quicksort Density Function (2000)
James Allen Fill, Svante Janson
Using Fourier analysis, we prove that the limiting distribution of the standardized random number of comparisons used by Quicksort to sort an array of n numbers has an everywhere positive and...
A Characterization of the Set of Fixed Points of the Quicksort Transformation (2000)
James Allen Fill, Svante Janson
The limiting distribution of the normalized number of key comparisons required by the Quicksort sorting algorithm is known to be the unique fixed point of a certain distributional transformation T...
he integers 1; : : : ; n, and then randomly selecting (by drawing without replacement) m of the \Gamma n 2 \Delta possible edges. A closely related model, denoted by for example G n;p , where 0 p 1,...
James Allen Fill, Svante Janson
Using Fourier analysis, we prove that the limiting distribution of the standardized random number of comparisons used by Quicksort to sort an array of n numbers has an everywhere positive and...
The deletion method for upper tail estimates (2000)
Abstract. We present a new method to show concentration of the upper tail of random variables that can be written as sums of variables with plenty of independence. The method is formally different...
The deletion method for upper tail estimates (2000)
Abstract. We present a new method to show concentration of the upper tail of random variables that can be written as sums of variables with plenty of independence. The method is formally different...
Svante Janson, Andrzej Ruciński, A. Mickiewicz
Let Γ be a finite index set and k ≥ 1 a given integer. Let further S ⊆ [Γ] ≤k be an arbitray family of k element subsets of Γ. Consider a (binomial) random subset Γp of Γ, where p = (pi: i...
James Allen Fill, Svante Janson
The limiting distribution µ of the normalized number of key comparisons required by the Quicksort sorting algorithm is known to be the unique fixed point of a certain distributional transformation T...
James Allen Fill, Svante Janson
The limiting distribution µ of the normalized number of key comparisons required by the Quicksort sorting algorithm is known to be the unique fixed point of a certain distributional transformation T...
James Allen Fill, Svante Janson
Using Fourier analysis, we prove that the limiting distribution of the standardized random number of comparisons used by Quicksort to sort an array of n numbers has an everywhere positive and...
Laurent Alonso, Philippe Chassaing, Florent Gillet, Svante Janson, Edward M. Reingold, René Schott
Abstract. We provide a probabilistic analysis of the output of Quicksort when comparisons can err. 1.
Philippe Chassaing, Svante Janson
We describe a Vervaat-like path transformation for the reflected Brownian bridge conditioned on its local time at 0: up to random shifts, this process equals the two processes constructed from a...
. We prove that a random Boolean 3-SAT formula on n variables with 4:596n clauses is almost certainly unsatisfiable, in the sense that the probability of it being satisfiable tends to 0 as n !1. 1....
Philippe Chassaing, Svante Janson
We describe a Vervaat-like path transformation for the reected Brownian bridge conditioned on its local time at 0: up to random shifts, this process equals the two processes constructed from a...
Anant P. Godbole, Svante Janson, Nicolas W. Locantore, Rebecca Rapoport
A subset A of the set [n] = f1; 2; : : : ; ng, jAj = k, is said to form a Sidon (or B h ) sequence, h 2, if each of the sums a 1 + a 2 + : : : + a h ; a 1 a 2 : : : a h ; a i 2 A, are distinct. We...
On Concentration Of Probability (1999)
. We give a survey of several methods to obtain sharp concentration results, typically with exponentially small error probabilities, for random variables occuring in combinatorial probability....
Laurent Alonso, Philippe Chassaing, Florent Gillet, Svante Janson, Edward M. Reingold, ...
We provide a probabilistic analysis of the output of Quicksort when comparisons can err. 1.
Q Spaces of Several Real Variables (1998)
Matts Essén, Svante Janson, Lizhong Peng, Jie Xiao
. For ff 2 (\Gamma1; 1), let Q ff (R n ) be the space of all measurable functions with sup[`(I)] 2ff\Gamman Z I Z I jf(x) \Gamma f(y)j 2 jx \Gamma yj n+2ff dx dy ! 1; where the supremum is taken over...
One, Two And Three Times log n/n For Paths In A Complete Graph With Random Weights (1998)
. Consider the minimal weights of paths between two points in a complete graph Kn with random weights on the edges, the weights being e.g. uniformly distributed. It is shown that, asymptotically,...
Analysis of an Asymmetric Leader Election Algorithm (1997)
Janson, Svante, Szpankowski, Wojciech
We consider a leader election algorithm in which a set of distributed objects (people, computers, etc.) try to identify one object as their leader. The election process is randomized, that is, at...
Analysis of an Asymmetric Leader Election Algorithm (1997)
Janson, Svante, Szpankowski, Wojciech
We consider a leader election algorithm in which a set of distributed objects (people, computers, etc.) try to identify one object as their leader. The election process is randomized, that is, at...
Analysis of an Asymmetric Leader Election Algorithm (1997)
Janson, Svante, Szpankowski, Wojciech
We consider a leader election algorithm in which a set of distributed objects (people, computers, etc.) try to identify one object as their leader. The election process is randomized, that is, at...
Analysis of an asymmetric leader election algorithm (1997)
Svante Janson, Wojciech Szpankowski
We consider a leader election algorithm in which a set of distributed objects (people, computers, etc.) try to identify one object as their leader. The election process is randomized, that is, at...
Analysis of an Asymmetric Leader Election Algorithm (1997)
Svante Janson, Svante Janson, Wojciech Szpankowski, Wojciech Szpankowski, Projet Mistral
: We consider a leader election algorithm in which a set of distributed objects (people, computers, etc.) try to identify one object as their leader. The election process is randomized, that is, at...
Hook lengths in a skew Young diagram (1997)
Regev and Vershik (Electronic J. Combinatorics 4 (1997), #R22) have obtained some properties of the set of hook lengths for certain skew Young diagrams, using asymptotic calculations of character...
. The minimal weight of a spanning tree in a complete graph Kn with independent, uniformly distributed random weights on the edges, is shown to have an asymptotic normal distribution. The proof uses...
Analysis of an Asymmetric Leader Election Algorithm (1997)
Svante Janson, Wojciech Szpankowski
We consider a leader election algorithm in which a set of distributed objects (people, computers, etc.) try to identify one object as their leader. The election process is randomized, that is, at...
New Versions of Suen's Correlation Inequality (1997)
This paper has benefitted from discussions with participants of the Eighth International Conference on Random Structures and Algorithms in Pozna'n in August 1997. In particular, I am grateful to...
Hook lengths in a skew Young diagram (1997)
Regev and Vershik (Electronic J. Combinatorics 4 (1997), #R22) have obtained some properties of the set of hook lengths for certain skew Young diagrams, using asymptotic calculations of character...
Shellsort With Three Increments (1997)
Svante Janson, Donald E. Knuth
. A perturbation technique can be used to simplify and sharpen A. C. Yao's theorems about the behavior of shellsort with increments (h; g; 1). In particular, when h = \Theta(n 7=15 ) and g =...
Perfect Matchings in Random s-Uniform Hypergraphs (1997)
this paper we consider the question of whether a random s-uniform hypergraph contains a perfect matching. More precisely, where [k] = f1; 2; : : : ; kg,
Shellsort with three increments (1996)
Janson, Svante, Knuth, Donald E.
A perturbation technique can be used to simplify and sharpen A. C. Yao's theorems about the behavior of shellsort with increments $(h,g,1)$. In particular, when $h=\Theta(n^{7/15})$ and...
Random Covering Designs (1996)
Anant P. Godbole, Svante Janson
A t \Gamma (n; k; ) covering design (n k ? t 2) consists of a collection of k-element subsets (blocks) of an n-element set X such that each t-element subset of X occurs in at least blocks. Let = 1...
Analysis of an Asymmetric Leader Election Algorithm (1996)
Svante Janson, Wojciech Szpankowski
We consider a leader election algorithm in which a set of distributed objects (people, computers, etc.) try to identify one object as their leader. The election process is randomized, that is, at...
On The Length Of The Longest Increasing Subsequence In A Random Permutation (1995)
. Complementing the results claiming that the maximal length Ln of an increasing subsequence in a random permutation of f1; 2; : : : ; ng is highly concentrated, we show that Ln is not concentrated...
Volume 111, number 534 (Third of snumbers)
Linear Extensions Of A Random Partial Order (1994)
Noga Alon, Béla Bollobás, Graham Brightwell, Svante Janson
. We study asymptotics of the number of linear extensions of the random Gn;p partial order, where p is fixed and n !1. In particular, it is shown that the distribution is asymptotically log-normal....
The Random-Cluster Model On The Complete Graph (1994)
Béla Bollobás, Geoffrey Grimmett, Svante Janson
. The random-cluster model of Fortuin and Kasteleyn contains as special cases the percolation, Ising, and Potts models of statistical physics. When the underlying graph is the complete graph on n...
Coupling And Poisson Approximation (1994)
. We give an overview of the Stein--Chen method for establishing Poisson approximations of various random variables. Couplings of certain variables are used to gives explicit bounds for the total...
Large Deviation Inequalities For Sums Of Indicator Variables (1994)
Some new Chernoff type bounds are given for the tail probabilities P(X \Gamma EX a) and P(X \Gamma EX a) when X is a random variable that can be written as a sum of indicator variables that are...
The birth of the giant component (1993)
Janson, Svante, Knuth, Donald E., Łuczak, Tomasz, Pittel, Boris
Limiting distributions are derived for the sparse connected components that are present when a random graph on $n$ vertices has approximately $\half n$ edges. In particular, we show that such a graph...
Intermediate Hankel Operators On The Bergman Space (1993)
Svante Janson, Richard Rochberg
this paper will be with some operators which are intermediate between these two; that is, R for which H
Random Regular Graphs: Asymptotic Distributions And Contiguity (1993)
. The asymptotic distribution of the number of Hamilton cycles in a random regular graph is determined. The limit distribution is of an unusual type; it is the distribution of a variable whose...
Random coverings and related problems /--by Svante Janson. (1984)
Diss. : Mathematical statistics : Uppsala : 1984.
On dominations between measures of dependence
Bradley, Richard C., Bryc, Wlodzimierz, Janson, Svante
Suppose one has two measures of dependence between two or more families of random variables. One of the measures is said to "dominate" the other if the latter becomes arbitrarily small as the former...
Tightness and weak convergence for jump processes
The aim of this note is to extend tightness criteria for random measures and simple point processes to processes with general jump distributions.
On the limiting distribution of the number of [`]near-matches'
Rao Jammalamadaka, S., Janson, Svante
When (R1,...,Rn) is a random permutation of the numbers (1,...,n), a [`]near-match' at the ith place is defined to have occured if Ri - i < k, for some fixed integer k. This note studies the...
Rademacher Chaos: Tail Estimates vs Limit Theorems
We study Rademacher chaos indexed by a sparse set which has a fractional combinatorial dimension. We obtain tail estimates for nite sums and a normal limit theorem as the size tends to in nity. The...