2-Colorings of Hypergraphs with Large Girth

Yu. A. Demidovich

Matematičeskie zametki, Tome 108 (2020) no. 2, pp. 200-214.

Résumé

A hypergraph $H=(V,E)$ has property $B_k$ if there exists a 2-coloring of the set $V$ such that each edge contains at least $k$ vertices of each color. We let $m_{k,g}(n)$ and $m_{k,b}(n)$, respectively, denote the least number of edges of an $n$-homogeneous hypergraph without property $B_k$ which contains either no cycles of length at least $g$ or no two edges intersecting in more than $b$ vertices. In the paper, upper bounds for these quantities are given. As a consequence, we obtain results for $m^{*}_k(n)$, i.e., for the least number of edges of an $n$-homogeneous simple hypergraph without property $B_k$. Let $\Delta(H)$ be the maximal degree of vertices of a hypergraph $H$. By $\Delta_k(n,g)$ we denote the minimal degree $\Delta$ such that there exists an $n$-homogeneous hypergraph $H$ with maximal degree $\Delta$ and girth at least $g$ but without property $B_k$. In the paper, an upper bound for $\Delta_k(n,g)$ is obtained.

Détail

Keywords: hypergraphs, girth, property $B$, simple hypergraphs.

Bibliographie

[1] P. Erdős, A. Hajnal, “On a property of families of sets”, Acta Math. Acad. Sci. Hungar., 12:1-2 (1961), 87–123 | MR | Zbl

[2] P. Erdős, “On a combinatorial problem”, Nordisk Mat. Tidskr., 11 (1963), 5–10 | MR | Zbl

[3] P. Erdős, “On a combinatorial problem. II”, Acta Math. Acad. Sci. Hungar., 15:3-4 (1964), 445–447 | MR | Zbl

[4] A. V. Kostochka, “Color-critical graphs and hypergraphs with few edges: a survey”, More Sets, Graphs and Numbers, Bolyai Soc. Math. Stud., 15, Springer-Verlag, Berlin, 2006, 175–197 | MR | Zbl

[5] A. M. Raigorodskii, D. A. Shabanov, “Zadacha Erdesha–Khainala o raskraskakh gipergrafov, ee obobscheniya i smezhnye problemy”, UMN, 66:5 (401) (2011), 109–182 | DOI | MR | Zbl

[6] J. Radhakrishnan, A. Srinivasan, “Improved bounds and algorithms for hypergraph 2-coloring”, Random Structures Algorithms, 16:1 (2000), 4–32 | MR | Zbl

[7] D. Cherkashin, J. Kozik, “A note on random greedy coloring of uniform hypergraphs”, Random Structures Algorithms, 47:3 (2015), 407–413 | DOI | MR | Zbl

[8] D. A. Shabanov, “Ob odnoi kombinatornoi zadache Erdesha”, Dokl. AN, 396:2 (2004), 166–169 | MR | Zbl

[9] D. A. Shabanov, “Ekstremalnye zadachi dlya raskrasok ravnomernykh gipergrafov”, Izv. RAN. Ser. matem., 71:6 (2007), 183–222 | DOI | MR | Zbl

[10] S. M. Teplyakov, “Verkhnyaya otsenka v zadache Erdesha–Khainala o raskraske gipergrafa”, Matem. zametki, 93:1 (2013), 148–151 | DOI | MR | Zbl

[11] D. A. Shabanov, “Randomizirovannye algoritmy raskrasok gipergrafov”, Matem. sb., 199:7 (2008), 139–160 | DOI | MR | Zbl

[12] A. P. Rozovskaya, “Ekstremalnye kombinatornye zadachi dlya dvukhtsvetnykh raskrasok gipergrafov”, Matem. zametki, 90:4 (2011), 584–598 | DOI | MR | Zbl

[13] A. P. Rozovskaya, “O dvukhtsvetnykh raskraskakh obschego vida dlya ravnomernykh gipergrafov”, Dokl. AN, 429:3 (2009), 309–311 | Zbl

[14] Yu. A. Demidovich, On Some Generalizations of the Property $B$-Problem of an $n$-Uniform Hypergraph, arXiv: 1903.11708v1

[15] P. Erdős, L. Lovász, “Problems and results on 3-chromatic hypergraphs and some related questions”, Infinite and Finite Sets, Vol. II, Colloq. Math. Soc. János. Bolyai, 10, North-Holland, Amsterdam, 1975, 609–627 | MR

[16] Z. Szabó, “An application of Lovász Local Lemma – a new lower bound for the van der Waerden number”, Random Structures Algorithms, 1:3 (1990), 343–360 | DOI | MR | Zbl

[17] A. V. Kostochka, M. Kumbhat, “Coloring uniform hypergraphs with few edges”, Random Structures Algorithms, 35:3 (2009), 348–368 | DOI | MR | Zbl

[18] J. Kozik, D. Shabanov, “Improved algorithms for colorings of simple hypergraphs and applications”, J. Combin. Theory Ser. B, 116 (2016), 312–332 | DOI | MR | Zbl

[19] A. V. Kostochka, V. Rődl, “Constructions of sparse uniform hypergraphs with high chromatic number”, Random Structures and Algorithms, 36:1 (2010), 46–56 | DOI | MR | Zbl

[20] M. Akhmejanova, D. Shabanov, “Coloring hypergraphs with bounded cardinalities of edge intersections”, Discrete Math., 343:4 (2020), 111692 | DOI | MR | Zbl

[21] N. N. Kuzjurin, “On the difference between asymptotically good packings and coverings”, European J. Combin, 16:1 (1995), 35–40 | DOI | MR | Zbl

[22] N. Sauer, “On the existence of regular n-graphs with given girth”, J. Combin. Theory, 9 (1970), 144–147 | DOI | MR | Zbl

[23] A. Semenov, D. Shabanov, “On the weak chromatic number of random hypergraphs”, Discrete Appl. Math., 276 (2019), 134–154. | DOI | MR

[24] A. C. Semenov, “Dvukhtsvetnye raskraski sluchainogo gipergrafa”, Teoriya veroyatn. i ee primen., 64:1 (2019), 75–97 | DOI | MR | Zbl

[25] A. Kupavskii, D. Shabanov, “Colourings of uniform hypergraphs with large girth and applications”, Combin. Probab. Comput., 27:2 (2018), 245–273 | MR | Zbl

[26] D. Cherkashin, F. Petrov, “On small $n$-uniform hypergraphs with positive discrepancy”, J. Combin. Theory Ser. B, 139 (2019), 353–359 | MR | Zbl

[27] J. Balogh, D. Cherkashin, S. Kiselev, “Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs”, European J. Combin., 79 (2019), 228–236 | MR | Zbl

[28] A. M. Raigorodskii, D. D. Cherkashin, “Ekstremalnye zadachi v raskraskakh gipergrafov”, UMN, 75:1 (451) (2020), 95–154 | DOI | Zbl