Old and new applications of the Combinatorial Nullstellensatz in geometry
Károlyi GyulaKombinatorika szeminárium
on 11/30/23
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.
