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.
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.