PaperlayerView exact revision on arXiv

Source-linked AI summary

Dependent Random Choice

Jacob Fox, Benny Sudakov

arXiv:0909.3271v2math.COmath.PR

TL;DR

Embedding small or sparse graphs in dense graphs motivates finding large subsets whose small subsets have many common neighbors. The survey presents dependent random choice and reviews its applications, including an improved tournament bound.

  • Problem

    Embedding a small or sparse graph in a dense graph can be approached by finding a large subset whose small subsets have many common neighbors.

    Source: §1 · p. 1

  • Method

    Dependent random choice samples vertices and uses their common neighborhood as a candidate rich subset.

    Source: §1 · p. 1

  • Results

    For tournaments, n(k, ε) < (16/ε)^(2k+1), a bound tight up to a constant factor in the exponent.

    Source: §10 · p. 24

  • Takeaways & Limitations

    A rich subset can be used to greedily embed the desired subgraph one vertex at a time.

    Source: §1 · p. 1

    The basic lemma assumes integer t, and the survey says extending its current proof techniques to non-integer t is unclear.

    Source: §10 · p. 27

Abstract

from arXiv · show

We describe a simple and yet surprisingly powerful probabilistic technique which shows how to find in a dense graph a large subset of vertices in which all (or almost all) small subsets have many common neighbors. Recently this technique has had several striking applications to Extremal Graph Theory, Ramsey Theory, Additive Combinatorics, and Combinatorial Geometry. In this survey we discuss some of them.

1 Introduction

Embedding small or sparse graphs in dense graphs can be eased by finding a large vertex subset whose small subsets have many common neighbors. The survey presents dependent random choice and systematically reviews its variants and applications.

1 Introduction

  • Dependent random choice selects a random vertex set T and takes its common neighborhood as the candidate rich set U.A subset with few common neighbors is unlikely to contain every vertex of T, so U is not expected to contain such a subset.Source: §1 · p. 1
  • The survey describes known variants and main ideas, rather than usually presenting the arguments for the sharpest bounds.The authors note that their topic selection is biased and not comprehensive.Source: §1 · pp. 1–2
  • Dependent random choice has applications in Extremal Graph Theory, Ramsey Theory, Additive Combinatorics, and Combinatorial Geometry.The survey aims to explain ideas with wide applicability across combinatorial problems.Source: §1 · p. 1

2 Basic Lemma

The basic lemma formalizes how a dense graph can contain a large subset whose small subsets have many common neighbors.

2 Basic Lemma

  • The common neighborhood N(U) consists of vertices adjacent to every vertex in U.N(v) denotes the neighbors of a single vertex v.Source: §2 · p. 2
  • The lemma is presented as a typical dependent-random-choice result for finding rich subsets in dense graphs.The survey points to its applications in the following section.Source: §2 · p. 2
  • If the lemma’s condition on the parameters holds, the graph contains at least a vertices such that every r vertices have at least m common neighbors.The proof samples t vertices with replacement, takes their common neighborhood, and removes a vertex from each r-subset with fewer than m common neighbors.Source: §2 · pp. 2–3

3 A Few Quick Applications

Four applications illustrate how the basic lemma supports results on bipartite Turán numbers, graph subdivisions, cube Ramsey numbers, and Ramsey–Turán problems.

3.1 Tur´an numbers of bipartite graphs

  • ex(n, H) ≤ cn^(2−1/r) when H is bipartite and every vertex in one part has degree at most r.The proof finds a subset with many common neighbors and embeds H one vertex at a time.Source: §3.1 · pp. 3–4

3.2 Embedding a 1-subdivision of a complete graph

  • A graph with n vertices and εn² edges contains a 1-subdivision of a complete graph on ε^(3/2)n^(1/2) vertices.The survey notes that more complicated arguments improve this result and extend it to subdivisions of graphs with O(n) edges.Source: §3.2 · p. 4

3.3 Ramsey number of the cube

  • The cube satisfies r(Q_r) ≤ 2^(3r), and every graph of density 1/2 contains Q_r.The proof embeds the r-regular bipartite cube in the denser color of a two-coloring.Source: §3.3 · p. 5

3.4 Ramsey-Tur´an problem for K4-free graphs

  • For K4-free graphs with independence number o(n), the maximum edge count is (1 + o(1))n²/8, and this bound is tight.For the stated f(n), the survey also proves RT(n, K4, f(n)) = o(n²), using a pair with many common neighbors to derive a contradiction.Source: §3.4 · pp. 5–6

4 A dense graph without a rich subset of linear size

A dense graph need not contain a linear-size subset in which every pair has linearly many common neighbors. The section gives a dense counterexample, including in its complement, before noting a weaker almost-all-pairs guarantee.

4 A dense graph without a rich subset of linear size

  • For infinitely many n, a graph with at least n(n −2)/4 edges has a pair with o(n) common neighbors in every linear-size subset.The construction uses binary strings as vertices, joining pairs whose Hamming distance is at most m/2.Source: §4 · p. 6
  • The same construction also shows that the complement has no linear-size subset in which every pair has linearly many common neighbors.The proof uses pairs of vertices at nearly maximal Hamming distance to bound their common neighborhoods.Source: §4 · p. 7
  • A variant of dependent random choice still gives a linear-size subset in which almost every pair has a linear number of common neighbors.The section points to this weaker guarantee as useful for the Balog-Szemerédi-Gowers theorem.Source: §4 · p. 7

