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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Downloads (Pure)

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 Kn(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)(χ(H) − 1) + σ(H), where σ(H) stands for the minimum size of a colour class over all proper χ(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(Pn, H)/n for a pair (Pn, 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 χ(H). We complement these negative results with a positive one, determining the Ramsey number asymptotically for pairs (Pn, H) when H belongs to a certain family of hypergraphs.
Original languageEnglish
Title of host publicationEUROCOMB’23
PublisherMasaryk University Press
Pages1-7
Number of pages7
DOIs
Publication statusPublished - 28 Aug 2023
EventEuropean Conference on Combinatorics, Graph Theory and Applications - Charles University, Faculty of Mathematics and Physics, Prague, Czech Republic
Duration: 28 Aug 20231 Sept 2023
https://iuuk.mff.cuni.cz/events/conferences/eurocomb23/

Publication series

NameEuropean Conference on Combinatorics, Graph Theory and Applications
PublisherMasaryk University Press
Number12
ISSN (Electronic)2788-3116

Conference

ConferenceEuropean Conference on Combinatorics, Graph Theory and Applications
Abbreviated titleEUROCOMB'23
Country/TerritoryCzech Republic
CityPrague
Period28/08/231/09/23
Internet address

Fingerprint

Dive into the research topics of 'Tight path, what is it (Ramsey-) good for? Absolutely (almost) nothing!'. Together they form a unique fingerprint.

Cite this