Variants of the Erdos-Szekeres and Erdos-Hajnal Ramsey problems

preprint2016arXivOpen access

Abstract

Given integers ℓ,n\ell,n, the ℓ\ellth power of the path PnP_n is the ordered graph PnℓP_n^{\ell} with vertex set v1<v2<⋯<vnv_1<v_2<\cdots < v_n, and all edges of the form vivjv_iv_j where ∣i−j∣≤ℓ|i-j|\le \ell. The ramsey number r(Pnℓ,Pnℓ)r(P_n^{\ell}, P_n^{\ell}) is the minimum NN such that every 2-coloring of ([N]2){[N] \choose 2} results in a monochromatic copy of PnℓP_n^{\ell}. It is well-known that r(Pn1,Pn1)=(n−1)2+1r(P_n^1, P_n^1)=(n-1)^2+1. For ℓ>1\ell>1, Balko-Cibulka-Král-Kynčl proved that r(Pnℓ,Pnℓ)<cℓn128ℓr(P_n^{\ell}, P_n^{\ell})< c_{\ell}n^{128 \ell} and asked for the growth rate for fixed ℓ\ell. When ℓ=2\ell=2, we improve this upper bound by proving r(Pn2,Pn2)<cn19.5r(P_n^{2}, P_n^{2})< cn^{19.5}. Using this result, we determine the correct tower growth rate of the kk-uniform hypergraph ramsey number of a (k+1)(k+1)-clique versus an ordered tight path. Finally, we consider an ordered version of the classical Erd Hos-Hajnal hypergraph ramsey problem, improve the tower height given by the trivial upper bound, and conjecture that this tower height is optimal.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.