4. Forbidding a subgraph III: algebraic constructions

TL;DR

Randomized algebraic techniques are used to construct Kst-free graphs with a high number of edges.

Transcript

YUFEI ZHAO: Last time, we started discussing the extremal problem for bipartide graphs. And in particular, we saw the Kovari-Sos-Turan theorem, which tells us that if you forbid your graph from having a complete bipartide graph, Kst, then you have this upper bound on the number of edges in your graph. So we gave a proof. It was fairly short, used t... Read More

Key Insights

• 📈 The Kovari-Sos-Turan theorem provides an upper bound on the number of edges in a graph that avoids a complete bipartite graph Kst.
• 👷 Two constructions are presented, one using algebraic geometric ideas and the other using randomized algebraic techniques.
• 🤗 The extremal number for Kst free graphs is a major open problem, with the conjecture that the bound is tight up to constant factors.
• 👷 Randomized algebraic techniques involve choosing random polynomials to construct graphs, while algebraic geometric techniques involve constructing graphs based on geometric properties of a projective plane.
• 👷 The number of common neighbors in randomized algebraic constructions can be analyzed using moments and Markov's inequality. The distribution of common neighbors is highly constrained due to algebraic geometric properties.

Questions & Answers

Q: What is the Kovari-Sos-Turan theorem and how does it relate to the extremal number for Kst free graphs?

The Kovari-Sos-Turan theorem provides an upper bound on the number of edges in a graph that avoids a complete bipartite graph Kst. The extremal number for Kst free graphs refers to the maximum number of edges in a Kst-free graph.

Q: What are the two constructions presented in the content?

The first construction uses algebraic geometric ideas and involves the point-line incidence graph of a projective plane. The second construction uses randomized algebraic techniques and involves random polynomials to construct a bipartite graph.

Q: What is the major open problem related to the extremal number for Kst free graphs?

The major open problem is determining the tightness of the upper bound for the extremal number. It is conjectured that the bound is tight up to constant factors.

Q: How does the second construction using randomized algebraic techniques differ from the first construction?

The second construction uses random polynomials to construct a bipartite graph, while the first construction uses the point-line incidence graph of a projective plane. The randomized algebraic techniques in the second construction involve choosing a random polynomial and evaluating it on pairs of vertices to determine the edges in the graph.

Summary & Key Takeaways

• The Kovari-Sos-Turan theorem provides an upper bound on the number of edges in a graph that avoids a complete bipartite graph Kst.

• The extremal number for Kst free graphs is a major open problem, and two constructions are presented that achieve the upper bound for certain values of s and t.

• The first construction uses algebraic geometric ideas and involves the point-line incidence graph of a projective plane.

• The second construction uses randomized algebraic techniques and involves random polynomials to construct a bipartite graph.