Tight path, what is it (Ramsey-)good for? Absolutely (almost) nothing!

Simona Boyadzhiyska; Allan Lo

doi:10.5817/CZ.MUNI.EUROCOMB23-026

Tight path, what is it (Ramsey-)good for? Absolutely (almost) nothing!

EUROCOMB’23

Simona Boyadzhiyska Allan Lo

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-026

PDF

Abstract

Given a pair of $k$-uniform hypergraphs $(G,H)$, the Ramsey number of $(G,H)$, denoted by $R(G,H)$, is the smallest integer $n$ such that in every red/blue-colouring of the edges of $K_n^{(k)}$ there exists a red copy of $G$ or a blue copy of $H$. Burr showed that, for any pair of graphs $(G,H)$, where $G$ is large and connected, the Ramsey number $R(G,H)$ is bounded below by $(v(G)-1)(\chi(H)-1)+\sigma(H)$, where $\sigma(H)$ stands for the minimum size of a colour class over all proper $\chi(H)$-colourings of $H$. Together with Erdős, he then asked when this lower bound is attained, introducing the notion of Ramsey goodness and its systematic study. We say that $G$ is $H$-good if the Ramsey number of $(G,H)$ is equal to the general lower bound. Among other results, it was shown by Burr that, for any graph $H$, every sufficiently long path is $H$-good. Our goal is to explore the notion of Ramsey goodness in the setting of 3-uniform hypergraphs. Motivated by Burr‘s result concerning paths and a recent result of Balogh, Clemen, Skokan, and Wagner, we ask: what 3-graphs $H$ is a (long) tight path good for? We demonstrate that, in stark contrast to the graph case, long tight paths are generally not $H$-good for various types of 3-graphs $H$. Even more, we show that the ratio $R(P_n, H)/n$ for a pair $(P_n, H)$ consisting of a tight path on $n$ vertices and a 3-graph $H$ cannot in general be bounded above by any function depending only on $\chi(H)$. We complement these negative results with a positive one, determining the Ramsey number asymptotically for pairs $(P_n, H)$ when $H$ belongs to a certain family of hypergraphs.

Pages:
186–192

References

P. Allen, G. Brightwell, and J. Skokan. Ramsey-goodness - and otherwise. Combinatorica, 33:125-160, 2013.
https://doi.org/10.1007/s00493-013-2778-4

J. Balogh, F. C. Clemen, J. Skokan, and A. Z. Wagner. The Ramsey number of the Fano plane versus the tight path. Electron. J. Combin., 27(1):P1.60, 2020.
https://doi.org/10.37236/8374

S. Brandt. Expanding graphs and Ramsey numbers. Freie Univ., Fachbereich Mathematik und Informatik, 1996.

S. A. Burr. Ramsey numbers involving graphs with long suspended paths. J. London Math. Soc., 2(3):405-413, 1981.
https://doi.org/10.1112/jlms/s2-24.3.405

S. A. Burr and P. Erdős. Generalizations of a Ramsey-theoretic result of Chvátal. J. Graph Theory, 7(1):39-51, 1983.
https://doi.org/10.1002/jgt.3190070106

M. Campos, S. Griffiths, R. Morris, and J. Sahasrabudhe. An exponential improvement for diagonal Ramsey. arXiv:2303.09521, 2023.

V. Chvátal. Tree-complete graph Ramsey numbers. J. Graph Theory, 1(1):93, 1977.
https://doi.org/10.1002/jgt.3190010118

V. Chvátal and F. Harary. Generalized Ramsey theory for graphs. III. Small off-diagonal numbers. Pacific J. Math., 41(2): 335-345, 1972.
https://doi.org/10.2140/pjm.1972.41.335

D. Conlon, J. Fox, and B. Sudakov. Recent developments in graph Ramsey theory. In Surveys in combinatorics 2015, volume 424 of London Math. Soc. Lecture Note Ser., pages 49-118. Cambridge Univ. Press, Cambridge, 2015.
https://doi.org/10.1017/CBO9781316106853.003

P. Erdős. Some remarks on the theory of graphs. Bull. Amer. Math. Soc., 53:292-294, 1947.
https://doi.org/10.1090/S0002-9904-1947-08785-1

P. Erdős and G. Szekeres. A combinatorial problem in geometry. Compositio Math., 2:463-470, 1935.

P. Keevash and Y. Zhao. Codegree problems for projective geometries. J. Combin. Theory Ser. B, 97(6):919-928, 2007.
https://doi.org/10.1016/j.jctb.2007.01.004

D. Mubayi and A. Suk. A survey of hypergraph Ramsey problems. Discrete Math.

Appl., 165:405-428, 2020.

F. P. Ramsey. On a problem in formal logic. Proc. Lond. Math. Soc., 30:264-286, 1930.
https://doi.org/10.1112/plms/s2-30.1.264

Metrics