Recent progress on the Erdos-Hajnal Conjecture
组织者
本杰明·苏达科夫
演讲者
Alexander Scott
时间
2024年04月30日 17:05 至 18:15
地点
Online
线上
Zoom 787 662 9899
(BIMSA)
摘要
A typical graph contains cliques and independent sets of no more than logarithmic size. The Erdos-Hajnal Conjecture asserts that if we forbid some induced subgraph H then we can do much better: the conjecture claims that there is some c=c(H)>0 such that every H-free graph G contains a clique or independent set of size at least |G|^c. The conjecture looks far out of reach, and is only known for a small family of graphs. We will discuss some recent progress. Joint work with Tung Nguyen and Paul Seymour.