5 A variant of the basic lemma and additive combinatorics

The section weakens the all-pairs rich-set guarantee to an almost-all-pairs version and shows how length-three paths yield a quantitative Balog-Szemerédi-Gowers theorem. It then applies related ideas to cycle-connected subgraphs.

5 A variant of the basic lemma and additive combinatorics

  • A bipartite graph of density c contains U of size at least c|A|/2 where at least a (1 − ε)-fraction of ordered pairs have at least εc²|B|/2 common neighbors.The proof selects a vertex whose neighborhood is large and has few bad pairs.Source: §5 · p. 8

5.1 Balog-Szemerédi-Gowers theorem

  • The Balog-Szemerédi-Gowers conclusion gives A′ and B′ of linear size with |A′ + B′| ≤ C′n, where the constants depend on c and C, not n.Gowers’ approach improves the original tower-like parameter dependence to a constant-degree polynomial in 1/c and C.Source: §5.1 · p. 9
  • Dense bipartite graphs contain linear-size parts with at least 2^-12c^5n^2 length-three paths between every cross-pair.This graph lemma supplies the path structure used to obtain linear-size subsets with a small sumset from a dense partial sumset.Source: §5.1 · p. 9

5.2 An application to an extremal problem

  • For 0 < β < 1/5, every graph with n vertices and at least n^(2−β) edges contains a strongly C8-connected subgraph.Its edge bound is best possible apart from a constant factor; the cited C6-connected guarantee has only cn^(2−3β) edges.Source: §5.2 · p. 10
  • A strengthened bipartite graph lemma places the length-three paths between selected vertices entirely inside the induced subgraph on A′ ∪ B′.The induced subgraph has at least 2^-6c²n² edges and at least 2^-24c^7n² such paths for every cross-pair.Source: §5.2 · p. 10

6 Ramsey numbers of bounded degree graphs

Dependent random choice finds vertex sets with rich common neighborhoods, and an embedding argument uses them to place bounded-degree bipartite graphs in dense graphs. The section also gives Ramsey bounds for such graphs and linear Ramsey bounds for bounded-degree uniform hypergraphs.

6 Ramsey numbers of bounded degree graphs

  • For bipartite H with n vertices and maximum degree ∆, the section gives r(H) ≤ ∆2^(∆+3)n; in particular, r(Q_d) ≤ d2^(2d+3).The upper bound is tight up to a constant factor in the exponent and is also the best known upper bound for the d-cube.Source: §6 · p. 11

6.1 Dependent random choice lemma

  • If a dense graph has more than 4dε^-d n vertices, it contains U with |U| > 2n where fewer than (2d)^-d of its d-sets have fewer than n common neighbors.This extends the rich-subset lemma from pairs to d-sets.Source: §6.1 · p. 12

6.2 Embedding lemma and the proof of Theorem 6.1

  • A set U larger than 2n with few bad d-sets suffices to embed every n-vertex bipartite graph of maximum degree d.The embedding proceeds one side at a time, maintaining good neighborhoods so each next vertex has an available common neighbor.Source: §6.2 · pp. 12–13

6.3 Ramsey numbers of sparse hypergraphs

  • Every k-uniform hypergraph with n vertices and maximum degree ∆ has Ramsey number at most c(∆, k)n.For k ≥ 4, the section reports c(∆, k) ≤ t_k(c∆), improving on the Ackermann-type upper bound from regularity methods.Source: §6.3 · p. 14

7 Degenerate graphs

The section adapts dependent random choice to embeddings of degenerate graphs, then applies the method to Ramsey and Turán problems. Its explicit Ramsey bound is nearly linear for bipartite degenerate graphs.

7.1 Embedding a degenerate bipartite graph in a dense graph

  • Every r-degenerate bipartite graph with at most N^(1−1.8/s) vertices embeds in a graph on N vertices with at least N^(2−1/(s^3r)) edges, for r,s ≥ 2.The method finds two sets in which every r-tuple has many common neighbors in the other set.Source: §7.1 · p. 15

7.2 Applications

Ramsey numbers of degenerate graphs

  • For sufficiently large n, every r-degenerate bipartite graph H on n vertices has Ramsey number at most 28r^(1/3)(log n)^(2/3)n.The bound follows by applying the dense-graph embedding corollary to the majority color in a two-coloring.Source: Ramsey numbers of degenerate graphs · p. 16

Turán numbers of degenerate bipartite graphs

Ramsey numbers of graphs with few edges

  • The section presents a short proof of the Ramsey-number result for bipartite graphs with m edges and no isolated vertices.That result had already been verified for bipartite graphs; the paper’s proof is the contribution described here.Source: Ramsey numbers of graphs with few edges · p. 17

8 Embedding 1-subdivided graphs

The survey develops dependent-random-choice extensions for embedding 1-subdivisions in dense graphs. It improves the clique-subdivision bound and extends the result to subdivisions of general sparse graphs.

