Dependent random choice

In mathematics, dependent random choice is a simple yet powerful probabilistic technique which shows how to find a large set of vertices in a dense graph such that every small subset of vertices has a lot of common neighbors. It is a useful tool to embed a graph into another graph with many edges, and thus has its application in extremal graph theory and Ramsey theory.

Statement of theorem

[1][2][3][4][5]Let ${\displaystyle u,n,r,m,t\in \mathbb {N} }$, ${\displaystyle \alpha >0}$ and suppose

$${\displaystyle n\alpha ^{t}-{n \choose r}\left({\frac {m}{n}}\right)^{t}\geq u.}$$

Then every graph on ${\displaystyle n}$ vertices with at least ${\displaystyle {\frac {\alpha n^{2}}{2}}}$ edges contains a subset ${\displaystyle U}$ of vertices with ${\displaystyle |U|\geq u}$ such that for all ${\displaystyle S\subset U}$ with ${\displaystyle |S|=r}$, ${\displaystyle S}$ has at least ${\displaystyle m}$ common neighbors.

Proof

The basic idea is to choose the set of vertices randomly. However, instead of choosing each vertex uniformly at random, the procedure chooses a list of ${\displaystyle t}$ vertices first and then chooses its 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 ${\displaystyle T}$ be a list of ${\displaystyle t}$ vertices chosen uniformly at random from ${\displaystyle V(G)}$ with replacement (allowing repetition). Let ${\displaystyle A}$ be the common neighborhood of ${\displaystyle T}$. The expected value of ${\displaystyle |A|}$ is

$${\displaystyle {\begin{aligned}\mathbb {E} |A|&=\sum _{v\in V}\mathbb {P} (v\in A)=\sum _{v\in V}\mathbb {P} (T\subseteq N(v))=\sum _{v\in V}\left({\frac {d(v)}{n}}\right)^{t}\\&\geq n\left({\frac {1}{n}}\sum _{v\in V}{\frac {d(v)}{n}}\right)^{t}\quad {\text{(convexity)}}\\&\geq n\alpha ^{t}.\end{aligned}}}$$

