Large monochromatic components in hypergraphs with large minimum codegree

Deepak Bal, Louis DeBiasio

Research output: Contribution to journalArticlepeer-review

Abstract

A result of Gyárfás says that for every 3-coloring of the edges of the complete graph (Formula presented.), there is a monochromatic component of order at least (Formula presented.), and this is best possible when 4 divides (Formula presented.). Furthermore, for all (Formula presented.) and every (Formula presented.) -coloring of the edges of the complete (Formula presented.) -uniform hypergraph (Formula presented.), there is a monochromatic component of order at least (Formula presented.) and this is best possible for all (Formula presented.). 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 (Formula presented.) is replaced by any graph on (Formula presented.) vertices with minimum degree at least (Formula presented.); furthermore, this bound on the minimum degree is best possible. We prove a strengthening of the (Formula presented.) case in the result above which says that the same conclusion holds if (Formula presented.) is replaced by any (Formula presented.) -uniform hypergraph on (Formula presented.) vertices with minimum (Formula presented.) -degree at least (Formula presented.); furthermore, this bound on the (Formula presented.) -degree is best possible.

Original languageEnglish
JournalJournal of Graph Theory
DOIs
StateAccepted/In press - 2023

Keywords

  • hypergraphs
  • monochromatic components
  • Ramsey

Fingerprint

Dive into the research topics of 'Large monochromatic components in hypergraphs with large minimum codegree'. Together they form a unique fingerprint.

Cite this