DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

M. Axenovich and A. Karrer

Title:

High girth hypergraphs with unavoidable monochromatic or rainbow edges

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-07-12, Revised: 2019-11-27, Accepted: 2019-11-29, https://doi.org/10.7151/dmgt.2291

Abstract:

A classical result of Erdős and Hajnal claims that for any integers $k, r, g \geq 2$ there is an $r$-uniform hypergraph of girth at least $g$ with chromatic number at least $k$. This implies that there are sparse hypergraphs such that in any coloring of their vertices with at most $k-1$ colors there is a monochromatic hyperedge. When there is no restriction on the number of the colors used, one can easily avoid monochromatic hyperedges. Then, however, so-called rainbow or multicolored hyperedges might appear. Nešetřil and Rödl \cite{NR-sel} called hypergraphs such that in any vertex-coloring there is either a monochromatic or a rainbow hyperedge, selective. They showed an existence of selective $r$-uniform hypergraphs of girth $g$ for any integers $r, g\geq 2$ using probabilistic and explicit constructions. In this paper, we provide a slightly different construction of such hypergraphs and summarize the probabilistic approaches. The main building block of the construction, a part-rainbow-forced hypergraph, is of independent interest. This is an $r$-uniform $r$-partite hypergraph with a given girth such that in any vertex-coloring that is rainbow on each part, there is a rainbow hyperedge. We give a simple construction of such a hypergraph that does not use iterative amalgamation.

Keywords:

hypergraph, chromatic number, mixed hypergraph, bihypergraphs, monochromatic, rainbow, girth, selective

PDF
Close