Dependent random choice
In mathematics, dependent random choice is a probabilistic technique that shows how to find a large set of vertices in a dense graph such that every small subset of vertices has many common neighbors. It is a useful tool to embed a graph into another graph with many edges. Thus it has its application in extremal graph theory, additive combinatorics and Ramsey theory.
Wikipedia contributors, "Dependent random choice", Wikipedia, revision 1385146496, retrieved 20 November 2026, source, CC BY-SA 4.0.