| 1. |
- Addario-Berry, Louigi, et al.
(författare)
-
On the Spread of Random Graphs
- 2014
-
Ingår i: Combinatorics, probability & computing. - 0963-5483 .- 1469-2163. ; 23:4, s. 477-504
-
Tidskriftsartikel (refereegranskat)abstract
- The spread of a connected graph G was introduced by Alon, Boppana and Spencer [1], and measures how tightly connected the graph is. It is defined as the maximum over all Lipschitz functions f on V(G) of the variance of f(X) when X is uniformly distributed on V(G). We investigate the spread for certain models of sparse random graph, in particular for random regular graphs G(n,d), for Erdos-Renyi random graphs G(n,p) in the supercritical range p > 1/n, and for a `small world' model. For supercritical G(n,p), we show that if p = c/n with c > 1 fixed, then with high probability the spread of the giant component is bounded, and we prove corresponding statements for other models of random graphs, including a model with random edge lengths. We also give lower bounds on the spread for the barely supercritical case when p = (1 + o(1))/n. Further, we show that for d large, with high probability the spread of G(n, d) becomes arbitrarily close to that of the complete graph K-n.
|
|
| 2. |
- Alm, Sven Erick, et al.
(författare)
-
A Counter-Intuitive Correlation in a Random Tournament
- 2011
-
Ingår i: Combinatorics, probability & computing. - 0963-5483 .- 1469-2163. ; 20:1, s. 1-9
-
Tidskriftsartikel (refereegranskat)abstract
- Consider a randomly oriented graph G = (V, E) and let a, s and b be three distinct vertices in V. We study the correlation between the events {a -> s} and {s -> b}. We show that, counter-intuitively, when G is the complete graph K-n, n >= 5, then the correlation is positive. (It is negative for n = 3 and zero for n = 4.) We briefly discuss and pose problems for the same question on other graphs.
|
|
| 3. |
- Andren, Lina J., et al.
(författare)
-
Avoiding Arrays of Odd Order by Latin Squares
- 2013
-
Ingår i: Combinatorics, probability & computing. - : Cambridge University Press (CUP). - 0963-5483 .- 1469-2163. ; 22:2, s. 184-212
-
Tidskriftsartikel (refereegranskat)abstract
- We prove that there is a constant c such that, for each positive integer k, every (2k + 1) x (2k + 1) array A on the symbols 1, ... , 2k + 1 with at most c(2k + 1) symbols in every cell, and each symbol repeated at most c(2k + 1) times in every row and column is avoidable; that is, there is a (2k + 1) x (2k + 1) Latin square S on the symbols 1, ... , 2k + 1 such that, for each i, j is an element of {1, ... , 2k + 1}, the symbol in position (i, j) of S does not appear in the corresponding cell in Lambda. This settles the last open case of a conjecture by Haggkvist. Using this result, we also show that there is a constant rho, such that, for any positive integer n, if each cell in an n x n array B is assigned a set of m andlt;= rho n symbols, where each set is chosen independently and uniformly at random from {1, ... , n}, then the probability that B is avoidable tends to 1 as n -andgt; infinity.
|
|
| 4. |
- Andrén, Lina, et al.
(författare)
-
Restricted completion of sparse partial Latin squares
- 2019
-
Ingår i: Combinatorics, probability & computing. - : Cambridge University Press. - 0963-5483 .- 1469-2163. ; 28:5, s. 675-695
-
Tidskriftsartikel (refereegranskat)abstract
- An n × n partial Latin square P is called α-dense if each row and column has at most αn non-empty cells and each symbol occurs at most αn times in P. An n × n array A where each cell contains a subset of {1,.., n} is a (βn, βn, βn)-array if each symbol occurs at most βn times in each row and column and each cell contains a set of size at most βn. Combining the notions of completing partial Latin squares and avoiding arrays, we prove that there are constants α, β > 0 such that, for every positive integer n, if P is an α-dense n × n partial Latin square, A is an n × n (βn, βn, βn)-array, and no cell of P contains a symbol that appears in the corresponding cell of A, then there is a completion of P that avoids A; that is, there is a Latin square L that agrees with P on every non-empty cell of P, and, for each i, j satisfying 1 ≤ i, j ≤ n, the symbol in position (i, j) in L does not appear in the corresponding cell of A.
|
|
| 5. |
- Berzunza Ojeda, Gabriel, et al.
(författare)
-
The distance profile of rooted and unrooted simply generated trees
- 2022
-
Ingår i: Combinatorics, probability & computing. - : Cambridge University Press. - 0963-5483 .- 1469-2163. ; 31:3, s. 368-410
-
Tidskriftsartikel (refereegranskat)abstract
- It is well known that the height profile of a critical conditioned Galton-Watson tree with finite offspring variance converges, after a suitable normalisation, to the local time of a standard Brownian excursion. In this work, we study the distance profile, defined as the profile of all distances between pairs of vertices. We show that after a proper rescaling the distance profile converges to a continuous random function that can be described as the density of distances between random points in the Brownian continuum random tree. We show that this limiting function a.s. is Holder continuous of any order alpha < 1, and that it is a.e. differentiable. We note that it cannot be differentiable at 0, but leave as open questions whether it is Lipschitz, and whether it is continuously differentiable on the half-line (0, infinity). The distance profile is naturally defined also for unrooted trees contrary to the height profile that is designed for rooted trees. This is used in our proof, and we prove the corresponding convergence result for the distance profile of random unrooted simply generated trees. As a minor purpose of the present work, we also formalize the notion of unrooted simply generated trees and include some simple results relating them to rooted simply generated trees, which might be of independent interest.
|
|
| 6. |
- Bhattacharya, Bhaswar B., et al.
(författare)
-
Fluctuations of subgraph counts in graphon based random graphs
- 2023
-
Ingår i: Combinatorics, probability & computing. - : Cambridge University Press. - 0963-5483 .- 1469-2163. ; 32:3, s. 428-464
-
Tidskriftsartikel (refereegranskat)abstract
- Given a graphon W and a finite simple graph H, with vertex set V(H), denote by X-n(H, W) the number of copies of H in a W-random graph on n vertices. The asymptotic distribution of X-n(H, W) was recently obtained by Hladky, Pelekis, and Sileikis [17] in the case where H is a clique. In this paper, we extend this result to any fixed graph H. Towards this we introduce a notion of H-regularity of graphons and show that if the graphon W is not H-regular, then Xn(H, W) has Gaussian fluctuations with scaling n(V(H)-1/2). On the other hand, if W is H-regular, then the fluctuations are of order n(V(H)-1) and the limiting distribution of X-n(H, W) can have both Gaussian and non-Gaussian components, where the non-Gaussian component is a (possibly) infinite weighted sum of centred chi-squared random variables with the weights determined by the spectral properties of a graphon derived from W. Our proofs use the asymptotic theory of generalised U-statistics developed by Janson and Nowicki [22]. We also investigate the structure of H-regular graphons for which either the Gaussian or the non-Gaussian component of the limiting distribution (but not both) is degenerate. Interestingly, there are also H-regular graphons W for which both the Gaussian or the non-Gaussian components are degenerate, that is, X-n(H, W) has a degenerate limit even under the scaling n(|V(H)|-1). We give an example of this degeneracy with H = K-1,K-3 (the 3-star) and also establish non-degeneracy in a few examples. This naturally leads to interesting open questions on higher order degeneracies.
|
|
| 7. |
- Bollobás, Béla, et al.
(författare)
-
Line-of-sight percolation
- 2009
-
Ingår i: Combinatorics, probability & computing. - 0963-5483 .- 1469-2163. ; 18:1-2, s. 83-106
-
Tidskriftsartikel (refereegranskat)abstract
- Given omega >= 1, let Z((omega))(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 omega in the other. (Thus Z((1))(2) is precisely Z(2).) Let p(c)(omega) be the critical probability for site percolation on Z((omega))(2) Extending recent results of Frieze, Kleinberg, Ravi and Debany, we show that lim(omega ->infinity) omega p(c)(omega) = log(3/2). We also prove analogues of this result for the n-by-n grid and in higher dimensions, the latter involving interesting connections to Gilbert's continuum percolation model. To prove our results, we explore the component of the origin in a certain non-standard way, and show that this exploration is well approximated by a certain branching random walk.
|
|
| 8. |
- Bollobas, Bela, et al.
(författare)
-
Monotone Cellular Automata in a Random Environment
- 2015
-
Ingår i: Combinatorics, probability & computing. - 0963-5483 .- 1469-2163. ; 24:4, s. 687-722
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper we study in complete generality the family of two-state, deterministic, monotone, local, homogeneous cellular automata in Z(d) with random initial configurations. Formally, we are given a set U = {X-1,...,X-m} of finite subsets of Z(d) \ {0}, and an initial set A(0) subset of Z(d) of 'infected' sites, which we take to be random according to the product measure with density p. At time t is an element of N, the set of infected sites A(t) is the union of A(t-1) and the set of all x is an element of Z(d) such that x + X is an element of A(t-1) for some X is an element of U. Our model may alternatively be thought of as bootstrap percolation on Z(d) with arbitrary update rules, and for this reason we call it U-bootstrap percolation. In two dimensions, we give a classification of U-bootstrap percolation models into three classes -supercritical, critical and subcritical - and we prove results about the phase transitions of all models belonging to the first two of these classes. More precisely, we show that the critical probability for percolation on (Z/nZ)(2) is (log n)(-Theta(1)) for all models in the critical class, and that it is n(-Theta(1)) for all models in the supercritical class. The results in this paper are the first of any kind on bootstrap percolation considered in this level of generality, and in particular they are the first that make no assumptions of symmetry. It is the hope of the authors that this work will initiate a new, unified theory of bootstrap percolation on Z(d).
|
|
| 9. |
- Brändén, Petter, et al.
(författare)
-
Multivariate Eulerian Polynomials and Exclusion Processes
- 2016
-
Ingår i: Combinatorics, probability & computing. - : Cambridge University Press. - 0963-5483 .- 1469-2163. ; 25:4, s. 486-499
-
Tidskriftsartikel (refereegranskat)abstract
- We give a new combinatorial interpretation of the stationary distribution of the (partially) asymmetric exclusion process on a finite number of sites in terms of decorated alternative trees and coloured permutations. The corresponding expressions of the multivariate partition functions are then related to multivariate generalisations of Eulerian polynomials for coloured permutations considered recently by N. Williams and the third author, and others. We also discuss stability and negative dependence properties satisfied by the partition functions.
|
|
| 10. |
- Cai, Xing Shi, et al.
(författare)
-
Inversions in Split Trees and Conditional Galton-Watson Treest
- 2019
-
Ingår i: Combinatorics, probability & computing. - 0963-5483 .- 1469-2163. ; 28:3, s. 335-364
-
Tidskriftsartikel (refereegranskat)abstract
- We study I(T), the number of inversions in a tree T with its vertices labelled uniformly at random, which is a generalization of inversions in permutations. We first show that the cumulants of I(T) have explicit formulas involving the k-total common ancestors of T (an extension of the total path length). Then we consider X-n, the normalized version of I(T-n), for a sequence of trees T-n. For fixed T-n's, we prove a sufficient condition for X-n to converge in distribution. As an application, we identify the limit of X-n for complete b-ary trees. For T(n )being split trees [16], we show that X-n converges to the unique solution of a distributional equation. Finally, when T-n's are conditional Galton-Watson trees, we show that X-n converges to a random variable defined in terms of Brownian excursions. By exploiting the connection between inversions and the total path length, we are able to give results that significantly strengthen and broaden previous work by Panholzer and Seitz [46].
|
|
