Results 21 to 30 of about 93 (85)
Persisting randomness in randomly growing discrete structures: graphs and search trees [PDF]
Discrete Mathematics & Theoretical Computer Science, 2015 The successive discrete structures generated by a sequential algorithm from random input constitute a Markov chain that may exhibit long term dependence on its first few input values.
Rudolf Grübel
doaj +1 more source
Random subgraphs of certain graph powers
International Journal of Mathematics and Mathematical Sciences, Volume 32, Issue 5, Page 285-292, 2002., 2002 We determine the limiting probability that a random subgraph of the Cartesian power Kan or of Ka,an is connected.
Lane Clark
wiley +1 more source
Queues, random graphs and branching processes
International Journal of Stochastic Analysis, Volume 1, Issue 3, Page 223-243, 1988., 1988 In this paper it is shown that certain basic results of queueing theory can be used successfully in solving various problems of random graphs and branching processes.
Lajos Takács
wiley +1 more source
The Percolation Process on a Tree Where Infinite Clusters are Frozen [PDF]
, 1999 Modify the usual percolation process on the infinite binary tree by forbidding infinite clusters to grow further. The ultimate configuration will consist of both infinite and finite clusters.
ALDOUS, DAVID J, David J. Aldous
core +1 more source
The Largest Component in Critical Random Intersection Graphs
Discussiones Mathematicae Graph Theory, 2018 In this paper, through the coupling and martingale method, we prove the order of the largest component in some critical random intersection graphs is n23$n^{{2 \over 3}}$ with high probability and the width of scaling window around the critical ...
Wang Bin, Wang Longmin, Xiang Kainan
doaj +1 more source
SYMMETRIC AND ASYMMETRIC RAMSEY PROPERTIES IN RANDOM HYPERGRAPHS
Forum of Mathematics, Sigma, 2017 A celebrated result of Rödl and Ruciński states that for every graph $F$ , which is not a forest of stars and paths of length 3, and fixed number of colours
LUCA GUGELMANN +5 more
doaj +1 more source
Ramsey Properties of Random Graphs and Folkman Numbers
Discussiones Mathematicae Graph Theory, 2017 For two graphs, G and F, and an integer r ≥ 2 we write G → (F)r if every r-coloring of the edges of G results in a monochromatic copy of F. In 1995, the first two authors established a threshold edge probability for the Ramsey property G(n, p) → (F)r ...
Rödl Vojtěch +2 more
doaj +1 more source
Limit theorems for the weights and the degrees in anN-interactions random graph model
Open Mathematics, 2016 A random graph evolution based on interactions of N vertices is studied. During the evolution both the preferential attachment rule and the uniform choice of vertices are allowed. The weight of an M-clique means the number of its interactions.
Fazekas István, Porvázsnyik Bettina
doaj +1 more source
EIGENVALUES AND LINEAR QUASIRANDOM HYPERGRAPHS
Forum of Mathematics, Sigma, 2015 Let $p(k)$ denote the partition function of $k$. For each $k\geqslant 2$, we describe a list of $p(k)-1$ quasirandom properties that a $k$-uniform hypergraph can have. Our work connects previous notions on linear hypergraph quasirandomness by Kohayakawa,
JOHN LENZ, DHRUV MUBAYI
doaj +1 more source
On the length of a random minimum spanning tree
, 2016 We study the expected value of the length Ln of the minimum spanning tree of the complete graph Kn when each edge e is given an independent uniform [0, 1] edge weight.
Janson, Svante, +14 more
core +1 more source