Füredi Zoltán: Monochromatic components in almost complete graphs (in Hungarian)

Description of video

Date: 4/29/21
Speaker :Füredi Zoltán

Keywords

    Gyarfas proved that every coloring of the edges of K_n with  t+1
    colors contains a monochromatic connected component of size at least
    n/t. Later, Gyarfas and Sarkozy asked for which values of
    \gamma=\gamma(t)  does the following strengthening for {almost}
    complete graphs hold: if G is an n-vertex graph with minimum degree at
    least  (1-\gamma)n, then every (t+1)-edge coloring of  G  contains a
    monochromatic component of size at least  n/t. We show  \gamma=
    1/(6t^3)  suffices, improving the results of DeBiasio, Krueger, and
    Sarkozy as well.

    We also point out connections to (t+1)-partite hypergraphs, and
    regular intersecting families.

    The new results are joint with Ruth Luo.

    Downloads