Ramsey numbers of cliques versus monotone paths

DOI10.1016/J.EJC.2024.103922arXiv2303.16995WikidataQ130132401 ScholiaQ130132401MaRDI QIDQ6201899FDOQ6201899

Dhruv Mubayi, Andrew Suk

Publication date: 26 March 2024

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: One formulation of the Erdos-Szekeres monotone subsequence theorem states that for any red/blue coloring of the edge set of the complete graph on $1,2,ldots,N$, there exists a monochromatic red $s$-clique or a monochromatic blue increasing path $P_n$ with $n$ vertices, provided $N>(s-1)(n-1)$. %We had previously shown that a suitable generalization of this problem to quadruple systems is essentially equivalent to classical diagonal hypergraph Ramsey numbers. Here, we prove a similar statement as above in the off-diagonal case for triple systems, with the quasipolynomial bound $N>2^{c(logn{)}^{s-1}}$. For the $t$th power $P_n^t$ of the ordered increasing graph path with $n$ vertices, we prove a near linear bound $c,n(logn{)}^{s-2}$ which improves the previous bound that applied to a more general class of graphs than $P_n^t$ due to Conlon-Fox-Lee-Sudakov.

Full work available at URL: https://arxiv.org/abs/2303.16995

zbMATH Keywords

Erdős-Szekeres monotone subsequence theoremmonochromatic blue increasing path \(P_n\)monochromatic red \(s\)-clique

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cites Work

• Some remarks on the theory of graphs
• Title not available (Why is that?)
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• A decomposition theorem for partially ordered sets
• Turan's theorem for \(k\)-graphs
• Title not available (Why is that?)
• Partition relations for cardinal numbers
• Erdős-Szekeres-type theorems for monotone paths and convex bodies
• Off-diagonal hypergraph Ramsey numbers
• Variants of the Erdős-Szekeres and Erdős-Hajnal Ramsey problems
• Ordered Ramsey numbers
• Ramsey numbers of ordered graphs
• Diagonal Ramsey via effective quasirandomness

This page was built for publication: Ramsey numbers of cliques versus monotone paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201899)