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

TL;DR

Turán's theorem gives the maximum number of edges in a graph without a specific subgraph, and the extremal number of a graph is determined by its chromatic number.

Transcript

YUFEI ZHAO: So the first topic that I want to discuss in this course is extremal graph theory. And in particular, there is a whole class of problems which have to do with what happens if you forbid a specific subgraph. Forbid a specific subgraph. And I ask you, what's the maximum number of edges that can appear in your graph? In particular, and thi... Read More

Key Insights

• 🦔 Turán's theorem gives a precise answer to the maximum number of edges in a graph without a specific subgraph.
• #️⃣ The chromatic number of a graph influences the extremal number.

Questions & Answers

Q: What is Turán's theorem?

Turán's theorem provides the maximum number of edges in a graph without a specific subgraph, such as a triangle or a clique.

Q: How does the chromatic number of a graph affect its extremal number?

The chromatic number of a graph determines the extremal number. For example, the extremal number for a graph without a triangle is equal to the number of edges in a complete bipartite graph, and the extremal number for a graph without a tetrahedron is determined by the chromatic number minus one.

Q: Are there any known examples where the extremal number is not determined by the chromatic number?

Yes, for bipartite graphs, the Erdos-Stone-Simonovits theorem provides an upper bound on the extremal number, but the exact asymptotics are not known for most cases.

Q: What are some open problems in extremal graph theory?

One open problem is determining the extremal number of 3-uniform hypergraphs. Another open problem is the Zarankiewicz problem, which involves finding the extremal number of complete bipartite graphs.

Summary & Key Takeaways

• Extremal graph theory involves studying the maximum number of edges that can appear in a graph when a specific subgraph is forbidden.

• Turán's theorem states that the extremal number for a graph without a triangle is the number of edges in a complete bipartite graph.

• The extremal number of a graph is influenced by its chromatic number, which is the minimum number of colors needed to properly color the graph.