Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.