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.
Thus it has its application in extremal graph theory, additive combinatorics and Ramsey theory.
edges contains a subset
The basic idea is to choose the set of vertices randomly.
However, instead of choosing each vertex uniformly at random, the procedure randomly chooses a list of
The hope is that in this way, the chosen set would be more likely to have more common neighbors.
vertices chosen uniformly at random from
with replacement (allowing repetition).
To eliminate bad subsets, we exclude one element in each bad subset.
The number of remaining elements is at least
remaining after getting rid of all bad
elements expresses the desired properties.
Dependent random choice can help find the Turán number.
be a sufficiently large constant such that
and so the assumption of dependent random choice holds.
edges, there exists a vertex subset
arbitrarily and then embedding the vertices in
can be embedded into one of the common neighbors while avoiding collisions.
This can be generalized to degenerate graphs using a variation of dependent random choice.
DRC can be applied directly to show that if
This can be shown in a similar way to the above proof of the bound on Turán number of a bipartite graph.
vertices is a bipartite graph with parts of size
where every vertex in the second part has degree two, the embedding argument in the proof of the bound on Turán number of a bipartite graph produces the desired result.
A stronger version finds two subsets of vertices
so that every small subset of vertices in
edges contains two subsets
[1] Using this stronger statement, one can upper bound the extremal number of
vertices, the extremal number
[1] This statement can be also applied to obtain an upper bound of the Ramsey number of a degenerate bipartite graphs.
vertices, the Ramsey number