Dependent random choice

Last updated April 10, 2024

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

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

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

Every graph on $n$ vertices with at least ${\frac {\alpha n^{2}}{2}}$ edges contains a subset $U$ of vertices with $|U|\geq u$ such that for all $S\subset U$ with $|S|=r$ , $S$ has at least $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 randomly chooses a list of $t$ 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 $T$ be a list of $t$ vertices chosen uniformly at random from $V(G)$ with replacement (allowing repetition). Let $A$ be the common neighborhood of $T$ . The expected value of $|A|$ is

{\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 $r$ -element subset $S$ of $V$ , $A$ contains $S$ if and only if $T$ is contained in the common neighborhood of $S$ , which occurs with probability ${\textstyle \left({\frac {\#{\text{common neighbors of }}S}{n}}\right)^{t}.}$ An $S$ is bad if it has less than $m$ common neighbors. Then for each fixed $r$ -element subset $S$ of $V$ , it is contained in $A$ with probability less than $(m/n)^{t}$ . Therefore by linearity of expectation,

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

To eliminate bad subsets, we exclude one element in each bad subset. The number of remaining elements is at least $|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 $T$ such that there are at least $u$ elements in $A$ remaining after getting rid of all bad $r$ -element subsets. The set $U$ of the remaining $u$ 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 $H=A\cup B$ is a bipartite graph in which all vertices in $B$ have degree at most $r$ , then the extremal number ${\text{ex}}(n,H)\leq cn^{2-1/r}$ where $c=c(H)$ only depends on $H$ .^[1]^[5]

Formally, with $a=|A|,b=|B|$ , let $c$ be a sufficiently large constant such that $(2c)^{r}-(a+b)^{r}\geq a.$ If $\alpha =2cn^{-1/r},m=a+b,t=r,u=a$ then

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 $G$ with at least $cn^{2-1/r}$ edges, there exists a vertex subset $U$ of size $a$ satisfying that every $r$ -subset of $U$ has at least $a+b$ common neighbors. By embedding $H$ into $G$ by embedding $A$ into $U$ arbitrarily and then embedding the vertices in $B$ one by one, then for each vertex $v$ in $B$ , it has at most $r$ neighbors in $A$ , which shows that their images in $U$ have at least $a+b$ common neighbors. Thus $v$ 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 $G$ is a graph on $n$ vertices and $\epsilon n^{2}$ edges, then $G$ contains a 1-subdivision of a complete graph with $\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 $\alpha =2\epsilon ,m=a^{2},t={\frac {\log n}{2\log 1/\epsilon }},u=a$ , we have (since $2\epsilon =\alpha \leq 1$ )

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 DRC assumption holds. Since a 1-subdivision of the complete graph on $a$ vertices is a bipartite graph with parts of size $a$ and $b={\binom {a}{2}}$ 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 $U_{1},U_{2}$ in a dense graph $G$ so that every small subset of vertices in $U_{i}$ has a lot of common neighbors in $U_{3-i}$ .

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

{\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 $G$ on $n$ vertices with at least $\alpha n^{2}/2$ edges contains two subsets $U_{1},U_{2}$ of vertices so that any $r$ vertices in $U_{i}$ have at least $m$ common neighbors in $U_{3-i}$ .^[1]

Extremal number of a degenerate bipartite graph

Using this stronger statement, one can upper bound the extremal number of $r$ -degenerate bipartite graphs: for each $r$ -degenerate bipartite graph $H$ with at most $N^{1-1.8/s}$ vertices, the extremal number ${\text{ex}}(N,H)$ is at most $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 $r$ is a fixed integer, then for every bipartite $r$ -degenerate bipartite graph $G$ on $n$ vertices, the Ramsey number $r(G)$ is of the order $n^{1+o(1)}.$ ^[1]

Related Research Articles

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each internal vertex are equal to each other. A regular graph with vertices of degree $k$ is called a $k$ ‑regular graph or regular graph of degree $k$ . Also, from the handshaking lemma, a regular graph contains an even number of vertices with odd degree.

In mathematics, Hall's marriage theorem, proved by Philip Hall, is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist:

In extremal graph theory, Szemerédi’s regularity lemma states that a graph can be partitioned into a bounded number of parts so that the edges between parts are regular. The lemma shows that properties of random graphs can be applied to general graphs like counting the copies of a given subgraph within graphs. Endre Szemerédi proved the lemma over bipartite graphs for his theorem on arithmetic progressions in 1975 and for general graphs in 1978. Variants of the lemma use different notions of regularity and apply to other mathematical objects like hypergraphs.

In graph theory, the Kneser graph $K (n, k)$ (alternatively $KG n, k$ ) is the graph whose vertices correspond to the $k$ -element subsets of a set of $n$ elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1956.

The Zarankiewicz problem, an unsolved problem in mathematics, asks for the largest possible number of edges in a bipartite graph that has a given number of vertices and has no complete bipartite subgraphs of a given size. It belongs to the field of extremal graph theory, a branch of combinatorics, and is named after the Polish mathematician Kazimierz Zarankiewicz, who proposed several special cases of the problem in 1951.

In graph theory, a graph is said to be a pseudorandom graph if it obeys certain properties that random graphs obey with high probability. There is no concrete definition of graph pseudorandomness, but there are many reasonable characterizations of pseudorandomness one can consider.

The expander mixing lemma intuitively states that the edges of certain $-regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets and is always close to the expected number of edges between them in a random -regular graph, namely .$

Triadic closure is a concept in social network theory, first suggested by German sociologist Georg Simmel in his 1908 book Soziologie [Sociology: Investigations on the Forms of Sociation]. Triadic closure is the property among three nodes A, B, and C, that if the connections A-B and A-C exist, there is a tendency for the new connection B-C to be formed. Triadic closure can be used to understand and predict the growth of networks, although it is only one of many mechanisms by which new connections are formed in complex networks.

In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph $, find the maximal number of edges an -vertex graph can have such that it does not have a subgraph isomorphic to . In this context, is called a forbidden subgraph .$

In coding theory, Zemor's algorithm, designed and developed by Gilles Zemor, is a recursive low-complexity approach to code construction. It is an improvement over the algorithm of Sipser and Spielman.

In graph theory, the graph removal lemma states that when a graph contains few copies of a given subgraph, then all of the copies can be eliminated by removing a small number of edges. The special case in which the subgraph is a triangle is known as the triangle removal lemma.

The counting lemmas this article discusses are statements in combinatorics and graph theory. The first one extracts information from $-regular pairs of subsets of vertices in a graph, in order to guarantee patterns in the entire graph; more explicitly, these patterns correspond to the count of copies of a certain graph in . The second counting lemma provides a similar yet more general notion on the space of graphons, in which a scalar of the cut distance between two graphs is correlated to the homomorphism density between them and .$

Sidorenko's conjecture is a conjecture in the field of graph theory, posed by Alexander Sidorenko in 1986. Roughly speaking, the conjecture states that for any bipartite graph $and graph on vertices with average degree , there are at least labeled copies of in , up to a small error term. Formally, it provides an intuitive inequality about graph homomorphism densities in graphons. The conjectured inequality can be interpreted as a statement that the density of copies of in a graph is asymptotically minimized by a random graph, as one would expect a fraction of possible subgraphs to be a copy of if each edge exists with probability .$

In spectral graph theory, the Alon–Boppana bound provides a lower bound on the second-largest eigenvalue of the adjacency matrix of a $-regular graph, meaning a graph in which every vertex has degree . The reason for the interest in the second-largest eigenvalue is that the largest eigenvalue is guaranteed to be due to -regularity, with the all-ones vector being the associated eigenvector. The graphs that come close to meeting this bound are Ramanujan graphs, which are examples of the best possible expander graphs.$

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.

In graph theory, perfect matching in high-degree hypergraphs is a research avenue trying to find sufficient conditions for existence of a perfect matching in a hypergraph, based only on the degree of vertices or subsets of them.

In mathematics, a quasirandom group is a group that does not contain a large product-free subset. Such groups are precisely those without a small non-trivial irreducible representation. The namesake of these groups stems from their connection to graph theory: bipartite Cayley graphs over any subset of a quasirandom group are always bipartite quasirandom graphs.

The blow-up lemma, proved by János Komlós, Gábor N. Sárközy, and Endre Szemerédi in 1997, is an important result in extremal graph theory, particularly within the context of the regularity method. It states that the regular pairs in the statement of Szemerédi's regularity lemma behave like complete bipartite graphs in the context of embedding spanning graphs of bounded degree.

The method of (hypergraph) containers is a powerful tool that can help characterize the typical structure and/or answer extremal questions about families of discrete objects with a prescribed set of local constraints. Such questions arise naturally in extremal graph theory, additive combinatorics, discrete geometry, coding theory, and Ramsey theory; they include some of the most classical problems in the associated fields.

References

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