1. A bridge between graph theory and additive combinatorics by MIT OpenCourseWare

Summary by www.lecturesummary.com: 1. A bridge between graph theory and additive combinatorics by MIT OpenCourseWare

• Overview of the Course and Introduction

  • Greetings from 1827: Additive Combinatorics, Graph Theory, and Combinatorial Theory.
  • The two primary components of the course are additive combinatorics and extremal graph theory.
  • It all started with Isaac Schur approximately a century ago.
  • All course information is available on the course website.

  Schur's Theorem and Fermat's Last Theorem Modulo P

  • Schur used the equation modulo P to demonstrate Fermat's Last Theorem.
  • In the end, Schur demonstrated that this strategy is ineffective.
  • The Fermat equation modulo P has non-trivial solutions for all P sufficiently large for all values of n.
  • Schur's theorem is the result from which this deduction is derived.

  Schur's Theorem: Finitary vs. Infinitary Forms

  • The Infinitary form of Schur's Theorem: There is a monochromatic solution to the equation x + y = z if the positive integers are coloured with a finite number of colours.
  • Schur's Theorem (final version): A monochromatic solution to x + y = z must exist within the set {1,..., N} if the numbers 1 through N are coloured using R colours.
  • A common diagonalisation trick can be used to display the infinitary version that implies the finitary version.
  • In combinatorics, quantitative questions like "how large N must be as a function of R" are typically very challenging and constitute major open problems.

  Deriving a Number Theory Outcome from Combinatorial Schur's Theorem

  • It asserts that there exist X, Y, and Z in {1,..., P-1} such that X^n + Y^n = Z^n mod P for any positive integer n and for all sufficiently large primes P.
  • Assuming combinatorial Schur's theorem, the proof is as follows: Examine the multiplicative group of residues that are not zero modulo P.
  • If P is large enough, one H coset must contain X, Y, and Z so that X + Y = Z (as integers) according to Schur's combinatorial theorem.
  • The non-trivial solution to Fermat's equation modulo P is x^n + y^n = z^n mod P, which is obtained by substituting into the equation X + Y = Z and cancelling 'a' modulo P.
  • Proving Schur's theorem's combinatorial claim is the last step.

  Graph Theory Connection: Ramsey's Theorem

  • Ramsey's Theorem is a very similar-looking theorem that states: For every R (number of colours), there exists some large N such that if the edges of the complete graph K_N on N vertices are R-colored, then there exists a monochromatic triangle.
  • Before his death at age 26, Frank Ramsey made important contributions to economics, philosophy, and mathematical logic—the field from which this theorem originated.

  Proof of Ramsey's Theorem for Triangles

  • Any triangle with three vertices is monochromatic when R=1.
  • Assume that for R-1 colours, where M' is the corresponding number of vertices, the claim is true.
  • In a graph where N = R * (M' - 1) + 2 vertices, choose a random vertex V.
  • According to the pigeonhole principle, at least M' edges from V must be the same colour (yellow, for example).
  • Examine the subgraph that V_0 creates: If there is a yellow edge in V_0, it joins vertex V to form a monochromatic yellow triangle.
  • As |V_0| is at least M', the inductive hypothesis requires that V_0 contain a monochromatic triangle in one of the remaining colours; otherwise, the edges must be coloured with no more than R-1 colours.

  • Using Ramsey's Theorem to Prove Schur's Theorem

    By connecting it to Ramsey's theorem, Schur's theorem is intended to be proved.

    Steps to Prove Schur's Theorem

    • First, R-color the integers 1 through N.
    • Create a full graph with N+1 vertices and label it 1, 2,..., N+1.
    • Use the color assigned to the number |j - i| to color the edge between vertex i and vertex j.
    • This gives the edges of the entire graph an R-coloring.
    • According to Ramsey's theorem, a monochromatic triangle exists if N is sufficiently large (i.e., N+1 vertices).
    • Let I, J, and K be the triangle's vertices.
    • The color of the edges is the same for (I,J), (J,K), and (I,K).
    • Under the original integer coloring, the colors of these edges match the numbers J-I, K-J, and K-I.
    • As a result, the color of the three numbers J-I, K-J, and K-I is the same.
    • Assign Z = K-I, Y = K-J, and X = J-I.
    • Note that X + Y = Z.
    • Thus, X, Y, and Z complete the proof of Schur's theorem by forming a monochromatic solution to x + y = z.
    • Switching to graphs has the benefit of increased flexibility, including the use of inductive arguments.

    Open Problems

    In general, enquiries concerning the precise bounds for N in these theorems are open problems.

    • The known lower and upper bounds are frequently separated by wide, exponential gaps.

    Course Logistics and Introduction to Modern Additive Combinatorics

    A brief break was suggested. A tour of modern additive combinatorics is given in the second half of the lecture. This is an extremely dynamic and fascinating area of study.

    Writing course notes and adding to Wikipedia articles about the topic are examples of course assignments.

    After class, there are office hours in the math common room, with dedicated time for homework enquiries.

    Course Assignments

    • Writing course notes entails both drafting and reviewing with the teacher.
    • In the early 2000s, Terry Tao came up with the term "additive combinatorics."
    • Graph theory, logic, discrete geometry, ergodic theory, harmonic analysis, and model theory are all related to this field.

    Important Developments in Additive Combinatorics (Post-Schur)

    About a century ago, Schur's theorem was established.

    Key Theorems

    • Van der Waerden's Theorem (1927): There are arbitrarily long arithmetic progressions (APs) in every finite coloring of the positive integers.
    • Erdos-Turán Conjecture (1936): There are arbitrarily long arithmetic progressions in every subset of the positive integers or integers with positive density.
    • Roth's Theorem (1953): Demonstrated for the case of three-term arithmetic progressions (k=3).
    • The full Erdos-Turán conjecture was resolved by Semerédi's Theorem in the late 1970s.
    • A fundamental, profound theorem with an intricate original combinatorial proof.
    • Encouraged further investigation and alternative evidence from other fields.
    • Furstenberg's perspective on ergodic theory: A sophisticated proof was discovered that permitted proving extensions that were not then combinatorially possible.

    Recent Advance

    Higher Order Fourier Analysis

    Tim Gowers (~2000): A potent extension of Fourier analysis that enables comprehension of longer APs (standard Fourier analysis fails for k > 3).

    • In part, this development earned Gowers a Fields Medal.
    • Hypergraph Regularity (Rödl, Gowers, early 2000s): An extension of Szemerédi's graph regularity method, this method required "an enormous amount of time and effort" to work out, but it produced a method that allowed combinatorial proofs of results that were previously only known via ergodic theory.
    • Offered a different combinatorial demonstration of Roth's theorem.

    The Polymath Project is an online collaborative project that was started by Terry Tao and Tim Gowers.

    • Semerédi's theorem is implied by the density Hales-Jewett theorem (related to Tic-Tac-Toe), which was proven combinatorially in the first successful Polymath project.
    • The pseudonym DHJ Polymath is used to publish papers.

    Semerédi's contributions earned him an Abel Prize.

    The conceptual relationship between the various approaches (ergodic theory, harmonic analysis, and graph theory) is still unclear, but a major theme is the dichotomy between structure and randomness (or pseudo-randomness). This entails separating the noise from the underlying structure.

    Generalisations of Semerédi's Theorem

    • Multi-dimensional Semerédi Theorem (Furstenberg, Katznelson): Any subset of the D-dimensional lattice with positive density contains arbitrary constellations (finite patterns that can be translated and dilated).
    • Finding a 10x10 square grid pattern is one example.
    • Ergodic theory was initially used to prove it.
    • In contrast to ergodic theory proofs, which use compactness and provide no bounds, combinatorial proofs (using hypergraph regularity) were later and had the advantage of offering concrete quantitative bounds.
    • An analogy would be similar to identifying a selected shape among the stars in the film "A Beautiful Mind."
    • Polynomial Semerédi Theorem (Bergelson, Leibman): Any subset of integers with positive density contains arbitrary polynomial patterns (of the form x, x+p_1(y),..., x+p_k(y), where p_i are polynomials with integer coefficients and zero constant terms).
    • Lovász posed a special case (finding x, x+y^2), to which Furstenberg and Sárközy responded in various ways.
    • As of right now, ergodic theory is the only known proof of the general result.

    The Green-Tao Theorem

    The primes contain arbitrarily long arithmetic progressions.

    • This is a well-known outcome from the previous few decades.
    • Since density decays like 1/log n, the primes don't have positive density.
    • Semerédi's theorem does not directly lead to the theorem.
    • Semerédi's theorem was applied as a black box in the proof to a related set known as the pseudo-primes, where the primes have a comparatively positive density.
    • Semerédi's theorem is transferred from a dense to a sparser setting using this method.
    • Additionally, they demonstrated that arbitrarily long APs can be found in any subset of the primes with a relatively positive density.
    • The proof used concepts from number theory, harmonic analysis, and combinatorics.

    Linking Graph Theory to Roth's Theorem

    Now, the course will concentrate on simpler outcomes, beginning with a review of Roth's theorem.

    • The finite form of Roth's Theorem: Size little o of N is required for any subset of integers 1 through N that does not contain three-term arithmetic progressions.
    • The infinitary positive density statement is equal to this finite statement.
    • In the 1970s, Ruzsa and Szemerédi provided a graph theoretic proof.
    • Finding the "right" graph theoretic question is necessary to make this connection.
    • The maximum number of edges in a triangle-free graph on N vertices is a naive guess.
    • About a century ago, Mantel's theorem provided an answer to this question: a complete bipartite graph with two equal halves can reach a maximum of N^2/4.
    • Mantel's theorem is not the right question for Roth's theorem, and it is comparatively simple.

    • The maximum number of edges in an N-vertex graph where every edge lies in exactly one triangle is the "right" graph theoretic question. This is an odd graph property.

      An indication of the relationship: Edges that lie in distinct triangles are related to trivial 3-term APs (x, x, x).

      Quantitative Limits for Open Problems and Roth's Theorem

      There is a wide open question regarding the asymptotics for the size of the largest subset of {1,..., N} that avoids 3-term APs.

      • A set size of about N / exp(c * sqrt(log N)) is the most well-known lower bound.
      • The best known upper bound is N / log N.
      • The distance between these boundaries is still quite wide.
      • It is still open for Erdős to conjecture that arbitrarily long APs can be found in a subset of positive integers with divergent harmonic series.
      • An upper bound of O(N^2) for the number of edges in the particular graph problem associated with Roth's theorem can be proved using Semerédi's regularity lemma.
      • The most well-known solution to the "exactly one triangle" graph problem is derived from the most well-known solution for big sets devoid of 3-term APs.
      • Throughout the course, additional links between graph theory and additive combinatorics will be demonstrated.

      Upcoming Topics

      Extremal graph theory will be covered in the upcoming lectures. This includes queries concerning the most edges a graph can have while prohibiting specific configurations, like:

      • A triangle
      • A 4-cycle
      • Another graph H

      There are still a lot of fascinating unsolved issues in this field.