×

On the cover Ramsey number of Berge hypergraphs. (English) Zbl 1443.05122

Summary: For a fixed set of positive integers \(R\), we say \(\mathcal{H}\) is an \(R\)-uniform hypergraph, or \(R\)-graph, if the cardinality of each edge belongs to \(R\). An \(R\)-graph \(\mathcal{H}\) is covering if every vertex pair of \(\mathcal{H}\) is contained in some hyperedge. For a graph \(G = (V, E)\), a hypergraph \(\mathcal{H}\) is called a Berge-\(G\), denoted by \(BG\), if there is an injection \(i : V(G) \to V(\mathcal{H})\) and a bijection \(f : E (G) \to E (\mathcal{H})\) such that for all \(e = uv \in E (G)\), we have \(\{i(u ), i(v)\} \subseteq f(e)\). In this note, we define a new type of Ramsey number, namely the cover Ramsey number, denoted as \(\hat{R}^R (BG_1, BG_2)\), as the smallest integer \(n_0\) such that for every covering \(R\)-uniform hypergraph \(\mathcal{H}\) on \(n \geq n_0\) vertices and every 2-edge-coloring (blue and red) of \(\mathcal{H}\) , there is either a blue Berge-\(G_1\) or a red Berge-\(G_2\) subhypergraph. We show that for every \(k \geq 2\), there exists some \(c_k\) such that for any finite graphs \(G_1\) and \(G_2, R (G_1, G_2 ) \leq \hat{R}^{[k]} (BG_1, BG_2) \leq c_k \cdot R (G_1, G_2)^3\). Moreover, we show that for each positive integer \(d\) and \(k\), there exists a constant \(C = C (d, k)\) such that if \(G\) is a graph on \(n\) vertices with maximum degree at most \(d\), then \(\hat{R}^{[k]} (BG, BG) \leq C n\).

MSC:

