Ramsey numbers of cliques versus monotone paths

DOI10.1016/J.EJC.2024.103922MaRDI QIDQ6201899zbMATH OpenWikidataFDO

Authors Dhruv Mubayi, Andrew Suk

Publication date 26 March 2024

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

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)

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.

Recommendations

• Ramsey problems for monotone paths in graphs and hypergraphs
• Ramsey numbers and monotone colorings
• scientific article; zbMATH DE number 398964
• A strengthening of the Erdős-Szekeres theorem
• Variants of the Erdős-Szekeres and Erdős-Hajnal Ramsey problems

Cites work

• scientific article; zbMATH DE number 795114 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• Diagonal Ramsey via effective quasirandomness
• Erdős-Szekeres-type theorems for monotone paths and convex bodies
• Off-diagonal hypergraph Ramsey numbers
• Ordered Ramsey numbers
• Partition relations for cardinal numbers
• Ramsey numbers of ordered graphs
• Some remarks on the theory of graphs
• Turan's theorem for k-graphs
• Variants of the Erdős-Szekeres and Erdős-Hajnal Ramsey problems

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)