Geodesic
High Girth Hypergraphs with Unavoidable Monochromatic or Rainbow Edges
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 471-484.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: hypergraph, chromatic number, mixed hypergraph, bihyper-graphs, monochromatic, rainbow, girth, selective 
@article{DMGT_2022_42_2_a8,
     author = {Axenovich, Maria and Karrer, Annette},
     title = {High {Girth} {Hypergraphs} with {Unavoidable} {Monochromatic} or {Rainbow} {Edges}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {471--484},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a8/}
}
TY  - JOUR
AU  - Axenovich, Maria
AU  - Karrer, Annette
TI  - High Girth Hypergraphs with Unavoidable Monochromatic or Rainbow Edges
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 471
EP  - 484
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a8/
LA  - en
ID  - DMGT_2022_42_2_a8
ER  - 
%0 Journal Article
%A Axenovich, Maria
%A Karrer, Annette
%T High Girth Hypergraphs with Unavoidable Monochromatic or Rainbow Edges
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 471-484
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a8/
%G en
%F DMGT_2022_42_2_a8
Axenovich, Maria; Karrer, Annette. High Girth Hypergraphs with Unavoidable Monochromatic or Rainbow Edges. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 471-484. http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a8/

[1] N. Alon, A. Kostochka, B. Reiniger, D. West and X. Zhu, Coloring, sparseness and girth, Israel J. Math. 214 (2016) 315–331. https://doi.org/10.1007/s11856-016-1361-2

[2] Y. Caro, J. Lauri and C. Zarb, Selective hypergraph colourings, Discrete Math. 339 (2016) 1232–1241. https://doi.org/10.1016/j.disc.2015.11.006

[3] D. Duffus, V. Rödl, B. Sands and N. Sauer, Chromatic numbers and homomorphisms of large girth hypergraphs, in: Topics in Discrete Mathematics, (Springer, 2006) 455–471.

[4] P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959) 34–38. https://doi.org/10.4153/CJM-1959-003-9

[5] P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Hungar. 17 (1966) 61–99. https://doi.org/10.1007/BF02020444

[6] P. Erdős and L. Lovász, Problems and results on 3 -chromatic hypergraphs and some related questions, in: Infinite and Finite Sets, (Keszthely, 1973), Colloq. Math. Soc. János Bolyai 10 (1975) 609–627.

[7] P. Erdős, J. Nešetřil and V. Rödl, Selectivity of hypergraphs, in: Finite and Infinite Sets, Vol. I (Eger, 1981), Colloq. Math. Soc. János Bolyai 37 (1984) 265–284. https://doi.org/10.1016/B978-0-444-86893-0.50020-6

[8] T. Feder and M.Y. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory, SIAM J. Comput. 28 (1998) 57–104. https://doi.org/10.1137/S0097539794266766

[9] A. Karrer, Colorability of Uniform Hypergraphs without Monochromatic and Rainbow Edges, Master Thesis (Moldova State University, 1997).

[10] A. Kostochka and J. Nešetřil, Properties of Descartes’ construction of triangle-free graphs with high chromatic number, Combin. Probab. Comput. 8 (1999) 467–472. https://doi.org/10.1017/S0963548399004022

[11] A. Kostochka and V. Rödl, Constructions of sparse uniform hypergraphs with high chromatic number, Random Structures Algorithms 36 (2010) 46–56. https://doi.org/10.1002/rsa.20293

[12] I. Kříž, A hypergraph-free construction of highly chromatic graphs without short cycles, Combinatorica 9 (1989) 227–229. https://doi.org/10.1007/BF02124683

[13] G. Kun, Constraints, MMSNP and expander relational structures, Combinatorica 33 (2013) 335–347. https://doi.org/10.1007/s00493-013-2405-4

[14] A. Kupavskii and D. Shabanov, Colourings of uniform hypergraphs with large girth and applications, Combin. Probab. Comput. 27 (2018) 245–273. https://doi.org/10.1017/S0963548317000475

[15] L. Lovász, On chromatic number of finite set-systems, Acta Math. Hungar. 19 (1968) 59–67. https://doi.org/10.1007/BF01894680

[16] V. Müller, On colorable critical and uniquely colorable critical graphs, in: Recent Advances in Graph Theory, M. Fiedler (Ed(s)), (Academia, Prague, 1975).

[17] V. Müller, On colorings of graphs without short cycles, Discrete Math. 26 (1979) 165–176. https://doi.org/10.1016/0012-365X(79)90121-3

[18] J. Nešetřil, A combinatorial classic—sparse graphs with high chromatic number, in: Erdős Centennial, (Springer, Berlin, Heidelberg, 2013) 383–407. https://doi.org/10.1007/978-3-642-39286-3_15

[19] J. Nešetřil and V. Rödl, Selective graphs and hypergraphs, Ann. Discrete Math. 3 (1978) 181–189. https://doi.org/10.1016/S0167-5060(08)70506-5

[20] J. Nešetřil and V. Rödl, On a probabilistic graph-theoretical method, Proc. Amer. Math. Soc. 72 (1978) 417–421. https://doi.org/10.1090/S0002-9939-1978-0507350-7

[21] A. Raigorodskii and D. Shabanov, The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems, Russian Math. Surveys 66 (2011) 933. https://doi.org/10.1070/RM2011v066n05ABEH004764

[22] N. Sauer, On the existence of regular n-graphs with given girth, J. Combin. Theory 9 (1970) 144–147. https://doi.org/10.1016/S0021-9800(70)80021-7

[23] V. Voloshin, Coloring Mixed Hypergraphs: Theory, Algorithms, and Applications (AMS, Providence, 2002). https://doi.org/10.1090/fim/017