In mathematics, dependent random choice is a
.
Statement of theorem
Let
,
and suppose:[1][2][3][4][5]
![{\displaystyle n\alpha ^{t}-{n \choose r}\left({\frac {m}{n}}\right)^{t}\geq u.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/085c2d3cf8ddef341c92b7dc3945b962e653d0db)
Every graph on
![{\displaystyle n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
vertices with at least
![{\displaystyle {\frac {\alpha n^{2}}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/85a8266170c86a50f0a7db170570626239318756)
edges contains a subset
![{\displaystyle U}](https://wikimedia.org/api/rest_v1/media/math/render/svg/458a728f53b9a0274f059cd695e067c430956025)
of vertices with
![{\displaystyle |U|\geq u}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83c3d5e55aed8cfd958ef675402bbef50181ca29)
such that for all
![{\displaystyle S\subset U}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ef7205f3d0a88150c5472cac687bb2285e36aad)
with
![{\displaystyle |S|=r}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12d991762c14fda814aedc24c96e516718264388)
,
![{\displaystyle S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2)
has at least
![{\displaystyle m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
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 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
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b599212ae0b77e13068e45081f0413bd84debcd)
For every
![{\displaystyle r}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1ecb613aa2984f0576f70f86650b7c2a132538)
-element subset
![{\displaystyle S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2)
of
![{\displaystyle V}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af0f6064540e84211d0ffe4dac72098adfa52845)
,
![{\displaystyle A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
contains
![{\displaystyle S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2)
if and only if
![{\displaystyle T}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0)
is contained in the common neighborhood of
![{\displaystyle S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2)
, which occurs with probability
![{\textstyle \left({\frac {\#{\text{common neighbors of }}S}{n}}\right)^{t}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d9e836b5807f2ca7c565b0bc481e3101d836ba5)
An
![{\displaystyle S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2)
is
bad if it has less than
![{\displaystyle m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
common neighbors. Then for each fixed
![{\displaystyle r}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1ecb613aa2984f0576f70f86650b7c2a132538)
-element subset
![{\displaystyle S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2)
of
![{\displaystyle V}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af0f6064540e84211d0ffe4dac72098adfa52845)
, it is contained in
![{\displaystyle A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
with probability less than
![{\displaystyle (m/n)^{t}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6535baa366a7ced466a86c17ffb4999d49c84846)
. 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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0df249471266884e100ecc57a3282955b1bd798)
To eliminate bad subsets, we exclude one element in each bad subset. The number of remaining elements is at least
![{\displaystyle |A|-(\#{\text{bad }}r{\text{-element subset of }}A)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12b35aa93c3ed88f96a361878bd679117f8b0389)
, whose expected value is at least
![{\textstyle n\alpha ^{t}-{\binom {n}{r}}\left({\frac {m}{n}}\right)^{t}\geq u.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/374bd040041ab7710126c39c9378e32d143f6000)
Consequently, there exists a
![{\displaystyle T}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0)
such that there are at least
![{\displaystyle u}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8)
elements in
![{\displaystyle A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
remaining after getting rid of all bad
![{\displaystyle r}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1ecb613aa2984f0576f70f86650b7c2a132538)
-element subsets. The set
![{\displaystyle U}](https://wikimedia.org/api/rest_v1/media/math/render/svg/458a728f53b9a0274f059cd695e067c430956025)
of the remaining
![{\displaystyle u}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8)
elements expresses the desired properties.
Applications
Turán numbers of a bipartite graph
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
![{\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,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4cc71fc6f8ec242f096a120a1b68b446a00c3ce)
and so the assumption of dependent random choice holds. Hence, for each graph
![{\displaystyle G}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
with at least
![{\displaystyle cn^{2-1/r}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a0f5315c4b4ac46f800b4afba254d85196a1747)
edges, there exists a vertex subset
![{\displaystyle U}](https://wikimedia.org/api/rest_v1/media/math/render/svg/458a728f53b9a0274f059cd695e067c430956025)
of size
![{\displaystyle a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc)
satisfying that every
![{\displaystyle r}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1ecb613aa2984f0576f70f86650b7c2a132538)
-subset of
![{\displaystyle U}](https://wikimedia.org/api/rest_v1/media/math/render/svg/458a728f53b9a0274f059cd695e067c430956025)
has at least
![{\displaystyle a+b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a2391acf09244b9dba74eb940e871a6be7e7973a)
common neighbors. By embedding
![{\displaystyle H}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75a9edddcca2f782014371f75dca39d7e13a9c1b)
into
![{\displaystyle G}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
by embedding
![{\displaystyle A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
into
![{\displaystyle U}](https://wikimedia.org/api/rest_v1/media/math/render/svg/458a728f53b9a0274f059cd695e067c430956025)
arbitrarily and then embedding the vertices in
![{\displaystyle B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a)
one by one, then for each vertex
![{\displaystyle v}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597)
in
![{\displaystyle B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a)
, it has at most
![{\displaystyle r}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1ecb613aa2984f0576f70f86650b7c2a132538)
neighbors in
![{\displaystyle A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
, which shows that their images in
![{\displaystyle U}](https://wikimedia.org/api/rest_v1/media/math/render/svg/458a728f53b9a0274f059cd695e067c430956025)
have at least
![{\displaystyle a+b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a2391acf09244b9dba74eb940e871a6be7e7973a)
common neighbors. Thus
![{\displaystyle v}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597)
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
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
)
![{\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,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d403ab14a6e6ed550a2ec16a15542ca2e27db804)
and so the DRC assumption holds. Since a 1-subdivision of the complete graph on
![{\displaystyle a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc)
vertices is a bipartite graph with parts of size
![{\displaystyle a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc)
and
![{\displaystyle b={\binom {a}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87c89d4ca8a55212c7bb7552adf0b4e5e43716fc)
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
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:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/605c1b4eeac3fcda8087a9c51f79cefc2763a6dc)
Then every graph
![{\displaystyle G}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
on
![{\displaystyle n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
vertices with at least
![{\displaystyle \alpha n^{2}/2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4349e023ae4d762a8f768530c9c7c99d41fd100d)
edges contains two subsets
![{\displaystyle U_{1},U_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5210b403dbd09578d718edb5419273b400387a70)
of vertices so that any
![{\displaystyle r}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1ecb613aa2984f0576f70f86650b7c2a132538)
vertices in
![{\displaystyle U_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b21a6f475b0e68475c6019abe1fed0b415e0e42)
have at least
![{\displaystyle m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
common neighbors in
![{\displaystyle U_{3-i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c8b7f057c384cceed28fef38e62cbd4c760ccd60)
.
[1]
Extremal number of a degenerate bipartite graph
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
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
- ^ .
- (PDF) on 2017-05-19.
- .
- .
- ^ .
Further reading