05C55 Generalized Ramsey theory
05D10 Ramsey theory
05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Axenovich, M.; Gyárfás, A., A note on Ramsey numbers for Berge-G hypergraphs, Discrete Math., 342, 5, 1245-1252 (2019) · Zbl 1407.05168
[2] Chang, Y., The existence of resolvable BIBD with \(k\) even and \(\lambda = 1\), Discrete Math., 218, 1-3, 9-23 (2000) · Zbl 0949.05007
[3] Chvátal, V.; Rödl, V.; Szemerédi, E.; Trotter, W. T., The Ramsey number of a graph with bounded maximum degree, J. Combin. Theory Ser. B, 34, 239-243 (1983) · Zbl 0547.05044
[4] Davoodi, A.; Győri, E.; Methuku, A.; Tompkins, C., An Erdős-Gallai type theorem for hypergraphs, European J. Combin., 69, 159-162 (2018) · Zbl 1376.05099
[5] Erdős, P.; Lovász, L., Problems and results on \(3\)-chromatic hypergraphs and some related questions, (Hajnal, A.; Rado, R.; Sós, V. T., Infinite and Finite Sets, Vol. II. Infinite and Finite Sets, Vol. II, Colloq., Keszthely, 1973; dedicated to P. Erdős on his \(60\) th birthday (1975), North-Holland), 609-627 · Zbl 0315.05117
[6] Ergemlidze, B.; Győri, E.; Methuku, A.; Salia, N.; Tompkins, C.; Zamora, O., Avoiding long Berge cycles, the missing cases \(k = r + 1\) and \(k = r + 2\), Combin. Probab. Comput., 1-13 (2019)
[7] Z. Füredi, A. Kostochka, R. Luo, Avoiding long Berge cycles II, exact bounds for all \(n\), arXiv:1807.06119. · Zbl 1416.05157
[8] Füredi, Z.; Kostochka, A.; Luo, R., Avoiding long Berge cycles, J. Combin. Theory Ser. B, 137, 55-64 (2019) · Zbl 1416.05157
[9] D. Gerbner, On Berge-Ramsey problems, arXiv:1906.02465. · Zbl 1441.05219
[10] Gerbner, D.; Methuku, A.; Omidi, G.; Vizer, M., Ramsey problems for Berge hypergraphs, SIAM J. Discrete Math., 34, 1, 351-369 (2020) · Zbl 1432.05066
[11] Gerbner, D.; Methuku, A.; Palmer, C., General lemmas for Berge-Turán hypergraph problems, European J. Combin., 86, Article 103082 pp. (2020) · Zbl 1437.05172
[12] Gerbner, D.; Palmer, C., Extremal results for Berge-hypergraphs, SIAM J. Discrete Math., 31, 4, 2314-2327 (2017) · Zbl 1372.05106
[13] D. Grósz, A. Methuku, C. Tompkins, Uniformity thresholds for the asymptotic size of extremal Berge-F-free hypergraphs, arXiv:1803.01953. · Zbl 1378.05145
[14] Győri, E.; Katona, G. Y.; Lemons, N., Hypergraph extensions of the Erdős-Gallai theorem, European J. Combin., 58, 238-246 (2016) · Zbl 1343.05113
[15] Győri, E.; Lemons, N., 3-uniform hypergraphs avoiding a given odd cycle, Combinatorica, 32, 2, 187-203 (2012) · Zbl 1299.05247
[16] Győri, E.; Lemons, N., Hypergraphs with no cycle of a given length, Combin. Probab. Comput., 21, 1-2, 193-201 (2012) · Zbl 1241.05101
[17] E. Győri, N. Lemons, N. Salia, O. Zamora, The Structure of Hypergraphs without long Berge cycles, arXiv:1812.10737.
[18] Hanani, H.; Ray-Chaudhuri, D. K.; Wilson, R. M., On resolvable designs, Discrete Math., 3, 343-357 (1972) · Zbl 0263.05016
[19] Kirkman, T. P., On a problem in combinations, Cambridge Dublin Math. J., 2, 191-204 (1847)
[20] Komlós, J.; Simonovits, M., Szemerédi’s regularity lemma and its applications in graph theory, (Combinatorics, Paul Erdos is eighty, Vol. 2. Combinatorics, Paul Erdos is eighty, Vol. 2, Keszthely, 1993. Combinatorics, Paul Erdos is eighty, Vol. 2. Combinatorics, Paul Erdos is eighty, Vol. 2, Keszthely, 1993, Bolyai Soc. Math. Stud., vol. 2 (1996), János Bolyai Math. Soc.: János Bolyai Math. Soc. Budapest), 295-352 · Zbl 0851.05065
[21] Kostochka, A.; Luo, R., On r-uniform hypergraphs with circumference less than \(r\), Disc. Appl. Math., 276, 69-91 (2020) · Zbl 1435.05153
[22] Palmer, C.; Tait, M.; Timmons, C.; Wagner, A. Z., Turán numbers for Berge-hypergraphs and related extremal problems, Discrete Math., 342, 6, 1553-1563 (2019) · Zbl 1414.05212
[23] D. Pálvölgyi, Exponential lower bound for Berge-Ramsey problems, arXiv:1906.04288.
[24] Ray-Chaudhuri, D. K.; Wilson, R. M., Solution of Kirkman’s schoolgirl problem, (Proc. Symp. in Pure Mathematics, Vol. 19 (1971), Am. Math. Soc.: Am. Math. Soc. Providence, R-l.), 187-203 · Zbl 0248.05009
[25] Ray-Chaudhuri, D. K.; Wilson, R. M., The existence of resolvable block designs, (Srivastava, J. N.; Harary, F.; Rao, C. R.; Rota, G.-C.; Shrikhande, S. S., Survey of Combinatorial Theory (1973), North-Holland, American Elsevier: North-Holland, American Elsevier Amsterdam, New York), 361-375 · Zbl 0274.05010
[26] Salia, N.; Tompkins, C.; Wang, Z.; Zamora, O., Ramsey numbers of Berge-hypergraphs and related structures, Electron. J. Comb., 26, 4, 25 (2019), Paper 4.40 · Zbl 1428.05215
[27] Spencer, J., Asymptotic lower bounds for Ramsey functions, Discrete Math., 20, 69-76 (1977) · Zbl 0375.05033
[28] Szemerédi, E., Regular partitions of graphs, (Bermond, J. C.; Fournier, J. C.; das Vergnas, M.; Sotteau, D., Proc. Colloque Inter (1978), CNRS) · Zbl 0413.05055
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.