Article in volume
Authors:
Title:
High girth hypergraphs with unavoidable monochromatic or rainbow edges
PDFSource:
Discussiones Mathematicae Graph Theory 42(2) (2022) 471-484
Received: 2019-07-12 , Revised: 2019-11-29 , Accepted: 2019-11-29 , Available online: 2020-01-16 , 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"odl [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\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
References:
- 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 - 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 - 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.
- P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959) 34–38.
https://doi.org/10.4153/CJM-1959-003-9 - 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 - 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.
- 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 - 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 - A. Karrer, Colorability of Uniform Hypergraphs without Monochromatic and Rainbow Edges, Master Thesis (Moldova State University, 1997).
- 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 - 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 - I. Kříž, A hypergraph-free construction of highly chromatic graphs without short cycles, Combinatorica 9 (1989) 227–229.
https://doi.org/10.1007/BF02124683 - G. Kun, Constraints, MMSNP and expander relational structures, Combinatorica 33 (2013) 335–347.
https://doi.org/10.1007/s00493-013-2405-4 - 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 - L. Lovász, On chromatic number of finite set-systems, Acta Math. Hungar. 19 (1968) 59–67.
https://doi.org/10.1007/BF01894680 - V. Müller, On colorable critical and uniquely colorable critical graphs, in: Recent Advances in Graph Theory, M. Fiedler (Ed(s)), (Academia, Prague 1975).
- 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 - 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 - 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 - 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 - 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 - 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 - V. Voloshin, Coloring Mixed Hypergraphs: Theory, Algorithms, and Applications (AMS, Providence, 2002).
https://doi.org/10.1090/fim/017
Close