uu.seUppsala University Publications
Change search
Refine search result
1 - 22 of 22
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Ahlberg, Daniel
    et al.
    Stockholm Univ, Dept Math, S-10691 Stockholm, Sweden.
    Deijfen, Maria
    Stockholm Univ, Dept Math, S-10691 Stockholm, Sweden.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
    Competing first passage percolation on random graphs with finite variance degrees2019In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 55, no 3, p. 545-559Article in journal (Refereed)
    Abstract [en]

    We study the growth of two competing infection types on graphs generated by the configuration model with a given degree sequence. Starting from two vertices chosen uniformly at random, the infection types spread via the edges in the graph in that an uninfected vertex becomes type 1 (2) infected at rate lambda(1) (lambda(2)) times the number of nearest neighbors of type 1 (2). Assuming (essentially) that the degree of a randomly chosen vertex has finite second moment, we show that if lambda(1) = lambda(2), then the fraction of vertices that are ultimately infected by type 1 converges to a continuous random variable V is an element of (0,1), as the number of vertices tends to infinity. Both infection types hence occupy a positive (random) fraction of the vertices. If lambda(1) not equal lambda(2), on the other hand, then the type with the larger intensity occupies all but a vanishing fraction of the vertices. Our results apply also to a uniformly chosen simple graph with the given degree sequence.

  • 2.
    Ahlberg, Daniel
    et al.
    Stockholm Univ, Dept Math, SE-10691 Stockholm, Sweden.
    Griffiths, Simon
    PUC Rio, Dept Matemat, BR-22451900 Gavea, RJ, Brazil.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
    Morris, Robert
    Inst Nacl Matemat Pura & Aplicada, Estr Dona Castorina 110, BR-22460320 Rio De Janeiro, Brazil.
    Competition in growth and urns2019In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 54, no 2, p. 211-227Article in journal (Refereed)
    Abstract [en]

    We study survival among two competing types in two settings: a planar growth model related to two-neighbor bootstrap percolation, and a system of urns with graph-based interactions. In the planar growth model, uncolored sites are given a color at rate 0, 1 or infinity, depending on whether they have zero, one, or at least two neighbors of that color. In the urn scheme, each vertex of a graph G has an associated urn containing some number of either blue or red balls ( but not both). At each time step, a ball is chosen uniformly at random from all those currently present in the system, a ball of the same color is added to each neighboring urn, and balls in the same urn but of different colors annihilate on a one-for-one basis. We show that, for every connected graph G and every initial configuration, only one color survives almost surely. As a corollary, we deduce that in the two-type growth model on Z(2), one of the colors only infects a finite number of sites with probability one. We also discuss generalizations to higher dimensions and multi-type processes, and list a number of open problems and conjectures.

  • 3.
    Alm, Sven Erick
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Mathematical Statistics.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
    Linusson, Svante
    Correlations for Paths in Random Orientations of G(n, p) and G(n, m)2011In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 39, no 4, p. 486-506Article in journal (Refereed)
    Abstract [en]

    We study random graphs, both G(n, p) and G(n, m), with random orientations on the edges. For three fixed distinct vertices s, a, b we study the correlation, in the combined probability space, of the events {a -> s} and {s -> b}. For G(n, p), we prove that there is a p(c) = 1/2 such that for a fixed p < p(c) the correlation is negative for large enough n and for p > p(c) the correlation is positive for large enough n. We conjecture that for a fixed n >= 27 the correlation changes sign three times for three critical values of p. For G(n, m) it is similarly proved that, with p = m/((n)(2)), there is a critical p(c) that is the solution to a certain equation and approximately equal to 0.7993. A lemma, which computes the probability of non existence of any l directed edges in G(n, m), is thought to be of independent interest. We present exact recursions to compute P(a -> s) and P(a -> s, s -> b). We also briefly discuss the corresponding question in the quenched version of the problem.

  • 4. Bollobas, Bela
    et al.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
    Riordan, Oliver
    Sparse Random Graphs with Clustering2011In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 38, no 3, p. 269-323Article in journal (Refereed)
    Abstract [en]

    In 2007, we introduced a general model of sparse random graphs with (conditional) independence between the edges. The aim of this article is to present an extension of this model in which the edges are far from independent, and to prove several results about this extension. The basic idea is to construct the random graph by adding not only edges but also other small graphs. In other words, we first construct an inhomogeneous random hypergraph with (conditionally) independent hyperedges, and then replace each hyperedge by a (perhaps complete) graph. Although flexible enough to produce graphs with significant dependence between edges, this model is nonetheless mathematically tractable. Indeed, we find the critical point where a giant component emerges in full generality, in terms of the norm of a certain integral operator, and relate the size of the giant component to the survival probability of a certain (non-Poisson) multi-type branching process. While our main focus is the phase transition, we also study the degree distribution and the numbers of small subgraphs. We illustrate the model with a simple special case that produces graphs with power-law degree sequences with a wide range of degree exponents and clustering coefficients.

  • 5. Bollobas, Bela
    et al.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    Riordan, Oliver
    Spread-out percolation in R-d2007In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 31, no 2, p. 239-246Article in journal (Refereed)
    Abstract [en]

    Fix d≥ 2, and let X be either ℤd or the points of a Poisson process in ℝd of intensity 1. Given parameters r and p, join each pair of points of X within distance r independently with probability p. This is the simplest case of a spread-out percolation model studied by Penrose [Ann Appl Probab 3 (1993) 253276], who showed that, as r, the average degree of the corresponding random graph at the percolation threshold tends to 1, i.e., the percolation threshold and the threshold for criticality of the naturally associated branching process approach one another. Here we show that this result follows immediately from of a general result of [3] on inhomogeneous random graphs.

  • 6.
    Bollobas, Bela
    et al.
    Dept Pure Math & Math Stat, Wilberforce Rd, Cambridge CB3 0WB, England.;Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA.;London Inst Math Sci, 35a South St, London W1K 2XF, England..
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
    Scott, Alex
    Univ Oxford, Radcliffe Observ Quarter, Math Inst, Andrew Wiles Bldg,Woodstock Rd, Oxford OX2 6GG, England..
    Packing Random Graphs and Hypergraphs2017In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 51, no 1, p. 3-13Article in journal (Refereed)
    Abstract [en]

    We determine to within a constant factor the threshold for the property that two random k-uniform hypergraphs with edge probability p have an edge-disjoint packing into the same vertex set. More generally, we allow the hypergraphs to have different densities. In the graph case, we prove a stronger result, on packing a random graph with a fixed graph.

  • 7. Bollobás, Béla
    et al.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
    Riordan, Oliver
    On Covering by Translates of a Set2011In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 38, no 1-2, p. 33-67Article in journal (Refereed)
    Abstract [en]

    In this paper we study the minimal number tau(S, G) 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 on finite subsets in discrete groups, reviewing the classical results in this area, and generalizing them to a much broader context. For example, the worst-case efficiency when S has k elements is of order 1/log k. We show that if n(k) grows at a suitable rate with k, then almost every k-subset of any given group with order n comes close to this worst-case bound. In contrast, if n(k) grows very rapidly, or if k is fixed and n ->infinity, then almost every k-subset of the cyclic group with order n comes close to the optimal efficiency.

  • 8. Bollobás, Béla
    et al.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    Riordan, Oliver
    The phase transition in inhomogeneous random graphs2007In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 31, no 1, p. 3-122Article in journal (Refereed)
    Abstract [en]

    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 graphs arising in the real world do not have this property, having, for example, power-law degree distributions. Thus there has been a lot of recent interest in defining and studying "inhomogeneous" random graph models.

    One of the most studied properties of these new models is their "robustness", or, equivalently, the "phase transition" as an edge density parameter is varied. For G(n,p), p = c/n, the phase transition at c = 1 has been a central topic in the study of random graphs for well over 40 years.

    Many of the new inhomogeneous models are rather complicated; although there are exceptions, in most cases precise questions such as determining exactly the critical point of the phase transition are approachable only when there is independence between the edges. Fortunately, some models studied have this property already, and others can be approximated by models with independence.

    Here we introduce a very general model of an inhomogeneous random graph with (conditional) independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling corresponds to the p = c/n scaling for G(n, p) used to study the phase transition; also, it seems to be a property of many large real-world graphs. Our model includes as special cases many models previously studied.

    We show that, under one very weak assumption (that the expected number of edges is "what it should be"), many properties of the model can be determined, in particular the critical point of the phase transition, and the size of the giant component above the transition. We do this by relating our random graphs to branching processes, which are much easier to analyze.

    We also consider other properties of the model, showing, for example, that when there is a giant component, it is "stable": for a typical random graph, no matter how we add or delete o(n) edges, the size of the giant component does not change by more than o(n).

  • 9.
    Brightwell, Graham
    et al.
    London Sch Econ, Dept Math, London WC2A 2AE, England..
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
    Luczak, Malwina
    Queen Mary Univ London, Sch Math, London, England..
    The Greedy Independent Set in a Random Graph with Given Degrees2017In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 51, no 4, p. 565-586Article in journal (Refereed)
    Abstract [en]

    We analyse the size of an independent set in a random graph on n vertices with specified vertex degrees, constructed via a simple greedy algorithm: order the vertices arbitrarily, and, for each vertex in turn, place it in the independent set unless it is adjacent to some vertex already chosen. We find the limit of the expected proportion of vertices in the greedy independent set as n (the jamming constant), expressed as an integral whose upper limit is defined implicitly, valid whenever the second moment of a random vertex degree is uniformly bounded. We further show that the random proportion of vertices in the independent set converges in probability to the jamming constant as n. The results hold under weaker assumptions in a random multigraph with given degrees constructed via the configuration model.

  • 10. Devroye, Luc
    et al.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
    Distances Between Pairs of Vertices and Vertical Profile in Conditioned Galton-Watson Trees2011In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 38, no 4, p. 381-395Article in journal (Refereed)
    Abstract [en]

    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 proofs of this result, one probabilistic and the other using generating functions and singularity analysis. Moreover, the latter proof yields a more general estimate for generating functions, which is used to prove a conjecture by Bousquet-Melou and Janson (Bousquet-Melou and Janson, Ann Appl Probab 16 (2006) 1597-1632), saying that the vertical profile of a randomly labelled conditioned Galton-Watson tree converges in distribution, after suitable normalization, to the density of ISE (Integrated Superbrownian Excursion).

  • 11. Grimmett, Geoffrey
    et al.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
    Random Graphs with Forbidden Vertex Degrees2010In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 37, no 2, p. 137-175Article in journal (Refereed)
    Abstract [en]

    We study the random graph G 4 conditioned on the event that all vertex degrees he in some given subset S of the nonnegative interacts. Subject to a certain hypothesis on S. the empirical distribution of the vertex degrees is asymptotically Poisson with some parameter (mu) over cap men as the root of a certain "characteristic equation" of S that maximizes a certain function psi s(mu) Subject to a hypothesis on S. we obtain a partial description of the structure of such a random graph, including a condition for the existence (or not) of a giant component The requisite hypothesis is in many cases benign. and applications are presented to a number of choices for the set S including the sets of (respectively) even and odd numbers.

  • 12.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
    Asymptotic Equivalence and Contiguity of Some Random Graphs2010In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 36, no 1, p. 26-45Article in journal (Refereed)
    Abstract [en]

    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 be expected. One application is a simple proof of a recent result by van den Esker, van der Hofstad, and Hooghiemstra on the equivalence between graph distances for some random graph models.

  • 13.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
    Asymptotic Normality of Fringe Subtrees and Additive Functionals in Conditioned Galton-Watson Trees2016In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 48, no 1, p. 57-101Article in journal (Refereed)
    Abstract [en]

    We consider conditioned Galton-Watson trees and show asymptotic normality of additive functionals that are defined by toll functions that are not too large. This includes, as a special case, asymptotic normality of the number of fringe subtrees isomorphic to any given tree, and joint asymptotic normality for several such subtree counts. Another example is the number of protected nodes. The offspring distribution defining the random tree is assumed to have expectation 1 and finite variance; no further moment condition is assumed.

  • 14.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
    Patterns in random permutations avoiding the pattern 3212019In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 55, no 2, p. 249-270Article in journal (Refereed)
    Abstract [en]

    We consider a random permutation drawn from the set of 321-avoiding permutations of length n and show that the number of occurrences of another pattern sigma has a limit distribution, after scaling by n(m + l) where m is the length of sigma and l is the number of blocks in it. The limit is not normal, and can be expressed as a functional of a Brownian excursion.

  • 15.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    Random cutting and records in deterministic and random trees2006In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 29, no 2, p. 139-179Article in journal (Refereed)
    Abstract [en]

    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 labels.

    Limit theorems are given for this number, in particular when the tree is a random conditioned Galton-Watson tree. We consider both the distribution when both the tree and the cutting (or labels) are random and the case when we condition on the tree. The proofs are based on Aldous' theory of the continuum random tree.

  • 16.
    Janson, Svante
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    Luczak, Malwina J.
    A new approach to the giant component problem2009In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 34, no 2, p. 197-216Article in journal (Refereed)
    Abstract [en]

    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 conditions on the asymptotic shape of the degree sequence that imply that with high probability all the components are small, and other conditions that imply that with high probability there is a giant component and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these are the only two possibilities. In particular, we recover the results by Molloy and Reed on the size of the largest component in a random graph with a given degree sequence.

    We further obtain a new sharp result for the giant component just above the threshold, generalizing the case of G(n,p) with np = 1 + ω(n)n−1/3, where ω(n) → arbitrarily slowly.

    Our method is based on the properties of empirical distributions of independent random variables, and leads to simple proofs

  • 17.
    Janson, Svante
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    Luczak, Malwina J.
    A simple solution to the k-core problem2007In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 30, no 1-2, p. 50-62Article in journal (Refereed)
    Abstract [en]

    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 on the asymptotic shape of the degree sequence that imply that with high probability the k-core is empty and other conditions that imply that with high probability the k-core is non-empty and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these are the only two possibilities. In particular, we recover the result by Pittel, Spencer, and Wormald (J Combinator Theory 67 (1996), 111-151) on the existence and size of a k-core in G(n,p) and G(n,m), see also Molloy (Random Struct Algor 27 (2005), 124-135) and Cooper (Random Struct Algor 25 (2004), 353-375). Our method is based on the properties of empirical distributions of independent random variables and leads to simple proofs.

  • 18.
    Janson, Svante
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    Luczak, Malwina
    Windridge, Peter
    Law of Large Numbers for the SIR Epidemic on a Random Graph with Given Degrees2014In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 45, no 4, p. 724-761Article in journal (Refereed)
    Abstract [en]

    We study the susceptible-infective-recovered (SIR) epidemic on a random graph chosen uniformly subject to having given vertex degrees. In this model infective vertices infect each of their susceptible neighbours, and recover, at a constant rate. Suppose that initially there are only a few infective vertices. We prove there is a threshold for a parameter involving the rates and vertex degrees below which only a small number of infections occur. Above the threshold a large outbreak occurs with probability bounded away from zero. Our main result is that, conditional on a large outbreak, the evolutions of certain quantities of interest, such as the fraction of infective vertices, converge to deterministic functions of time. We also consider more general initial conditions for the epidemic, and derive criteria for a simple vaccination strategy to be successful. In contrast to earlier results for this model, our approach only requires basic regularity conditions and a uniformly bounded second moment of the degree of a random vertex. En route, we prove analogous results for the epidemic on the configuration model multigraph under much weaker conditions. Essentially, our main result requires only that the initial values for our processes converge, i.e. it is the best possible.

  • 19.
    Janson, Svante
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
    Riordan, Oliver
    Duality in Inhomogeneous Random Graphs, and the Cut Metric2011In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 39, no 3, p. 399-411Article in journal (Refereed)
    Abstract [en]

    The classical random graph model G(n, c/n) satisfies a "duality principle", in that removing the giant component from a supercritical instance of the model leaves (essentially) a subcritical instance. Such principles have been proved for various models; they are useful since it is often much easier to study the subcritical model than to directly study small components in the supercritical model. Here we prove a duality principle of this type for a very general class of random graphs with independence between the edges, defined by convergence of the matrices of edge probabilities in the cut metric.

  • 20.
    Janson, Svante
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
    Warnke, Lutz
    Univ Cambridge, Dept Pure Math & Math Stat, Cambridge CB3 0WB, England..
    The lower tail: Poisson approximation revisited2016In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 48, no 2, p. 219-246Article in journal (Refereed)
    Abstract [en]

    The well-known Janson's inequality gives Poisson-like upper bounds for the lower tail probability P(X(1-epsilon)EX) when X is the sum of dependent indicator random variables of a special form. We show that, for large deviations, this inequality is optimal whenever X is approximately Poisson, i.e., when the dependencies are weak. We also present correlation-based approaches that, in certain symmetric applications, yield related conclusions when X is no longer close to Poisson. As an illustration we, e.g., consider subgraph counts in random graphs, and obtain new lower tail estimates, extending earlier work (for the special case epsilon=1) of Janson, uczak and Ruciski.

  • 21.
    Janson, Svante
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
    Wormald, Nicholas
    Rainbow Hamilton cycles in random regular graphs2007In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 30, no 1-2, p. 35-49Article in journal (Refereed)
    Abstract [en]

    A rainbow subgraph of an edge-colored graph has all edges of distinct colors. A random d-regular graph with d even, and having edges colored randomly with d/2 of each of n colors, has a rainbow Hamilton cycle with probability tending to 1 as n → ∞, for fixed d ≥ 8.

  • 22.
    van der Hofstad, Remco
    et al.
    Eindhoven Univ Technol, Dept Math & Comp Sci, Eindhoven, Netherlands.
    Janson, Svante
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
    Luczak, Malwina
    Univ Melbourne, Sch Math & Stat, Parkville, Vic, Australia.
    Component structure of the configuration model: Barely supercritical case2019In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 55, no 1, p. 3-55Article in journal (Refereed)
    Abstract [en]

    We study near-critical behavior in the configuration model. Let D-n be the degree of a random vertex and nu n=E[Dn(Dn-1)]/E[Dn]; we consider the barely supercritical regime, where nu(n)-> 1 as n ->infinity, but nu n-1 n-1/3(E[Dn3])2/3. Let Dn* denote the size-biased version of D-n. We prove that there is a unique giant component of size n rho nEDn(1+o(1)), where rho(n) denotes the survival probability of a branching process with offspring distribution Dn*-1. This extends earlier results of Janson and Luczak, as well as those of Janson, Luczak, Windridge, and House, to the case where the third moment of D-n is unbounded. We further study the size of the largest component in the critical regime, where nu n-1=O(n-1/3(EDn3)2/3), extending and complementing results of Hatami and Molloy.

1 - 22 of 22
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf