5. Forbidding a subgraph IV: dependent random choice by MIT OpenCourseWare

Summary by www.lecturesummary.com: 5. Forbidding a subgraph IV: dependent random choice by MIT OpenCourseWare 

• Summary of the Lecture: Dependent Random Choice: Prohibiting a Subgraph

  An overview of the Kővári-SóS-Turán theorem for complete bipartite graphs K_{s,t} is presented:

  • The theorem gives an upper bound of O(n^(2 - 1/s)).
  • Questions arise about achieving better results for sparser bipartite graphs.
  • A theorem (Farad/Alon-Vershynin-Sudakov) is introduced for bipartite graphs H.
  • If R is small in relation to S in K_{S,T}, a better upper bound of O(n^(2 - 1/R)) can be provided.
  • The exponent 1/R in this bound is ideal.

  Dependent Random Choice (DRC)

  DRC is a significant probabilistic method used to demonstrate the bounded degree theorem:

  • Unofficial concept: Find a large subset of vertices U in a graph with many edges.
  • An analogy: Choose an 'anchor' person to find a well-connected group of friends.
  • Formal statement: A subset U has at least M common neighbours for each R-element subset.
  • DRC approach: A uniform random selection of T 'anchor' vertices is made.
  • Define a set A as the set of T's common neighbours.
  • Determine the expected size of A; it is at least proportional to n alpha^t.
  • If an R-element subset S has fewer than M common neighbours, it is considered "bad."
  • The likelihood that a fixed R-element subset S is contained in A is calculated.
  • Use (n choose R) * (M/n)^t to limit the expected number of bad R-element subsets.
  • The expected size of A must be sufficiently large to support the DRC theorem hypothesis.
  • Cleaning step: Remove vertices from A to create a smaller set A' free of bad R-element subsets.

  The Bounded Degree Theorem Proof Sketch Using DRC

  • Utilize the lemma of Dependent Random Choice.
  • Set the auxiliary parameter t to R, the highest degree in A of H.
  • Prove the DRC lemma's hypothesis for appropriate constants.
  • A set U is given at the end of DRC with at least |V(H)| common neighbours.
  • Insert the partition B's vertices into the set U.
  • Embed the vertices of partition A of H into G.
  • Each vertex of A can be embedded into a unique location in G.
  • This procedure proves the theorem by embedding H into G.

  Extreme Issues with Even Cycles (C_{2k})

  • Other sparser bipartite graphs, such as even cycles (C4, C6, etc.), are discussed.
  • K2,2 is C4; for graphs where every vertex in A has degree at most 2, the bound is O(n^(3/2)).
  • The Bondi-Simonovits theorem states the extremal number of C_{2k} is at most O(n^(1 + 1/k)).
  • This bound is superior to n^(3/2) from the general bounded degree theorem.
  • For k=2, 3, and 5, the Bondi-Simonovits bound is known to be tight.

  Proof Sketch for a Weaker Even Cycle Theorem

  • The weaker theorem states there is an even cycle of maximum length 2k in every graph with at least C n^(1 + 1/k) edges.
  • Lemma 1 states every graph G has a subgraph with a minimum degree at least half of the average degree of G.
  • Lemma 2 states every graph G has a bipartite subgraph containing at least half of G's edges.
  • The proof sketch begins with G and moves on to a bipartite subgraph with a large minimum degree.
  • Construct layers of vertices by expanding paths.
  • If there are no cycles, the minimum degree condition suggests exponential growth.
  • This growth contradicts the total number of vertices, implying a cycle must exist.

  • Reviewing Graphs without C4 and Bounded Degree (R=2)

    An n^(3/2) bound is provided by the first theorem's R=2 case. K2,2 (C4) makes this tight.

    Key Question

    If graph H does not contain K2,2 as a subgraph, can we improve the n^(3/2) bound for graphs with bounded degree at most 2 on one side?

    Indeed. According to a recent theorem (Conlon and Lee), the exponent can be lowered below 3/2 if H is bipartite, with a maximum degree of 2 on one side and no K2,2 subgraph. The presence of K2,2 is associated with the 3/2 exponent.

    Related Statements

    The statement that the extremal number of the one-subdivision of a clique (KT') can be improved upon the exponent provided by the first theorem is qualitatively equivalent to this result.

    A vertex is added to the middle of each edge of H to create a one-subdivision of H (H').

    K3', a triangle that is a subdivision of K3, is a C6. When KT' (the subdivision of K_t) is subjected to the Conlon-Lee theorem, a particular exponent associated with t is obtained.

    KT's Free Theorem Proof Sketch

    Preparation Lemma

    • Go to a sizable, nearly regular, bipartite subgraph G' that has a balanced partition.
    • Although not entirely proven, the details are comparable to those of previous simple lemmas.
    • G' has a controlled degree distribution and keeps a significant number of vertices and edges.

    Identifying Vertex Pairs

    • Using the number of their common neighbours on the other side (B), identify "light" and "heavy" pairs of vertices on one side (U) of the bipartite graph G'.
    • A pair is considered heavy if at least T chooses two common neighbours, and light if at least one and less than T chooses two common neighbours.

    Lemma

    There is a vertex on side U that is involved in numerous "light" pairs in a KT' free bipartite graph with a sufficient minimum degree. Because it keeps all pairs from being heavy, the KT's free condition is essential.

    Proof Sketch of the Lemma

    For paths between U and B of length 2 (K1,2s), use a double counting argument. A count is obtained by adding up all of the vertices in B, weighted by (degree choose 2). B's low-degree vertices don't make much of an impact. High-degree vertices make a significant contribution. Examine the high-degree vertex neighbourhoods in B using Turan's theorem. T mutually heavy vertices cannot exist in U since the graph is KT' free. According to Turan's theorem, there must be a large number of "light" pairs in B's high-degree vertex neighbourhoods. There are numerous light pairs in U, as indicated by adding up B.

    KT's Theorem Proof Sketch

    Determine a sequence of T vertices V1, V2,..., VT on side U by iteratively applying the lemma.

    Important Characteristics

    • All V_i and V_j pairs are light.
    • No three Vs share a neighbour.
    • The vertex sets U used in the iterative process do not significantly shrink in size.
    • The set U_{i+1} is light to V_i.

    Building the KT' Subdivision

    • A KT' subdivision can be built using the common neighbours of Properties 1 and 2.
    • Each pair is guaranteed at least one common neighbour by the 'light' property.
    • Property 2 (no three common neighbours) guards against collapses that would compromise KT's structural integrity.

    Iterative Building Process

    • The lemma is used to build the sequence iteratively (property 3 guarantees that there are enough vertices left).
    • Because this restriction limits the number of options at each stage, Property 2, which is about triple common neighbours, is manageable.