3. Forbidding a subgraph II: complete bipartite subgraph by MIT OpenCourseWare

Summary by www.lecturesummary.com: 3. Forbidding a subgraph II: complete bipartite subgraph by MIT OpenCourseWare

• • Introduction to Extremal Graph Theory and Turan's Theorem [0:00]

    • Continues the discussion of extremal graph theory. [0:00]
    • Recalls the problem of finding the maximum number of edges in an N-vertex graph that is H-free, denoted as ex(n, H). [0:10]
    • Mentions the Erdős-Stone-Simonovits theorem, which states that ex(n, H) is largely governed by the chromatic number of H [0:22].
    • If H is not bipartite (chromatic number at least three), the theorem gives the first-order asymptotics for ex(n, H) [0:36].
    • If H is bipartite (chromatic number is exactly two), the theorem only states that ex(n, H) is little O of N squared, which doesn't provide the full story [0:43].
    • The next lectures will explore what more can be said about ex(n, H) for bipartite graphs H [0:54].
    • This area has many open problems regarding the growth rate of this function for bipartite graphs [0:58].

  • The Zarankiewicz Problem and Complete Bipartite Graphs (K_s,t) [1:07]

    • The complete bipartite graph K_s,t plays a special role, with S vertices on one side and T vertices on the other [1:11].
    • Understanding the extremal number for K_s,t is a famous open problem known as the Zarankiewicz problem [1:22].
    • Little is known about this problem [1:28].
    • Every bipartite graph H is a subgraph of some K_s,t [1:32].
    • If a graph is H-free, it is automatically K_s,t-free if H is a subgraph of K_s,t [1:36].
    • Therefore, an upper bound on ex(n, K_s,t) provides an upper bound on ex(n, H) for any bipartite graph H that is a subgraph of K_s,t [1:40]. However, better bounds might exist for specific H [1:47].

  • The Kővári–Sós–Turán Theorem (KST Theorem) [1:51]

    • The most important theorem concerning the Zarankiewicz problem is the result due to Kővári, Sós, and Turán [1:55].
    • The Kővári–Sós–Turán theorem states that for fixed integers s and t (with s ≤ t), there exists a constant C such that ex(n, K_s,t) is upper bounded by something on the order of n^(2 - 1/s) [2:03].
    • This shows that the bound is sub-quadratic, with a gap from 2 in the exponent [2:15].
    • The theorem is easily remembered as the KST theorem, referring to K_s,t and the initials of the authors [2:26].

  • Proof of the KST Theorem via Double Counting [2:33]

    • The proof uses a double-counting argument [2:35].
    • Consider a graph G with n vertices, m edges, which is K_s,t-free [2:39].
    • The argument counts the number of stars K_{s,1} (configurations with a central vertex connected to S other vertices) in G [2:42].
    • An upper bound on the number of K_s,1 stars is derived from the K_s,t-free property: every subset of S vertices has at most t-1 common neighbours [2:56]. If they had t common neighbours, it would form a 

      • Lower Bounds on K_s,1 Stars

        • A lower bound on the number of K_s,1 stars is derived from the number of edges (m) using a convexity argument on the sum of binomial coefficients involving vertex degrees [3:06]. The sum of degrees is twice the number of edges [3:34].
        • Combining the upper and lower bounds gives an inequality relating m and n [3:44].
        • Using asymptotics (n choose s grows like n^s/s! for fixed s) [3:54], the inequality is simplified [4:03].
        • Rearranging the inequality yields the upper bound for m: m is on the order of n^(2 - 1/s) for fixed S and T [4:13].

      • Questions and Discussion on the KST Theorem

        • The argument for the KST theorem does not strictly require s ≤ t, but for better asymptotics as n grows, s should be less than or equal to t [4:37].
        • The tightness of the KST bound is a major open problem in extremal graph theory [4:55].
        • The bound is conjectured to be tight, but this is only proven for a small number of S and T values, such as (2,2), (3,3), and (4,7), and when T is much larger than S [5:01, 5:28].
        • There's unexplored territory regarding when the bound is sharp [5:34].

      • Applications of the KST Theorem: Unit Distance Problem

        • Begins with a geometric application: Erdős's unit distance problem [5:45].
        • Asks for the maximum number of unit distances among n points in the plane [5:48].
        • Small examples are shown (3, 4, 5, 6, 7 points) [5:57 - 6:24].
        • Small examples can be misleading for the large n case [6:31].
        • The problem for large n is a major open problem [6:36].
        • Simple constructions like points on a line (n-1 unit distances) or arranged to maximize connections (2(n-1) unit distances) are discussed [6:47, 7:01].
        • Translating a configuration doesn't help much [7:13].
        • Replacing vertices with triangles is a similar idea [7:29].
        • Erdős's construction using a square grid (root n by root n) [7:53].
        • Taking the unit distance to be root r, where r is a sum of two squares in many ways (product of primes 1 mod 4) [8:08].
        • This construction yields n^(1 + c/log log n) unit distances, which is better than previous constructions [8:25].
        • Upper bounds are needed for this problem [8:30].
        • An upper bound can be deduced from the KST theorem: any set of n points in the plane has at most on the order of n to the three halves unit distances [8:41].
        • Proof: Consider the unit distance graph (vertices are points, edges connect points at unit distance) [8:49].
        • This graph is K_{2,3}-free [8:53]. Why? Two points have at most two common neighbors (intersections of unit circles centered at the points) [9:01].
        • Therefore, the number of edges (unit distances) in this graph is upper bounded by ex(n, K_{2,3}), which is at most order n^(2 - 1/2) = n^(3/2) by KST [9:06].
        • This gives a bound much better than the trivial n choose 2 [8:46].

      • Further Geometric Problems: Distinct Distances Problem

        • Another problem is the Erdős Distinct Distances problem: minimum number of distinct distances among n points in the plane [9:24].
        • These problems are related; many repeated distances imply few distinct distances [9:32].
        • An inequality relates them: number of distinct distances >= n choose 2 / maximum number of unit distances [9:42].
        • Examples: points on a line (n-1 distinct distances) [9:50], square grid (n/sqrt(log n) distinct distances) [9:55].
        • It was conjectured that the square grid is close to the best possible [10:03].
          • • Distinct Distances: This problem was solved by Guth and Katz, showing at least on the order of n/log n distinct distances [10:11]. This was a sophisticated result using techniques like the polynomial method and algebraic geometry [10:21].

          • Lower Bounds for ex(n, H): Constructing Dense H-Free Graphs [10:40]

            • Shift focus: Move from upper bounds (KST) to lower bounds, which means constructing graphs with many edges that are H-free [10:44].
            • Utilize techniques such as the probabilistic method (randomized construction) [10:53] and algebraic constructions [11:12].
            • Understand the probabilistic method: General and robust but often not sharp [11:00].
            • Explore algebraic constructions: More specific ("magical") but can yield tight bounds [11:14].
            • Recent developments: Combine both: randomized algebraic constructions [11:20].

          • Randomized Constructions and the Probabilistic Method [11:32]

            • The probabilistic method is general and applicable for every graph H (especially bipartite H, as Turan graphs are tight for non-bipartite H) [11:36].
            • For a fixed graph H with at least two edges, there exists an H-free graph on n vertices with at least n^(2 - (v(H)-2)/(e(H)-1)) edges [11:48, 12:00].
            • Comparing this to KST for K_s,t: the probabilistic method gives a lower bound of n^(2 - (s+t-2)/(st-1)) [12:15].
            • For K_s,s, this is n^(2 - (2s-2)/(s^2-1)) [12:23].
            • Comparing ex(n, K_s,s) upper bound (KST: n^(2 - 1/s)) and probabilistic lower bound shows a gap, even for K_{2,2} [12:28, 12:37].
            • The correct exponent for K_{2,2} is 3/2, shown by other constructions [12:40].
            • The probabilistic method doesn't always give the right exponent for specific S and T [12:59].
            • The bound from the probabilistic method can sometimes be slightly improved by considering a "denser core" subgraph H' of H, based on the ratio (v(H')-2)/(e(H')-1) [13:07].
            • This ratio is called the two-density or M_q(H) [13:22]. The exponent depends on the maximum of this ratio over subgraphs [13:28].
            • Example: for a graph H with 5 vertices and 8 edges, a subgraph K4 might have a better ratio (4 vertices, 6 edges), potentially improving the bound [13:47, 14:02].

          • Proof Sketch of Probabilistic Construction (Alteration Method) [14:20]

            • The idea is to take a random graph and fix it [14:21].
            • Consider an Erdos-Renyi random graph G(n,p) where each edge exists with probability p [14:28].
            • The expected number of copies of H is computed using linearity of expectation [14:35]. It's roughly proportional to p^(e(H)) * n^(v(H)) [14:46].
            • The expected number of edges in G is p * n choose 2, approximately p * n^2 / 2 [14:53].
            • Choose p such that the expected number of edges is much larger than the expected number of copies of H [14:57].
            • The exponent for p comes from balancing these expectations [15:06].
            • With this p, the expected number of edges minus the expected number of H copies is at least a constant times n^(2 - (v(H)-2)/(e(H)-1)) [15:17].
              • • With this proposition, the expected number of edges minus the expected number of H copies is at least a constant times n^(2 - (v(H)-2)/(e(H)-1)) [15:17].
                • By linearity of expectation, there exists a specific graph instance where the number of edges minus H copies is at least the expectation [15:27].
                • Remove one edge from each copy of H in this graph to make it H-free [15:31].
                • The resulting graph has at least the desired number of edges [15:37].
                • This technique is called the alteration method [15:45].

              • Algebraic Constructions for Tight Bounds

                • Algebraic constructions can provide tight bounds but work in fewer cases [16:02].
                • Shows how to obtain the tight bound for K_{2,2} (a four-cycle) [16:07].
                • Result by Erdos, Renyi, and Sos: ex(n, K_{2,2}) is at least (1/2 - o(1)) * n^(3/2) [16:11].
                • Together with KST, this shows ex(n, K_{2,2}) is approximately (1/2) * n^(3/2) [16:17]. This is one of the few cases where the extremal number is known precisely [16:21].

              • Construction of a K_{2,2}-Free Graph (Polarity Graph)

                • Explicit construction called a polarity graph [16:27].
                • Assume n+1 is the square of a prime p (can adjust n otherwise) [16:29].
                • Vertices are points in the plane over FP, excluding the origin [16:35].
                • Edges between (x,y) and (a,b) exist if ax + by = 1 (mod p) [16:40].
                • Proof of K_{2,2}-freeness: A K_{2,2} involves two points and two common neighbours [16:52].
                • Proof of having many edges: Each vertex (a,b) has degree p-1 or p [17:17].
                • The number of edges is close to (1/2) * n * p, which gives the claimed bound n^(3/2) [17:31].
                • This construction works for n where n+1 is a prime square; can extend to other n by using a prime close to sqrt(n) and adding isolated vertices [17:36, 17:49].

              • Interpretation as Incidence Graph of Projective Plane

                • A bipartite version of the construction can be viewed as the point-line incidence graph of a projective plane over a finite field FP [18:27].
                • One vertex set is points, the other is lines [18:31].
                • Equation for point (x,y,z) on line [a,b,c] is ax + by + cz = 0 [18:37].
                • No four-cycle because two distinct points lie on exactly one line [18:43].
                • The polarity graph combines points and lines, identifying them [18:57].

              • Generalisation to K_{3,3} Free Graphs

                • Can this be generalised to K_{3,3} and higher? Yes [19:11].
                • Construction by Brown for ex(n, K_{3,3}) showing it is at least n^(2 - 1/3) = n^(5/3) [19:20].
                • This exponent is correct (matches KST upper bound), and

                  Generalisation to K_{3,3} Free Graphs

                  • Generalisation to K_{3,3} Free Graphs [19:07]

                    • Yes, this can be generalised to K_{3,3} and higher [19:11].
                    • Brown's construction for ex(n, K_{3,3}) shows it is at least n^(2 - 1/3) = n^(5/3) [19:20].
                    • This exponent is correct (matches KST upper bound) [19:24].

                  • Construction of a K_{3,3}-Free Graph (using Spheres) [19:37]

                    • Assume n is a cube of a prime p [19:43].
                    • Vertices are points in affine 3D space over FP (FP^3) [19:46].
                    • Edges exist between (x,y,z) and (a,b,c) if (x-a)^2 + (y-b)^2 + (z-c)^2 = u for some fixed non-zero u in FP [19:51].
                    • Intuition from real space R3: Three unit spheres intersect in at most two points [20:05].
                    • The unit distance graph in R3 is K_{3,3}-free [20:16].
                    • This geometric intuition translates to an algebraic argument for finite fields [20:18].
                    • Be careful with finite field specifics (e.g., spheres containing lines) [20:30].
                    • If parameters are chosen correctly, the graph is indeed K_{3,3}-free [20:35].
                    • The graph also has many edges; each vertex has degree close to p^2 [20:48].

                  • Higher KSTs and Open Problems [20:56]

                    • Constructions for K_{2,2} are also K_{2,k}-free for k ≥ 2 [21:01].
                    • Generalising these geometric constructions to K_{s,t} for higher s and t is difficult [21:06].
                    • The order of ex(n, K_{4,4}) is a major open problem [21:13].
                    • Algebraic constructions are key to finding large KST-free graphs with many edges [21:19].

                  • Upcoming Topic: Different Algebraic Constructions [21:22]

                    • Next lecture will cover a different type of algebraic construction [21:27].
                    • Theorem by Kollár, Rónyai, and Szabó: if t is much larger than s, then ex(n, K_s,t) is on the same order as the KST upper bound [21:33].
                    • Specific examples of (s,t) where this theorem applies: (2,2), (3,3), (4,7), and others [21:48].
                    • These are algebraic constructions [21:54].