Uniform hypergraphs with many edge‐colorings avoiding a fixed rainbow expanded complete graph. Issue 1 (31st May 2021)

• Record Type: Journal Article
• Authors: Contiero, Lucas de Oliveira; Hoppen, Carlos; Lefmann, Hanno; Odermann, Knut
• Is Part Of: Journal of graph theory. Volume 98:Issue 1(2021)
• Page Start: 141
• Page End: 173
• Publication Date: 2021-05-31
• Subjects: edge‐coloring -- Erdős–Rothschild problem -- linear hypergraph -- Turán problem -- stability; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22686
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: For fixed positive integers r and k, and a fixed k ‐uniform hypergraph F, we look for n ‐vertex hypergraphs that admit the maximum number of r ‐edge‐colorings with the property that there is no copy of F for which all hyperedges are assigned different colors. We consider F = H ℓ + 1 ( k ), the k ‐uniform expanded complete graph, and we prove that the Turán hypergraph T ℓ ( k ) ( n ), the balanced ℓ ‐partite k ‐uniform hypergraph on n vertices, is the only extremal configuration for any r ≥ r 0 ( k, ℓ ) and large n .