4. Forbidding a subgraph III: algebraic constructions by MIT OpenCourseWare

Summary by www.lecturesummary.com: 4. Forbidding a subgraph III: algebraic constructions by MIT OpenCourseWare

• Background and Introduction [0:00]

  • Discussed the Kovari-Shuron theorem, which gives an upper bound on the number of edges in a graph that prevents a complete bipartite graph K_st.
  • Mentioned the Turan problem for bipartite graphs.
  • Recalled constructions from the previous time that used the polarity graph to demonstrate that the bound is tight for K_2,2 (order n^(3/2)).
  • Reviewed a sketch utilizing spheres in a finite field space for K_3,3.
  • Noted that both earlier constructions were "algebra-geometric" and explored expanding on these concepts.
  • Cited the state-of-the-art finding by Alon, Kolar, Rier, and Sabul, demonstrating that if t is sufficiently large in relation to s, the extremal number for K_st matches the Kovari-Shuron bound (order n^(2-1/s)).
  • Included examples: K_2,2 and K_3,3 are within this range and were previously known.
  • Noted that while K_4,6 is still open, K_4,7 is covered by this result.
  • Intended to demonstrate two distinct methods for building graphs with algebraic geometry to reach this bound for large T.

  Algebraic Construction 1: The Norm Graph [2:00]

  • Introduced the norm graph, the first construction based on a prime p and N = p^s, where s is at least two.
  • Reviewed the norm map definition from a field extension FPs to the base field FP.
  • Defined the elements of the field extension FPs as the vertices of the norm graph.
  • Connected a pair of distinct vertices, x and y, if and only if the norm of their sum (norm(x+y)) equals one, defining the edges of the norm graph.

  Norm Graph Properties** [3:00]

  • Confirmed the large number of edges in the norm graph.
  • Counted the number of vertices B such that norm(A+B)=1 for any vertex A, roughly equal to p^(s-1).
  • Noted that each vertex has a degree of at least p^(s-1) - 1 (taking loops into account), which is large (N^(1 - 1/s)).
  • Claimed that the total number of edges is on the order of N^(2 - 1/s).

  Norm Graph: KST-Freeness (Weaker Bound) [5:00]

  • Asserted that the construction of this norm graph is K s, s!+1 free.
  • Acknowledged that this bound is marginally weaker than the S-1 factorial previously mentioned.
  • Declared that a stronger S-1 factorial result would be obtained using a different graph.

  KST-Freeness Algebraic Fact [6:30]

  • Invoked a crucial algebraic fact: The system of equations has at most S! solutions for X in the field for any field F.
  • Gave insight into the situation where B_i = 0 for every i, where the solutions are exactly S! and count permutations.
  • Noted that this fact's proof is complex and requires algebraic geometry and commutative algebra.

  Using the Algebraic Fact on the Norm Graph [9:00]

  • Demonstrated how the algebraic fact leads to the KST-freeness of the norm graph.
  • Defined a K_s,t subgraph as finding s vertices (y1...ys) with t common neighbours (x).
  • Noted that a common neighbour x for vertices y1...ys must satisfy norm(y_i + x) = 1.
  • Extended the system into a form that corresponds to the algebraic fact using properties of characteristic p fields.
  • Concluded that any set of S vertices can have at most S! common neighbours.
  • Resulted in the graph being K s, s!+1 free.
  • Clarified that raising to power p is a bijection in the field.

  
  

  • Algebraic Construction 2: The Projective Norm Graph [11:24]

    In order to improve the bound to S-1 factorial for S >= 3, the projective norm graph was introduced as a variant.

    Vertex Set

    The vertex set consists of:

    • A pair (x, y), where y is a non-zero element from FP and x is from the field extension FP(s-1).
    • A total of p^(s-1) * (p-1) vertices.

    Edge Definition

    According to the definition of an edge:

    • There is an edge between (x1, y1) and (x2, y2) if and only if norm(x1 + x2) = y1 * y2.

    Projective Norm Graph Properties

    The number of edges was calculated:

    • Each vertex's degree is precisely p^(s-1) - 1.
    • The total number of edges is 1/2 * (number of vertices) * (degree), or approximately p^(s-1) for N, which is on the order of n^(2 - 1/s).

    KST-Freeness (Stronger Bound)

    The projective norm graph is K s, s-1!+1 free.

    Proof Sketch

    Find common neighbours (X, x) after fixing s vertices ((Y1, y1)... (Ys, ys)).

    • A system of s equations is obtained by the common neighbour condition.
    • It was demonstrated that the first coordinates (Y_i) must be different for there to be a common neighbour.
    • The system of equations was divided and rearranged, resulting in s-1 equations resembling the key algebraic fact but now including FP^(s-1) elements.
    • There are a maximum of (s-1)! solutions for x (after a substitution) when the algebraic fact is applied to this system of s-1 equations.

    This indicates that the graph is K s, s-1! since any s vertices have at most s-1! common neighbours. Free +1.

    Unresolved Issues and Restrictions

    The determination of the extremal number for K_4,4, K_4,5, and K_4,6 is still an open problem.

    • A recent paper demonstrated that the norm graph (the first construction) for s=4 does contain K_4,6; however, this does not prove that the bound is tight for K_4,6.
    • It is unclear if K_st for other (s, t) smaller than the stated threshold (s!+1) is present in the norm graph.

    Algebraic Construction 3: Randomised Algebraic Construction

    Boris Bukh introduced a different, relatively new concept known as a randomised algebraic construction.

    Method Overview

    This method blends concepts from:

    • Algebraic constructions
    • Randomised constructions (such as Erdos-Renyi)

    Assuming S >= 4, it operates over a finite field FQ.

    Definition of Randomised Algebraic Graph

    A random polynomial F is selected in place of selecting edges at random.

    • A uniformly random selection of all polynomials with degree at most 'd' (a large constant depending on S) results in F, a polynomial in 2S variables (S variables for X, S for Y).
    • With vertex sets L and R that are both FQ^S, graph G is bipartite.
    • If and only if the polynomial F evaluates to zero on (X, Y), then there is an edge between X in L and Y in R. The zero set of F is the edge set.

    Randomised Algebraic Graph Properties

    • The graph has many edges.
    • For a fixed pair (X, Y), the probability that F(X, Y) = 0 is precisely 1/Q.
    • (size of L) * (size of R) * (probability of edge) = (Q^S) * (Q^S) * (1/Q) = Q^(2S-1) is the expected number of edges.
    • This corresponds to N^2/Q, the required number of edges, where N=Q^S or N^(2-1/S).

    Rand Alg Graph: KST-Freeness Intuition [23:10]

    It was necessary to demonstrate that there are usually not many KST copies in the graph, in contrast to Erdos-Renyi graphs with independent edge probabilities and roughly Poisson counts of common neighbours.

    Key Insights

    • Things don't behave independently in this algebraic context due to the structure imposed by the polynomial.
    • There are either very few or a limited number of common neighbours.
    • Moments and Markov's inequality for tail bounds are used intuitively to demonstrate this.

    Vanishing Probability Lemma [25:10]

    A lemma was stated: Q^(-SR) is the exact probability that the random polynomial F vanishes on the full Cartesian product of a set U (size S) and a set V (size R).

    Proof Sketch

    • Supplied a proof sketch or intuition by adding a particular random polynomial G so that F+G has the same distribution as F.
    • Demonstrated a bijection using Lagrange interpolation twice (once for each variable).
    • Extended the proof to general U and V by applying random invertible linear transformations to make the coordinates distinct with high probability.

    Tail Bounds and Moments [32:30]

    Calculating the moments of the random variable counting common neighbours for a fixed set U was discussed.

    • The vanishing probability lemma was used to limit the expectation of the D-th moment.
    • Based on the moments, the probability of having more than lambda common neighbours was bound using Markov's inequality.

    Lang-Weil Key Algebraic Geometry Input [38:00]

    • The essential algebraic input: The set of common zeros (an algebraic variety) over FQ for a set of polynomials of degree at most d is either bounded by a constant C or very large (at least Q minus a small term).
    • This contradiction is associated with the Lang-Weil bound, which states that the number of FQ points on an irreducible algebraic variety is roughly Q raised to its dimension, with a deviation that varies with Q.

    Completing the Randomised Algebraic Construction Proof [41:40]

    • Used the dichotomy of algebraic geometry: A set of S vertices U must have many common neighbours (e.g., > Q/2 for large Q) if it has more than C common neighbours (where C is from the lemma).
    • Demonstrated that the likelihood of a set U having more common neighbours than C is extremely low using the moment bound and the Markov inequality.
    • Defined "Bad" as having more common neighbours than C, indicating that there should be very few bad sets.
    • To create a new graph G', the last step is comparable to randomised graph constructions: remove one vertex from each bad set.

    By construction, G' is K S, C+1 free (no set of S vertices has more than C common neighbours). G' still has many edges, confirmed by the expected edges less the edges eliminated from bad sets.

    G' is KST-free for sufficiently large T (T=C+1) and has a maximum of 2N vertices.

    Final Thoughts [45:40]

    The Kovari-Shuron bound for T significantly larger than S is matched by two distinct algebraic constructions of KST-free graphs with many edges. The general conjecture remains a significant open problem, but these constructions show that the Kovari-Shuron theorem is tight up to a constant factor.

    • Looking for additional constructions and perhaps fusing algebraic or other concepts are future directions.

    Next Steps [47:35]

    Further implications of these constructions, related solved and open conjectures, and expanding the analysis beyond KST to other bipartite graphs will all be covered in the upcoming lecture.