2. Forbidding a subgraph I: Mantel's theorem and Turán's theorem by MIT OpenCourseWare

Summary by www.lecturesummary.com: 2. Forbidding a subgraph I: Mantel's theorem and Turán's theorem by MIT OpenCourseWare

• 0:00–1:45: Overview of Mantel's Theorem and Extremal Graph Theory

  Extremal graph theory is the subject of the course, focusing on the consequences of forbidding a specific subgraph.

  The query is: how many edges can a graph have if it doesn't contain a particular subgraph? This query is answered for graphs with no triangles by Mantel's theorem.

  A complete bipartite graph (designated K n/2, n/2) serves as the extremal example for Mantel's theorem.

  • For the full bipartite example, this bound is tight: at most floor(n^2 / 4) edges make up a triangle-free graph on n vertices.
  • To demonstrate various graph theory methods, several proofs of Mantel's theorem will be presented.

  1:45–3:55: Initial Validation of Mantel's Theorem (Cauchy-Schwarz Inequality)

  • Configuration: Vertices V and edges E make up the n-vertex triangle-free graph G.
  • Property: Vertices X and Y cannot have any common neighbours if there is an edge connecting them; otherwise, a triangle would form.
  • When XY is an edge, the degrees of its endpoints (deg(X) + deg(Y)) cannot add up to more than n.
  • Examine the sum of squared degrees (Σ deg(X)^2). This sum is equal to the sum of (deg(X) + deg(Y) over all edges XY.
  • The sum of squared degrees is at most mn (number of edges * n), since deg(X) + deg(Y) is at most n for any edge XY.
  • The handshaking lemma states that the sum of degrees (Σ deg(X)) is twice the number of edges (2m).
  • When the Cauchy-Schwarz inequality is applied to the sum of degrees, it relates (Σ deg(X))^2 to Σ deg(X)^2.
  • The inequality yields (2m)^2 <= n * (Σ deg(X)^2).
  • The upper bound for Σ deg(X)^2 can be substituted as follows: 4m^2 <= n * (mn).
  • This reduces to m <= n^2 / 4.
  • m is at most the floor of n^2/4, since it must be an integer. The proof is now complete.

  3:55–6:55: Second Proof of Mantel's Theorem (Independent Sets)

  To begin, choose A, a subset of vertices that is a largest independent set of G. There are no edges in an independent set.

  Any vertex's neighbourhood needs to be an independent set to avoid forming a triangle with the vertex itself.

  • This means that each vertex's degree is at most the size of the largest independent set (|A|).
  • Let B be A's complement (V \ A).
  • Since A is an independent set, no edge in the graph can be completely contained within it; instead, every edge must intersect B.
  • The total of the vertices' degrees in B is the maximum number of edges (this may overcount edges within B).
  • The sum of the degrees in B is at most |B| * |A| since each vertex in B has a degree of no more than |A|.
  • The AM-GM inequality suggests that |A||B| <= n^2 / 4 based on the fact that |A| + |B| = n.
  • As a result, there are no more than n^2/4 edges. This offers yet another example.
  • Every vertex in B is complete to A, there are no edges within B, and the sizes of A and B should be almost equal (|A| ≈ |B| ≈ n/2) according to an analysis of the equality case in this proof.
  • This equality configuration is the unique maximal example (having the maximum number of edges) among triangle-free graphs, and it corresponds exactly to the complete bipartite graph with two equal or nearly equal parts.

  • 6:55–7:40: Applying Turan's Theorem to Generalise from Triangles to Cliques

    Next steps: The question of what would happen if we forbid graphs other than a triangle, that is, a clique on r+1 vertices (K r+1), is the logical next step.

    The query then becomes: how many edges can there be on n vertices in a K r+1 free graph?

    Complete r-partite graphs with n vertices divided into r parts and edges existing only between vertices in different parts are good candidates for K r+1 free graphs with many edges.

    A complete r-partite graph should have part sizes that are as equal as possible in order to maximise edges.

    These graphs, represented by the notation T n,r, are known as Turan graphs.

    The Turan graph T n,r is the extreme example, according to Turán's theorem; a K r+1 free graph cannot have more edges than T n,r.

    Turán's theorem is a generalisation of Mantel's theorem, which prohibits K3 in the case r=2.

    Since it is not always easy to generalise the earlier proofs, Turan's theorem will be demonstrated in three different ways.

    7:40–10:00: Initial Inductive Proof of Turan's Theorem

    Induction on the number of vertices (n) is used in this proof. One of the rare occasions induction will be a crucial method in this course is this one.

    For small n, the base case is trivial.

    Assume that all graphs with fewer than n vertices are covered by the theorem.

    Assume that G is a K r+1 free graph with n vertices and as many edges as possible.

    Claim: A clique on r vertices (K r) must be present in G. If not, maximality would be violated since more edges could be added while keeping K r+1 free.

    Let B be the complement (V \ A) and A be the vertices of an r-clique in G.

    In order to avoid forming a R+1 clique with A, each vertex in B can have at most r-1 neighbours in A.

    Edges within A (R choose 2) + edges between A and B (at most |B|(r-1)) + edges within B is how to count the edges in G.

    Examine the subgraph that B induces, which is likewise K r+1 free, using the induction hypothesis.

    If the original graph G was a Turan graph, then this edge count and the Turan graph T n,r would be equal. This suggests that the Turan graph is the tight example.

    10:00–17:40: Second Proof of Zikov Symmetrisation (Turan's Theorem)

    Zikov symmetrisation is the name of this proof technique.

    Assume that G has the most edges and is a maximal n-vertex K r+1 free graph.

    The assertion is that G's complement must be an equivalence relation. This indicates that the complement of G is a disjoint union of cliques and that non-edges form equivalence classes. For the Turan graph example, this property is true.

    Evidence of claim: Assume for contradiction that there is an edge XZ but non-edges XY and YZ.

    Demonstrate that, for a non-edge XY, if deg(Y) < deg(X), you could increase edges while keeping K r+1 free by substituting Y with a "clone" of X, which is a new vertex connected to the same neighbours as X. Since this goes against maximality, deg(Y) >= deg(X) for any non-edge XY. Likewise, deg(Y) >= deg(Z) for non-edge YZ.

    Now, if XZ is an edge and XY and YZ are not, then a new graph G' is created by substituting clones of Y for X and Z (importantly by utilising the existence of edge XZ). Moreover, G' is K r+1 free.

    Determine the edges in G': E(G') = E(G) - edges incident to Z and X + edges incident to Y's two clones. Applying the degree conditions (deg(Y) >= deg(X), deg(Y) >= deg(Z)) and the presence of edge XZ, it is demonstrated that E(G') > E(G). This runs counter to G's maximality.

    Thus, the first presumption must be incorrect: XZ must likewise be a non-edge if XY and YZ are not edges. This demonstrates that the complement is an equivalency relation.

    • G must be a complete multipartite graph since the complement is a disjoint union of cliques.
    • G can have at most R parts; if not, it would have a K r+1.
    • The components of a complete R-partite graph must be nearly equal size in order to maximise edges. Moving a vertex can result in more edges if part sizes differ by more than one.

      The Third Proof of Turan's Theorem

      The proof will take place from 17:40 to 23:30. It employs the probabilistic method to add randomness to a non-random problem.

      Overview of the Proof

      Let's begin with G, a K r+1 free graph with n vertices and m edges.

      Examine a random sorting (ordering) of the vertices.

      Based on this random order, define a greedy set X of vertices by including a vertex V if it is adjacent to all earlier vertices in the order.

      Claims

      • The first claim is that the set X is a clique.
      • Claim 2: The total of all vertices V and the probability that V is a part of X is the expected size of X.
      • Given that X is a clique and G is K r+1 free, X's size (and consequently its expected size) is at most r.

      Thus, Σ (1 / (n - deg(V) + 1)) <= r.

      When degrees are almost equal, this sum is minimized using convexity.

      The bound m <= (1 - 1/r) * n^2 / 2 is obtained by rearranging.

      This limit is roughly the Turan graph's edge count. It gives a bound that is "basically as good as Turan's theorem" and matches exactly if n is divisible by r.

      Unresolved Issues: Turan's Theorem for Hypergraphs

      • Although Mantel's and Turan's theorems appear straightforward, a slight modification of the problem raises challenging open questions.
      • As an illustration, consider switching from graphs, where edges are pairs of vertices, to hypergraphs, where edges are sets of vertices.
      • One significant open problem is Turan's theorem for three-uniform hypergraphs (edges are triples of vertices).
      • A tetrahedron (K4 as a 3-uniform hypergraph, where all 4 triples of 4 vertices are edges) is prohibited.
      • Good extremal examples are hard to come by. By splitting vertices into three sections and incorporating particular kinds of triples, Turan proposed a construction. There is no tetrahedron in this construction.
      • For this construction, the edge density (fraction of all possible triples) is 5/9. It is hypothesized that this is the ideal value.
      • The most well-known upper bound, determined by computerized techniques such as flag algebras, is roughly 0.562.
      • It is a major open problem to prove or disprove the 5/9 conjecture. A significant "first-order gap" is defined as the difference between 5/9 and 0.562.

      Define the Extremal Number ex(n, H)

      In general, if you forbid a general graph H, how many edges can there be?

      The extremal number, represented by the notation ex(n, H), is introduced. Another name for it is the Turan number.

      The maximum number of edges in an n-vertex graph that contains no copy of H as a subgraph is defined as ex(n, H).

      Subgraph vs. Induced Subgraph

      • A subgraph needs a subset of the larger graph's edges and vertices.
      • A subset of vertices and all edges from the larger graph whose endpoints are both in the vertex subset are necessary for an induced subgraph.
      • This chapter discusses prohibiting subgraphs, not necessarily induced subgraphs.

      Erdos-Stone-Simonovits Theorem: Extremal Number and Chromatic Number

      A summary of Turan's clique theorem: Asymptotically, ex(n, K r+1) is (1 - 1/r) * n^2 / 2.

      The chromatic number of H (χ(H)) is the critical parameter that controls the behavior of ex(n, H) for a general graph H.

      The chromatic number is the bare minimum of colours required to appropriately colour H's vertices

      Extremal Number and Chromatic Number, 26:15-30:20

      Summary of Turan's Clique Theorem

      Asymptotically, ex(n, K r+1) is (1 - 1/r) * n^2 / 2.

      Chromatic Number of H

      The chromatic number of H (χ(H)) is the critical parameter that controls the behavior of ex(n, H) for a general graph H.

      The chromatic number is the bare minimum of colors required to appropriately color H's vertices.

      Key Relationships

      • χ(K r+1) = r+1
      • χ(T n,r) = r
      • χ(H) ≤ χ(G) if H is a subgraph of G

      The Turan graph T n,r is H-free if H has chromatic number r+1 because χ(T n,r) = r, and if H were a subgraph, its chromatic number would be at most r.

      This provides a lower bound: ex(n, H) is at least the number of edges in T n,r, where r = χ(H)-1.

      For any fixed graph H, the limit of the edge density ex(n, H) / (n^2/2) as n approaches infinity is 1 - 1 / (χ(H)-1), according to the Erdos-Stone-Simonovits theorem.

      According to this theorem, the extremal number's first-order asymptotic behavior is entirely determined by the chromatic number.

      Examples Supporting the Theorem

      • χ=3, limit = 1/2 (Mantel), and H=K3 (triangle)
      • H=K4, χ=4, limit = 2/3 (Turan)

      For instance, the Peterson graph, which has χ=3, is not bipartite because it has a 5-cycle. Given its complexity, it may come as a surprise that the theorem predicts that its extremal number density limit is 1/2.

      Bipartite Graph Restrictions and Additional Unresolved Issues

      • The finer details (the "little O" term) are not provided by the Erdos-Stone-Simonovits theorem, but the first-order asymptotics are.
      • Importantly, H's chromatic number is 2 if it is a bipartite graph. According to the theorem, the limit is 1 - 1/(2-1) = 0. Thus, ex(n, H) = little O of n^2.
      • For bipartite graphs, this zero limit is not a satisfactory answer with respect to the true asymptotic order (e.g., is it n^(3/2), n^(4/3)?).
      • Finding the first-order asymptotics of ex(n, H) is a very difficult open problem for most bipartite graphs H.
      • Techniques for upper bounds for bipartite H will be the main topic of future lectures, which will also demonstrate constructions that match these bounds in a few examples.
      • Bipartite graphs H for which the first-order asymptotics are known are extremely rare. There are significant, long-standing combinatorial open problems in this field.
      • Later on, we'll discuss the proof of Erdos-Stone-Simonovits, which may employ a combinatorial proof or Szemeredi's regularity lemma.

      Particular Bipartite Issues and Cultural Notes

      Extremal numbers for simple bipartite graphs, such as complete bipartite graphs K s,t (also referred to as the Zarankiewicz problem or cage problem), will be covered in future topics.

      Only a few values of s and t have a known answer for K s,t; for the majority of values (such as K4,4), the correct exponent on n is unknown.

      Demonstrating Complexity

      • This demonstrates how the previously seen straightforward proofs are "deceptively simple" because the associated problems are still quite challenging.
      • Algebraic and probabilistic construction methods will be discussed in the future.

      The prevalence of Hungarian names in this field (such as Erdos and Simonovits) is a cultural observation. Pronunciation tips for "s" (like "sh") and "sz" (like "s") are provided.