TY - JOUR
T1 - Large monochromatic components in expansive hypergraphs
AU - Bal, Deepak
AU - DeBiasio, Louis
N1 - Publisher Copyright:
© The Author(s), 2024.
PY - 2024
Y1 - 2024
N2 - A result of Gyárfás [12] exactly determines the size of a largest monochromatic component in an arbitrary r-colouring of the complete k-uniform hypergraph Knk when k ≥ 2 and k ∈ {r − 1, r}. We prove a result which says that if one replaces Knk in Gyárfás’ theorem by any ‘expansive’ k-uniform hypergraph on n vertices (that is, a k-uniform hypergraph G on n vertices in which e(V1, ⋯, Vk) > 0 for all disjoint sets V1, ⋯, Vk ⊆ V(G) with |Vi| > α for all i ∈ [k]), then one gets a largest monochromatic component of essentially the same size (within a small error term depending on r and α). As corollaries we recover a number of known results about large monochromatic components in random hypergraphs and random Steiner triple systems, often with drastically improved bounds on the error terms. Gyárfás’ result is equivalent to the dual problem of determining the smallest possible maximum degree of an arbitrary r-partite r-uniform hypergraph H with n edges in which every set of k edges has a common intersection. In this language, our result says that if one replaces the condition that every set of k edges has a common intersection with the condition that for every collection of k disjoint sets E1, ⋯, Ek ⊆ E(H) with |Ei| > α, there exists (e1, ⋯, ek) ∈ E1 × · · · × Ek such that e1 ∩ · · · ∩ ek /= ∅, then the smallest possible maximum degree of H is essentially the same (within a small error term depending on r and α). We prove our results in this dual setting.
AB - A result of Gyárfás [12] exactly determines the size of a largest monochromatic component in an arbitrary r-colouring of the complete k-uniform hypergraph Knk when k ≥ 2 and k ∈ {r − 1, r}. We prove a result which says that if one replaces Knk in Gyárfás’ theorem by any ‘expansive’ k-uniform hypergraph on n vertices (that is, a k-uniform hypergraph G on n vertices in which e(V1, ⋯, Vk) > 0 for all disjoint sets V1, ⋯, Vk ⊆ V(G) with |Vi| > α for all i ∈ [k]), then one gets a largest monochromatic component of essentially the same size (within a small error term depending on r and α). As corollaries we recover a number of known results about large monochromatic components in random hypergraphs and random Steiner triple systems, often with drastically improved bounds on the error terms. Gyárfás’ result is equivalent to the dual problem of determining the smallest possible maximum degree of an arbitrary r-partite r-uniform hypergraph H with n edges in which every set of k edges has a common intersection. In this language, our result says that if one replaces the condition that every set of k edges has a common intersection with the condition that for every collection of k disjoint sets E1, ⋯, Ek ⊆ E(H) with |Ei| > α, there exists (e1, ⋯, ek) ∈ E1 × · · · × Ek such that e1 ∩ · · · ∩ ek /= ∅, then the smallest possible maximum degree of H is essentially the same (within a small error term depending on r and α). We prove our results in this dual setting.
KW - colourings
KW - hypergraphs
KW - Monochromatic components
UR - http://www.scopus.com/inward/record.url?scp=85186687881&partnerID=8YFLogxK
U2 - 10.1017/S096354832400004X
DO - 10.1017/S096354832400004X
M3 - Article
AN - SCOPUS:85186687881
SN - 0963-5483
JO - Combinatorics Probability and Computing
JF - Combinatorics Probability and Computing
ER -