skip to main content


Title: Line percolation
Abstract

We study a new geometric bootstrap percolation model,line percolation, on thed‐dimensional integer grid. In line percolation with infection parameterr, infection spreads from a subsetof initially infected lattice points as follows: if there exists an axis‐parallel lineLwithror more infected lattice points on it, then every lattice point ofonLgets infected, and we repeat this until the infection can no longer spread. The elements of the setAare usually chosen independently, with some densityp, and the main question is to determine, the density at which percolation (infection of the entire grid) becomes likely. In this paper, we determineup to a multiplicative factor ofandup to a multiplicative constant asfor every fixed. We also determine the size of the minimal percolating sets in all dimensions and for all values of the infection parameter.

 
more » « less
PAR ID:
10049267
Author(s) / Creator(s):
 ;  ;  ;  
Publisher / Repository:
Wiley Blackwell (John Wiley & Sons)
Date Published:
Journal Name:
Random Structures & Algorithms
Volume:
52
Issue:
4
ISSN:
1042-9832
Page Range / eLocation ID:
p. 597-616
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    In 1990 Bender, Canfield, and McKay gave an asymptotic formula for the number of connected graphs onwith m edges, wheneverand. We give an asymptotic formula for the numberof connected r‐uniform hypergraphs onwith m edges, wheneveris fixed andwith, that is, the average degree tends to infinity. This complements recent results of Behrisch, Coja‐Oghlan, and Kang (the case) and the present authors (the case, ie, “nullity” or “excess”o(n)). The proof is based on probabilistic methods, and in particular on a bivariate local limit theorem for the number of vertices and edges in the largest component of a certain random hypergraph. The arguments are much simpler than in the sparse case; in particular, we can use “smoothing” techniques to directly prove the local limit theorem, without needing to first prove a central limit theorem.

     
    more » « less
  2. Abstract

    It is proved that for every countable structureand a computable successor ordinal α there is a countable structurewhich is‐least among all countable structuressuch thatis Σ‐definable in the αth jump. We also show that this result does not hold for the limit ordinal. Moreover, we prove that there is no countable structurewith the degree spectrumfor.

     
    more » « less
  3. Abstract

    Letbe the random directed graph onnvertices where each of thepossible arcs is present independently with probabilityp. A celebrated result of Frieze shows that ifthentypically has a directed Hamilton cycle, and this is best possible. In this paper, we obtain a strengthening of this result, showing that under the same condition, the number of directed Hamilton cycles inis typically. We also prove a hitting‐time version of this statement, showing that in the random directed graph process, as soon as every vertex has in‐/out‐degrees at least 1, there are typicallydirected Hamilton cycles.

     
    more » « less
  4. Abstract

    A graph is said to be‐universal if it contains every graph withnvertices and maximum degree at most Δ as a subgraph. Dellamonica, Kohayakawa, Rödl and Ruciński used a “matching‐based” embedding technique introduced by Alon and Füredi to show that the random graphis asymptotically almost surely‐universal for, a threshold for the property that every subset of Δ vertices has a common neighbor. This bound has become a benchmark in the field and many subsequent results on embedding spanning graphs of maximum degree Δ in random graphs are proven only up to this threshold. We take a step towards overcoming limitations of former techniques by showing thatis almost surely‐universal for.

     
    more » « less
  5. Abstract

    A graphGis said to be 2‐divisible if for all (nonempty) induced subgraphsHofG,can be partitioned into two setssuch thatand. (Heredenotes the clique number ofG, the number of vertices in a largest clique ofG). A graphGis said to be perfectly divisible if for all induced subgraphsHofG,can be partitioned into two setssuch thatis perfect and. We prove that if a graph is‐free, then it is 2‐divisible. We also prove that if a graph is bull‐free and either odd‐hole‐free orP5‐free, then it is perfectly divisible.

     
    more » « less