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.
Statement of theorem[edit]
Let , and suppose:[1][2][3][4][5]
Proof[edit]
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 vertices first and then chooses common neighbors as the set of vertices. The hope is that in this way, the chosen set would be more likely to have more common neighbors.
Formally, let be a list of vertices chosen uniformly at random from with replacement (allowing repetition). Let be the common neighborhood of . The expected value of is
Applications[edit]
Turán numbers of a bipartite graph[edit]
Dependent random choice can help find the Turán number. Using appropriate parameters, if is a bipartite graph in which all vertices in have degree at most , then the extremal number where only depends on .[1][5]
Formally, with , let be a sufficiently large constant such that If then
This can be generalized to degenerate graphs using a variation of dependent random choice.
Embedding a 1-subdivision of a complete graph[edit]
DRC can be applied directly to show that if is a graph on vertices and edges, then contains a 1-subdivision of a complete graph with vertices. This can be shown in a similar way to the above proof of the bound on Turán number of a bipartite graph.[1]
Indeed, if we set , we have (since )
Variation[edit]
A stronger version finds two subsets of vertices in a dense graph so that every small subset of vertices in has a lot of common neighbors in .
Formally, let be some positive integers with , and let be some real number. Suppose that the following constraints hold:
Extremal number of a degenerate bipartite graph[edit]
Using this stronger statement, one can upper bound the extremal number of -degenerate bipartite graphs: for each -degenerate bipartite graph with at most vertices, the extremal number is at most [1]
Ramsey number of a degenerate bipartite graph[edit]
This statement can be also applied to obtain an upper bound of the Ramsey number of a degenerate bipartite graphs. If is a fixed integer, then for every bipartite -degenerate bipartite graph on vertices, the Ramsey number is of the order [1]
References[edit]
- ^ a b c d e f Fox, Jacob; Sudakov, Benny (2011). "Dependent random choice". Random Structures & Algorithms. 38 (1–2): 68–99. doi:10.1002/rsa.20344. hdl:1721.1/70097. ISSN 1098-2418. S2CID 2321395.
- ^ Verstraëte, Jacques (2015). "6 - Dependent Random Choice" (PDF). University of California San Diego. S2CID 47638896. Archived from the original (PDF) on 2017-05-19.
- ^ Kostochka, A. V.; Rödl, V. (2001). "On graphs with small Ramsey numbers*". Journal of Graph Theory. 37 (4): 198–204. CiteSeerX 10.1.1.225.1347. doi:10.1002/jgt.1014. ISSN 1097-0118. S2CID 12292577.
- ^ Sudakov, Benny (2003-05-01). "A few remarks on Ramsey–Turán-type problems". Journal of Combinatorial Theory. Series B. 88 (1): 99–106. doi:10.1016/S0095-8956(02)00038-2. ISSN 0095-8956.
- ^ a b Alon, Noga; Krivelevich, Michael; Sudakov, Benny (November 2003). "Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions". Combinatorics, Probability and Computing. 12 (5+6): 477–494. doi:10.1017/S0963548303005741. ISSN 1469-2163.