For every ${\displaystyle r}$-element subset ${\displaystyle S}$ of ${\displaystyle V}$, the event of ${\displaystyle A}$ containing ${\displaystyle S}$ occurs if and only if ${\displaystyle T}$ is contained in the common neighborhood of ${\displaystyle S}$, which occurs with probability ${\textstyle \left({\frac {\#{\text{common neighbors of }}S}{n}}\right)^{t}.}$ Call an ${\displaystyle S}$ bad if it has less than ${\displaystyle m}$ common neighbors. Then for each fixed ${\displaystyle r}$-element subset ${\displaystyle S}$ of ${\displaystyle V}$, it is contained in ${\displaystyle A}$ with probability less than ${\displaystyle (m/n)^{t}}$. Therefore by linearity of expectation,

$${\displaystyle \mathbb {E} [\#{\text{bad }}r{\text{-element subset of }}A]<{\binom {n}{r}}\left({\frac {m}{n}}\right)^{t}.}$$

To make sure that there are no bad subsets, we can get rid of one element in each bad subset. The number of remaining elements is at least ${\displaystyle |A|-(\#{\text{bad }}r{\text{-element subset of }}A)}$, whose expected value is at least ${\textstyle n\alpha ^{t}-{\binom {n}{r}}\left({\frac {m}{n}}\right)^{t}\geq u.}$ Consequently, there exists a ${\displaystyle T}$ such that there are at least ${\displaystyle u}$ elements in ${\displaystyle A}$ remaining after getting rid of all bad ${\displaystyle r}$-element subsets. The set ${\displaystyle U}$ of the remaining ${\displaystyle u}$ elements satisfies the desired properties.

Applications

Turán numbers of a bipartite graph

Directly using dependent random choice by setting appropriate parameters, we can show that if ${\displaystyle H=A\cup B}$ is a bipartite graph in which all vertices in ${\displaystyle B}$ have degree at most ${\displaystyle r}$, then the extremal number ${\displaystyle {\text{ex}}(n,H)\leq cn^{2-1/r}}$ where ${\displaystyle c=c(H)}$ only depends on ${\displaystyle H}$.[1][5]

Formally, if ${\displaystyle a=|A|,b=|B|}$ and ${\displaystyle c}$ is a sufficiently large constant such that ${\displaystyle (2c)^{r}-(a+b)^{r}\geq a.}$ Then by setting ${\displaystyle \alpha =2cn^{-1/r},m=a+b,t=r,u=a}$ we know that

$${\displaystyle n\alpha ^{t}-{\binom {n}{r}}\left({\frac {m}{n}}\right)^{t}=(2c)^{r}-{\binom {n}{r}}\left({\frac {a+b}{n}}\right)^{r}\geq (2c)^{r}-(a+b)^{r}\geq a=u,}$$

and so the assumption of dependent random choice holds. Hence, for each graph ${\displaystyle G}$ with at least ${\displaystyle cn^{2-1/r}}$ edges, there exists a vertex subset ${\displaystyle U}$ of size ${\displaystyle a}$ satisfying that every ${\displaystyle r}$-subset of ${\displaystyle U}$ has at least ${\displaystyle a+b}$ common neighbors. This allows us to embed ${\displaystyle H}$ into ${\displaystyle G}$ in the following way. Embed ${\displaystyle A}$ into ${\displaystyle U}$ arbitrarily, and then embed the vertices in ${\displaystyle B}$ one by one. For each vertex ${\displaystyle v}$ in ${\displaystyle B}$, it has at most ${\displaystyle r}$ neighbors in ${\displaystyle A}$, which shows that their images in ${\displaystyle U}$ have at least ${\displaystyle a+b}$ common neighbors. This allows us to embed ${\displaystyle v}$ to one of the common neighbors while avoiding collisions.

In fact, this can be generalized to degenerate graphs using the variation of dependent random choice described below.

Embedding a 1-subdivision of a complete graph

Dependent random choice can be applied directly to show that if ${\displaystyle G}$ is a graph on ${\displaystyle n}$ vertices and ${\displaystyle \epsilon n^{2}}$ edges, then ${\displaystyle G}$ contains a 1-subdivision of a complete graph with ${\displaystyle \epsilon ^{3/2}n^{1/2}}$ 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 ${\displaystyle \alpha =2\epsilon ,m=a^{2},t={\frac {\log n}{2\log 1/\epsilon }},u=a}$, we have (since ${\displaystyle 2\epsilon =\alpha \leq 1}$)

$${\displaystyle n\alpha ^{t}-{\binom {n}{r}}\left({\frac {m}{n}}\right)^{t}\geq (2\epsilon )^{t}n-{\binom {n}{2}}\epsilon ^{3t}\geq n^{1/2}\geq a=u,}$$

and so the assumption of dependent random choice holds. Since a 1-subdivision of the complete graph on ${\displaystyle a}$ vertices is a bipartite graph with parts of size ${\displaystyle a}$ and ${\displaystyle b={\binom {a}{2}}}$ where every vertex in the second part has degree two, we can run the embedding argument in the above proof of the bound on Turán number of a bipartite graph to get the desired result.

Variation

There is a stronger version of dependent random choice that finds two subsets of vertices ${\displaystyle U_{1},U_{2}}$ in a dense graph ${\displaystyle G}$ so that every small subset of vertices in ${\displaystyle U_{i}}$ has a lot of common neighbors in ${\displaystyle U_{3-i}}$.

Formally, let ${\displaystyle u,n,r,m,t,q}$ be some positive integers with ${\displaystyle q>r}$, and let ${\displaystyle \alpha >0}$ be some real number. Suppose that the following constraints hold:

$${\displaystyle {\begin{aligned}n\alpha ^{t}-{\binom {n}{q}}\left({\frac {m}{n}}\right)^{t}&\geq u\\{\binom {n}{r}}\left({\frac {m}{u}}\right)^{q-r}&<1.\end{aligned}}}$$

Then every graph ${\displaystyle G}$ on ${\displaystyle n}$ vertices with at least ${\displaystyle \alpha n^{2}/2}$ edges contains two subsets ${\displaystyle U_{1},U_{2}}$ of vertices so that any ${\displaystyle r}$ vertices in ${\displaystyle U_{i}}$ have at least ${\displaystyle m}$ common neighbors in ${\displaystyle U_{3-i}}$.[1]

Extremal number of a degenerate bipartite graph

Using this stronger statement, one can upper bound the extremal number of ${\displaystyle r}$-degenerate bipartite graph: for each ${\displaystyle r}$-degenerate bipartite graph ${\displaystyle H}$ with at most ${\displaystyle N^{1-1.8/s}}$ vertices, the extremal number ${\displaystyle {\text{ex}}(N,H)}$ ist at most ${\displaystyle N^{2-1/(s^{3}r)}.}$[1]

Ramsey number of a degenerate bipartite graph

This statement can be also applied to obtain an upper bound of the Ramsey number of a degenerate bipartite graphs. If ${\displaystyle r}$ is a fixed integer, then for every bipartite ${\displaystyle r}$-degenerate bipartite graph ${\displaystyle G}$ on ${\displaystyle n}$ vertices, the Ramsey number ${\displaystyle r(G)}$ is of the order ${\displaystyle n^{1+o(1)}.}$[1]

References

1. 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.
2. Verstraëte, Jacques (2015). "6 - Dependent Random Choice" (PDF).
3. Kostochka, A. V.; Rödl, V. (2001). "On graphs with small Ramsey numbers*". Journal of Graph Theory. 37 (4): 198–204. doi:10.1002/jgt.1014. ISSN 1097-0118.
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. 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

• Dependent Random Choice - MIT Math