Off-diagonal hypergraph Ramsey numbers

DOI10.1016/J.JCTB.2017.03.002zbMATH Open1362.05093arXiv1505.05767OpenAlexW2963947028MaRDI QIDQ2396897FDOQ2396897

Andrew Suk, Dhruv Mubayi

Publication date: 26 May 2017

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: The Ramsey number $r_k(s,n)$ is the minimum $N$ such that every red-blue coloring of the $k$-subsets of $1,ldots,N$ contains a red set of size $s$ or a blue set of size $n$, where a set is red (blue) if all of its $k$-subsets are red (blue). A $k$-uniform emph{tight path} of size $s$, denoted by $P_s$, is a set of $s$ vertices $v_1<cdots<v_s$ in $mathbbZ$, and all $s-k+1$ edges of the form $v_j,v_{j+1},ldots,v_{j+k-1}$. Let $r_k(P_s,n)$ be the minimum $N$ such that every red-blue coloring of the $k$-subsets of $1,ldots,N$ results in a red $P_s$ or a blue set of size $n$. The problem of estimating both $r_k(s,n)$ and $r_k(P_s,n)$ for $k=2$ goes back to the seminal work of Erdos and Szekeres from 1935, while the case $kge3$ was first investigated by Erdos and Rado in 1952. In this paper, we deduce a quantitative relationship between multicolor variants of $r_k(P_s,n)$ and $r_k(n,n)$. This yields several consequences including the following: (1) We determine the correct tower growth rate for both $r_k(s,n)$ and $r_k(P_s,n)$ for $sgek+3$. The question of determining the tower growth rate of $r_k(s,n)$ for all $sgek+1$ was posed by Erdos and Hajnal in 1972. (2) We show that determining the tower growth rate of $r_k(P_{k+1},n)$ is equivalent to determining the tower growth rate of $r_k(n,n)$, which is a notorious conjecture of Erdos, Hajnal and Rado from 1965 that remains open. Some related off-diagonal hypergraph Ramsey problems are also explored.

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

Recommendations

• New lower bounds for hypergraph Ramsey numbers
• Shift graphs and lower bounds on Ramsey numbers \(r_ k(l;r)\)
• Variants of the Erdős-Szekeres and Erdős-Hajnal Ramsey problems
• Hypergraph Ramsey numbers
• The Erdős-Hajnal hypergraph Ramsey problem

zbMATH Keywords

Ramsey theoryordered hypergraphstight-paths

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Hypergraphs (05C65) Ramsey theory (05D10)

Cites Work

• Some remarks on the theory of graphs
• The triangle-free process
• The Ramsey number R(3, t) has order of magnitude t²/log t
• A note on Ramsey numbers
• Title not available (Why is that?)
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• A new upper bound for diagonal Ramsey numbers
• A decomposition theorem for partially ordered sets
• Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem
• The early evolution of the \(H\)-free process
• Shift graphs and lower bounds on Ramsey numbers \(r_ k(l;r)\)
• Ordered Ramsey theory and track representations of graphs
• Hypergraph Ramsey numbers
• Title not available (Why is that?)
• An improved bound for the stepping-up lemma
• Partition relations for cardinal numbers
• An upper bound for some ramsey numbers
• Erdős-Szekeres-type theorems for monotone paths and convex bodies
• Multicolor Ramsey numbers for triple systems
• A Note on the Partition Calculus of P. ErdÖs and R. Rado
• The Erdős-Hajnal hypergraph Ramsey problem
• Coloring triple systems with local conditions

Cited In (10)

• Ramsey numbers of Berge-hypergraphs and related structures
• Variants of the Erdős-Szekeres and Erdős-Hajnal Ramsey problems
• Off-diagonal ordered Ramsey numbers of matchings
• Local approximation of the maximum cut in regular graphs
• Tower Gaps in Multicolour Ramsey Numbers
• Ramsey numbers of cliques versus monotone paths
• Using Ramsey theory to measure unavoidable spurious correlations in big data
• On-line size Ramsey number for monotone \(k\)-uniform ordered paths with uniform looseness
• Shift graphs and lower bounds on Ramsey numbers \(r_ k(l;r)\)
• Hypergraph Ramsey numbers of cliques versus stars

This page was built for publication: Off-diagonal hypergraph Ramsey numbers

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