2023/01/14 by Bal, Deepak, DeBiasio, Louis
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2301.05806
A result of Gyárfás says that for every 3-coloring of the edges of the complete graph Kn, there is a monochromatic component of order at least (n)/(2), and this is best possible when 4 divides n. Furthermore, for all k≥ 3 and every (k+1)-coloring of the edges of the complete k-uniform hypergraph Knk, there is a monochromatic component of order at least (kn)/(k+1) and this is best possible for all n. Recently, Guggiari and Scott and independently Rahimi proved a strengthening of the graph case in the result above which says that the same conclusion holds if Kn is replaced by any graph on n vertices with minimum degree at least (5n)/(6)-1; furthermore, this bound on the minimum degree is best possible. We prove a strengthening of the k≥ 3 case in the result above which says that the same conclusion holds if Knk is replaced by any k-uniform hypergraph on n vertices with minimum (k-1)-degree at least (kn)/(k+1)-(k-1); furthermore, this bound on the (k-1)-degree is best possible.