8.1 A tight bound for 1-subdivisions of complete graphs

  • The dependence improves from δ = ε^3/2 to δ = ε, and a random-graph argument shows the power of ε cannot be further improved.The survey attributes the improved bound to Alon, Krivelevich, and Sudakov.Source: §8 · p. 17
  • A graph with n vertices and εn² edges contains a 1-subdivision of a clique on εn^1/2 vertices.This is the tight-bound result for complete-graph subdivisions.Source: §8.1 · p. 18

8.2 1-subdivision of a general graph

  • If Γ has at most n edges and vertices, every graph with N ≥ 128ε^-3n vertices and εN² edges contains the 1-subdivision of Γ.The proof uses the bipartite form of a 1-subdivision, whose subdividing vertices have degree two.Source: §8.2 · p. 19
  • Repeated dependent-random-choice steps produce nested sets where the fraction of pairs with small common neighborhoods decreases, supporting the general-graph embedding.The intermediate result embeds bipartite graphs whose vertices in one part have degree two under the stated size and density condition.Source: §8.2 · pp. 19–20

9 Graphs whose edges are in few triangles

The survey applies dependent random choice when adjacent vertices have few common neighbors, obtaining large sparse induced subgraphs. It uses this approach for triangle-free subgraphs of K5-free graphs and for a book–clique Ramsey bound.

9 Graphs whose edges are in few triangles

  • When every adjacent pair has few common neighbors, dependent random choice yields a large induced subgraph that is sparse.The argument compares the expected size of a common neighborhood with its expected number of edges.Source: §9 · p. 21

9.1 Applications

  • Every K5-free graph on n vertices contains a triangle-free induced subgraph on at least n^5/12/2 vertices.The proof treats separately graphs with large average degree and those with smaller average degree.Source: §9.1 · pp. 22–23

Book-complete graph Ramsey numbers

  • For sufficiently large n, the book–clique Ramsey number satisfies r(Bn, Kn) ≤ 800n³/log^3/2 n.The survey presents this as an improvement by a factor of log^1/2 n over the cited earlier upper bound.Source: Book-complete graph Ramsey numbers · p. 23
  • The book-free condition bounds the number of triangles containing each edge, and the proof uses an independent-set bound to obtain the Ramsey result.The proof assumes each edge lies in fewer than n triangles and applies Proposition 9.3.Source: Book-complete graph Ramsey numbers · p. 23

10 More applications and concluding remarks

The survey samples further applications of dependent random choice across graph theory, combinatorics, and geometry, while noting that its coverage is selective and current versions do not handle very sparse graphs.

Unavoidable patterns

  • Dependent random choice improves the bound for unavoidable patterns in 2-edge-colorings to n(k, ǫ) < (16/ǫ)2k+1, tight up to a constant factor in the exponent.The patterns are members of Fk, as described in the survey.Source: §10 · p. 24

Disjoint edges in topological graphs

  • Dense simple topological graphs contain two large disjoint edge sets with every cross-pair disjoint, and the method also improves a lower bound on pairwise disjoint edges in complete simple topological graphs.The first result holds for graphs with ǫn2 edges; the latter improves the earlier Ω(log n/ log log n) bound of Pach and Tóth.Source: §10 · pp. 24–25

Sidorenko’s conjecture

  • For bipartite H of width w and m edges, tH(G) ≥ tK2(G)m+w; the survey reports the exact Sidorenko inequality for bipartite graphs with a vertex complete to the other part.The exact result uses dependent random choice and yields the stated approximate version for all bipartite graphs.Source: §10 · p. 25

Testing subgraph in directed graphs

  • For testing whether a digraph contains no fixed H, polynomial query complexity in 1/ǫ is possible exactly when H’s core is a 2-cycle or an oriented tree.The proof for an oriented-tree core uses dependent random choice.Source: §10 · p. 26

Ramsey properties and forbidden induced subgraphs

  • For H-free graphs, the survey reports clique-or-independent-set bounds and an asymmetric result: if (log n1)(log n2) ≤ c log N, there is a clique of size n1 or an independent set of size n2.The cited proofs use dependent random choice with an embedding lemma.Source: §10 · p. 26

On a problem of Gowers

  • The first purely combinatorial proof of Gowers’s question used a new, weaker-than-Szemerédi regularity lemma with better bounds, whose proof relies heavily on dependent random choice.Earlier affirmative results used Fourier analysis.Source: §10 · p. 26

Induced subgraphs of prescribed size

  • When q(G) ≤ n/14, dependent-random-choice proofs give u(G) ≥ e^{c log n}; earlier work established u(G) ≥ n^δ.The survey also describes a broader conjecture relating u(G) to |E(G)| when q(G) ≤ n/4.Source: §10 · pp. 26–27

Concluding remarks

  • The survey is selective; current dependent-random-choice versions cannot handle very sparse graphs, and extending the method to non-integer t remains an unresolved technical question.For sparse graphs, the survey suggests sampling vertices close to a small random set; non-integer t is considered likely but current techniques do not establish it.Source: §10 · p. 27
Loading 0909.3271v2…