6. Szemerédi's graph regularity lemma I: statement and proof by MIT OpenCourseWare

Summary by www.lecturesummary.com: 6. Szemerédi's graph regularity lemma I: statement and proof by MIT OpenCourseWare 

• 0:00 - 2:19: Introduction

  An informal statement introduces the Regularity of Szemerédi's Graph, developed in the 1970s. This lemma is a potent tool in contemporary graph theory.

  • This holds true for big, dense graphs with a positive edge density.
  • The main idea is that the graph appears "random-like" between the majority of part pairs when the vertex set is divided into a finite number of parts.
  • "Random-like" refers to an edge density that is roughly uniform between typical pairs of parts, though it may differ between pairs of parts.
  • The lemma approximates a graph with bounded information and offers a universal structural description.

  2:19 - 3:31: Formal Definitions

  E(X, Y) indicates the number of edges connecting vertex sets X and Y. The fraction of potential edges that exist between X and Y is represented by the equation E(X, Y) / (|X||Y|).

  • A pair of vertex sets (X, Y) are said to be epsilon-regular if the edge density between A and B differs from the edge density between X and Y by no more than epsilon for all subsets A of X and B of Y that are not too small.
  • According to this definition, edges in such a pair are dispersed equally.

  3:31 - 5:01: Epsilon-Regular Partition and Terminology

  • Although different parameters could be used, the epsilon parameter is used consistently throughout the definitions mainly for convenience.
  • Certain subsets A in X and B in Y that meet the requirement of differing densities can witness the irregularity of a pair (X, Y) that is not epsilon-regular.
  • The distinction between "epsilon-regular" and "d-regular graphs" is typically made clear by context.
  • The pairs (Vi, Vj) define a epsilon-regular partition of the vertex set into subsets V1, V2,..., Vk.
  • If the sum of the sizes of pairs (Vi, Vj) that are *not* epsilon-regular is at most epsilon times the total number of pairs of vertices in the graph (N^2), then the graph is epsilon-regular.
  • Informally, this indicates that only a tiny percentage of vertex pairs are part of irregular partition part pairs.
  • Although i=j in the sum is permitted by the definition, this is usually not a major problem, particularly when there are many parts.

  5:01 - 6:17: The Regularity Lemma Statement by Szemerédi

  • According to the lemma, every graph G has an epsilon-regular partition of its vertex set into at most M parts.
  • Importantly, the graph's size (N) has no bearing on the number of parts (M).
  • For large, dense graphs, the lemma is most helpful.
  • The theorem is true but meaningless for sparse graphs since epsilon-regularity is trivially satisfied for constant epsilon.
  • It is possible for the constant M to be very large.
  • An epsilon-regular partition can be created by splitting each vertex into its own section if the graph contains fewer vertices than M.

  6:17 - 7:36: Additional Remarks and Equitable Partitions

  The lecture emphasizes understanding the spirit of the lemma rather than getting bogged down in specific parameter details.

  • In this context, epsilon-regularity serves as the formal definition of "random-like."
  • Pseudo-random graphs behave similarly to random graphs in some aspects.
  • The lemma is a strong assertion; it is possible to make additions or "decorations" without altering the main idea.
  • An equitable partition can be created in which each component is approximately the same size (varying by no more than one).
  • For every epsilon and minimum number of parts m_0, there exists M such that every graph has an epsilon-regular equitable partition into k parts, where m_0 <= k <= M.

  7:36 - 8:53: The Energy Increment Argument

  • The energy increment argument is a method used in the proof.
  • It begins with an initial partition, such as the m_0 parts or trivial partition with one part.
    • Finding pairs of subsets that witness the irregularity for non-epsilon-regular pairs of parts is how the current partition is refined if it is not epsilon-regular.
    • This refining process is repeated.
    • A concept of energy is defined for a partition to demonstrate that the process stops with a bounded number of parts.
    • This energy is a number that ranges from 0 to 1. Every refinement stage ensures a minimum increase in energy.
    • An epsilon-regular partition results from the iteration stopping after a bounded number of steps because the energy cannot increase past 1.

    Defining Energy (Q)

    The refinement step entails simultaneously refining the partition using all the witnessing sets discovered for all non-epsilon-regular pairs. It is acceptable for witnessing sets to overlap.

    Only one pair of witnessing sets (A_ij in Vi, B_ji in Vj) is required for each non-epsilon-regular pair (Vi, Vj), though many may exist.

    Defining Q

    • For two vertex sets U and W, a quantity Q(U, W) is defined, which is approximately the normalized edge density squared.
    • Q(PU, PW) is a weighted average of Q between portions of PU and PW for partitions PU of U and PW of W.
    • The weighted mean squared density between pairs of parts, Q(P, P), is the definition of the energy of a partition P.
    • Since it is an L2 quantity—a common mathematical convention derived from physics—it is referred to as "energy."

    Lemma 1 and 2: Energy Under Refinement

    Under refinement, energy does not decrease. Lemmas regarding the transformation of energy under refinement are the foundation of the proof.

    Lemma 1

    The energy Q(PU, PW) is always greater than Q(U, W) for any two vertex sets U and W, as well as any partitions PU of U and PW of W.

    • By defining a random variable Z (the density of parts containing randomly selected vertices from U and W) and comparing the expectation of Z squared to the square of the expectation of Z, this convexity claim is demonstrated.

    Lemma 2

    The energy of P' is always greater than the energy of P if a partition P' refines P. When Lemma 1 is applied to each pair of parts in P, this is the direct result.

    Lemma 3: Boosting Energy in Irregular Pairs

    • Energy must occasionally rise to demonstrate that the process stops.
    • Partitioning U into {U1, U\U1} and W into {W1, W\W1} produces an energy Q between these two-part partitions that is strictly greater than Q(U, W) by at least epsilon^4 if a pair (U, W) is not epsilon-regular and is observed by U1 in U and W1 in W.
    • The proof links the difference between E[Z^2] and (E[Z])^2 to the energy difference by utilizing the non-negative variance of the random variable Z (defined in Lemma 1 proof). A minimum non-zero contribution to the variance is ensured by the witnessing condition.
    • According to a witness, this lemma demonstrates an increase in energy when a pair is irregular and refined.

    Lemma 4: Irregular Partition Provides an Overall Energy Boost

    There is a refinement Q of P where each part is refined into at most 2^K parts if a partition P of G into K parts is not epsilon-regular. The energy of Q is at least the energy of P plus a constant that depends on epsilon (at least epsilon^5).

    • This lemma demonstrates that the procedure increases energy at each stage sufficiently.
    • The common refinement for all non-epsilon-regular pairs (Vi, Vj) using witnessing sets is called refinement Q. At most K sets refine each part Vi (one from each other Vj), producing a maximum of 2^K subparts.
    • The sum of Q's energy across all pairs of refined parts is Q's total energy. For epsilon-regular pairs, the Q does not decrease according to Lemma 1. Lemma 3 ensures a boost for non-epsilon-regular pairs.
    • It is implied that the sum of the boost terms over all irregular pairs is at least epsilon^5 (up to constants) by the definition of an epsilon-regular partition (that is, its failure if P is not regular. 

      Completing the Bounds and Proof on Parts

      • Lemma 4 is repeatedly applied to the trivial one-part partition to complete the proof of the regularity lemma.
      • Between 0 and 1, the energy begins. Energy increases by at least epsilon^5 with each step.
      • Therefore, the partition must be epsilon-regular, and the process must terminate after a maximum of epsilon^-5 steps.

      Restrictions on the Quantity of Parts

      The refinement in Lemma 4 can yield up to K * 2^K parts if a partition has K parts. There are a lot of parts after many iterations (epsilon^-5 steps).

      • A tower of twos with a maximum height of 2^(epsilon^-5) is the upper bound on the number of parts.
      • This limit is finite and solely reliant on epsilon rather than N.
      • Even for small epsilon, this bound is astronomically large.
      • Tim Gowers' theorem demonstrates that this large bound is necessary and cannot be significantly improved. A tower of exponentials also serves as the lower bound.

      There is interest in alternative proofs for applications because Szemerédi's regularity lemma is strong but produces quantitatively awful bounds.

      Adjusting for Fair Partitions

      How can the proof be changed to ensure a fair division?

      • Rebalancing is supposed to be incorporated into the iterative procedure.
      • Begin with a preliminary (perhaps fair) division.
      • If the partition is not epsilon-regular, repeat the refinement procedure with witnessing sets.
      • To make the partition equitable, add a rebalancing step after each refinement step. This may entail moving or merging a few vertices or further refining certain parts.
      • Rebalancing may result in a slight drop in energy, but this can be managed by altering just a small percentage of the vertices.
      • An overall energy increase over each iteration is guaranteed by the significant energy increase from the refinement step (at least epsilon^5) (e.g., at least half of epsilon^5).
      • The procedure still produces an equitable epsilon-regular partition in a bounded number of steps.

      The property of being epsilon-regular is not preserved under refinement, so it is not possible to simply apply the standard regularity lemma and then rebalance at the end. The iterative proof process must include the rebalancing.