17. Graph limits IV: inequalities between subgraph densities

TL;DR

Graph homomorphism inequalities, such as Turan's theorem and Sidorenko's conjecture, have been extensively studied in extremal graph theory. They are often decidable, but some open problems remain.

Transcript

PROFESSOR: We spent the last few lectures developing the theory of graph limits. And one of the motivations I gave at the beginning of the lecture on graph limits was that there were certain graph inequalities. Specifically, if I tell you that your graph has edge density one half, what's the minimum possible C4 density? So for those kinds of proble... Read More

Key Insights

• 📈 Graph homomorphism inequalities, such as Turan's theorem and Sidorenko's conjecture, are important topics in extremal graph theory.
• 👍 Theorems like Turan's theorem and Sidorenko's conjecture can be proven using graph limits and graphons as a mathematical framework.
• 📈 The decidability of graph homomorphism inequalities is dependent on the specific inequality and the constraints imposed.

Questions & Answers

Q: What is Turan's theorem?

Turan's theorem states that if the (r+1)-clique density is zero, then the K2 density is at most 1-r.

Q: What is Sidorenko's conjecture?

Sidorenko's conjecture states that for a bipartite graph H, the H density in a graph G is at least the edge density raised to the power of the number of edges of H.

Q: Are these graph homomorphism inequalities decidable?

Generally, graph homomorphism inequalities are undecidable. However, if an epsilon error is allowed, there exists an algorithm to decide whether the inequality is true up to an epsilon error.

Q: What is the current status of Sidorenko's conjecture?

Sidorenko's conjecture is still an open problem. There are no known counterexamples, but it has not been proven for all cases.

Summary & Key Takeaways

• Graph homomorphism inequalities, such as Turan's theorem and Sidorenko's conjecture, are important topics in extremal graph theory.

• Turan's theorem states that if the (r+1)-clique density is zero, then the K2 density is at most 1-r.

• Sidorenko's conjecture states that for a bipartite graph H, the H density in a graph G is at least the edge density raised to the power of the number of edges of H.

• These inequalities have been proven for certain cases but are still open problems for others.