Skip to main content
broken link fixed, cf. https://math.meta.stackexchange.com/a/34713/228959
Source Link
Glorfindel
  • 2.8k
  • 6
  • 28
  • 38

Has the technique of "sprinkling" been used in studying random matrices?  

In 1982, while studying the component sizes of random subgraphs of a hypercube, Ajtai, Komlós, and SzemerédiAjtai, Komlós, and Szemerédi introduced a technique that came to be known as sprinkling. In this technique, the edges of the random graph are exposed in rounds. To explain it, suppose that each edge $e$ is independently assigned a random Uniform$[0,1]$ variable $U_e$. Eventually, all edges with $U_e \leq p$ will be included in the graph. In the first round, however, for some subset of the edges, we only check whether $U_e \leq p-\epsilon$. In the second round, for the remaining edges for which we know $U_e > p-\epsilon$, we check whether $U_e \leq p$. (The last few edges are the ones being "sprinkled" on at the end.) The idea is that this additional, last-minute randomization can be used to ensure (or at least make it very likely) that some desirable graph property holds. A similar technique has also been used by percolation theorists.

Has the technique of sprinkling been used in the study of random Bernoulli matrices? Can you give me references?

Has the technique of "sprinkling" been used in studying random matrices?  

In 1982, while studying the component sizes of random subgraphs of a hypercube, Ajtai, Komlós, and Szemerédi introduced a technique that came to be known as sprinkling. In this technique, the edges of the random graph are exposed in rounds. To explain it, suppose that each edge $e$ is independently assigned a random Uniform$[0,1]$ variable $U_e$. Eventually, all edges with $U_e \leq p$ will be included in the graph. In the first round, however, for some subset of the edges, we only check whether $U_e \leq p-\epsilon$. In the second round, for the remaining edges for which we know $U_e > p-\epsilon$, we check whether $U_e \leq p$. (The last few edges are the ones being "sprinkled" on at the end.) The idea is that this additional, last-minute randomization can be used to ensure (or at least make it very likely) that some desirable graph property holds. A similar technique has also been used by percolation theorists.

Has the technique of sprinkling been used in the study of random Bernoulli matrices? Can you give me references?

Has the technique of "sprinkling" been used in studying random matrices?

In 1982, while studying the component sizes of random subgraphs of a hypercube, Ajtai, Komlós, and Szemerédi introduced a technique that came to be known as sprinkling. In this technique, the edges of the random graph are exposed in rounds. To explain it, suppose that each edge $e$ is independently assigned a random Uniform$[0,1]$ variable $U_e$. Eventually, all edges with $U_e \leq p$ will be included in the graph. In the first round, however, for some subset of the edges, we only check whether $U_e \leq p-\epsilon$. In the second round, for the remaining edges for which we know $U_e > p-\epsilon$, we check whether $U_e \leq p$. (The last few edges are the ones being "sprinkled" on at the end.) The idea is that this additional, last-minute randomization can be used to ensure (or at least make it very likely) that some desirable graph property holds. A similar technique has also been used by percolation theorists.

Has the technique of sprinkling been used in the study of random Bernoulli matrices? Can you give me references?

Source Link

Has the technique of "sprinkling" been used in studying random matrices?

In 1982, while studying the component sizes of random subgraphs of a hypercube, Ajtai, Komlós, and Szemerédi introduced a technique that came to be known as sprinkling. In this technique, the edges of the random graph are exposed in rounds. To explain it, suppose that each edge $e$ is independently assigned a random Uniform$[0,1]$ variable $U_e$. Eventually, all edges with $U_e \leq p$ will be included in the graph. In the first round, however, for some subset of the edges, we only check whether $U_e \leq p-\epsilon$. In the second round, for the remaining edges for which we know $U_e > p-\epsilon$, we check whether $U_e \leq p$. (The last few edges are the ones being "sprinkled" on at the end.) The idea is that this additional, last-minute randomization can be used to ensure (or at least make it very likely) that some desirable graph property holds. A similar technique has also been used by percolation theorists.

Has the technique of sprinkling been used in the study of random Bernoulli matrices? Can you give me references?