The Combinatorial Nullstellensatz and some applications to additive combinatorics
Maga PéterKombinatorika szeminárium
on 2/24/22
Popielarz, Sahasrabudhe and Snyder in 2018 proved that maximal
Kr+1-free graphs with
(1−1r)n22−o(nr+1r) edges contain a
complete r-partite subgraph on n−o(n) vertices. This was very
recently extended to odd cycles in place of K3 by Wang, Wang, Yang
and Yuan. We further extend it to some other 3-chromatic graphs, and
obtain some other stability results along the way.