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.

Statement of theorem

edit

Let  ,   and suppose:[1][2][3][4][5]  Every graph on   vertices with at least   edges contains a subset   of vertices with   such that for all   with  ,   has at least   common neighbors.

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 For every  -element subset   of  ,   contains   if and only if   is contained in the common neighborhood of  , which occurs with probability   An   is bad if it has less than   common neighbors. Then for each fixed  -element subset   of  , it is contained in   with probability less than  . Therefore by linearity of expectation,  To eliminate bad subsets, we exclude one element in each bad subset. The number of remaining elements is at least  , whose expected value is at least   Consequently, there exists a   such that there are at least   elements in   remaining after getting rid of all bad  -element subsets. The set   of the remaining   elements expresses the desired properties.

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

 and so the assumption of dependent random choice holds. Hence, for each graph   with at least   edges, there exists a vertex subset   of size   satisfying that every  -subset of   has at least   common neighbors. By embedding   into   by embedding   into   arbitrarily and then embedding the vertices in   one by one, then for each vertex   in  , it has at most   neighbors in  , which shows that their images in   have at least   common neighbors. Thus   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.

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  ) and so the DRC assumption holds. Since a 1-subdivision of the complete graph on   vertices is a bipartite graph with parts of size   and   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.

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:   Then every graph   on   vertices with at least   edges contains two subsets   of vertices so that any   vertices in   have at least   common neighbors in  .[1]

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
  1. ^ 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.
  2. ^ 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.
  3. ^ 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.
  4. ^ 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.
  5. ^ 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.

Further reading

edit