High Girth Hypergraphs with Unavoidable Monochromatic or Rainbow Edges
A classical result of Erdős and Hajnal claims that for any integers k, r, g ≥ 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 monoc...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2022-05-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2291 |
| _version_ | 1797713125339824128 |
|---|---|
| author | Axenovich Maria Karrer Annette |
| author_facet | Axenovich Maria Karrer Annette |
| author_sort | Axenovich Maria |
| collection | DOAJ |
| description | A classical result of Erdős and Hajnal claims that for any integers k, r, g ≥ 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 [19] 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 ≥ 2 using probabilistic and explicit constructions. In this paper, we provide a slightly di erent 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. |
| first_indexed | 2024-03-12T07:32:25Z |
| format | Article |
| id | doaj.art-139655358c7a4fb580ac2e9093a2717a |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T07:32:25Z |
| publishDate | 2022-05-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-139655358c7a4fb580ac2e9093a2717a2023-09-02T21:43:04ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922022-05-0142247148410.7151/dmgt.2291High Girth Hypergraphs with Unavoidable Monochromatic or Rainbow EdgesAxenovich Maria0Karrer Annette1Karlsruhe Institute of TechnologyKarlsruhe Institute of TechnologyA classical result of Erdős and Hajnal claims that for any integers k, r, g ≥ 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 [19] 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 ≥ 2 using probabilistic and explicit constructions. In this paper, we provide a slightly di erent 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.https://doi.org/10.7151/dmgt.2291hypergraphchromatic numbermixed hypergraphbihyper-graphsmonochromaticrainbowgirthselective05c1505c3505c65 |
| spellingShingle | Axenovich Maria Karrer Annette High Girth Hypergraphs with Unavoidable Monochromatic or Rainbow Edges Discussiones Mathematicae Graph Theory hypergraph chromatic number mixed hypergraph bihyper-graphs monochromatic rainbow girth selective 05c15 05c35 05c65 |
| title | High Girth Hypergraphs with Unavoidable Monochromatic or Rainbow Edges |
| title_full | High Girth Hypergraphs with Unavoidable Monochromatic or Rainbow Edges |
| title_fullStr | High Girth Hypergraphs with Unavoidable Monochromatic or Rainbow Edges |
| title_full_unstemmed | High Girth Hypergraphs with Unavoidable Monochromatic or Rainbow Edges |
| title_short | High Girth Hypergraphs with Unavoidable Monochromatic or Rainbow Edges |
| title_sort | high girth hypergraphs with unavoidable monochromatic or rainbow edges |
| topic | hypergraph chromatic number mixed hypergraph bihyper-graphs monochromatic rainbow girth selective 05c15 05c35 05c65 |
| url | https://doi.org/10.7151/dmgt.2291 |
| work_keys_str_mv | AT axenovichmaria highgirthhypergraphswithunavoidablemonochromaticorrainbowedges AT karrerannette highgirthhypergraphswithunavoidablemonochromaticorrainbowedges |