The \emph{ordered Ramsey number} $r_<(G,H)$ of ordered $k$-graphs $G$ and $H$ is the least integer $N$ such that every red-blue edge-coloring of the naturally ordered complete $k$-graph on $[N]$ contains a blue ordered copy of $G$ or a red ordered copy of $H$. We prove that there is an absolute constant $c>0$ such that, for every integer $d\ge1$, there is a constant $C_d>0$ for which every weakly $d$-degenerate ordered $3$-graph $H$ on $t$ vertices satisfies \[ r_<\bigl(H,K_3^{(3)}(n)\bigr) \le t\,2^{C_d n^{2-c/d}} \] for every positive integer $n$. This resolves a problem posed by Balko and Vizer ({\em SIAM J. Discrete Math., 2022}) in a stronger form. Furthermore, we show that the weak-degeneracy hypothesis cannot be replaced by bounded standard degeneracy. In particular, for every sufficiently large $n$, there exists a $1$-degenerate ordered $3$-graph $F$ on at most $2^{O(n)}$ vertices such that $r_<\bigl(F,K_3^{(3)}(n)\bigr)>2^{\Omega(n^2)}.$
Given graphs $F$ and $H$, the induced Ramsey number $r_{\mathrm{ind}}(F,H)$ is the smallest integer $n$ for which there exists a graph $G$ on $n$ vertices such that every red-blue colouring of $E(G)$ contains either a blue induced copy of $F$ or a red induced copy of $H$. A conjecture of Kohayakawa, Pr\"omel and R\"odl...
Bruno Andrades, Marcelo Campos, Rafael Filipe et al.· 0 citations
For ordered graphs $H_1,\ldots,H_t$, let $\rt(H_1,\ldots,H_t)$ denote the least integer $N$ such that every $t$-coloring of the edges of the naturally ordered complete graph on $[N]$ contains an ordered copy of $H_i$ in color $i$ for some $i\in[t]$. We prove that a uniformly random ordered matching $M$ on $n$ vertices...
For graphs $F$, $G$, and $H$, we write $F \to (G, H)$ if every red/blue edge-coloring of $F$ contains either a red copy of $G$ or a blue copy of $H$. The Ramsey number $R(G, H)$ is the smallest integer $N$ such that $K_N \to (G, H)$. Let $H := K_k + nK_h$ be the generalized book graph, and let $G := K_{p+1}(a_1, a_2, \...
For an integer $h\geq2$, an edge-ordered $h$-uniform hypergraph $H^<$ is an $h$-uniform hypergraph with a linear ordering of its hyperedges. For an integer $q \geq 1$, the edge-ordered Ramsey number $R_{\mathrm{edge}}(H^<;q)$ of $H^<$ is the smallest positive integer $N$ such that there exists an edge-ordered $h$-unifo...
For a graph $H$, the anti-Ramsey number $\operatorname{ar}(n,H)$ is the maximum number of colors in an edge-coloring of $K_n$ containing no rainbow copy of $H$, where a copy is rainbow if its edges have pairwise distinct colors. Let $s,t$ be nonnegative integers with $s+t\ge2$, and let $H_{s,t}$ be a graph consisting o...
The Ramsey number $R(G_1,G_2)$ is the smallest positive integer $n$ such that for every graph $H$ on $n$ vertices, either $H$ contains a copy of $G_1$ or the complement $\overline H$ contains a copy of $G_2$. Ramsey numbers involving the book graphs $B_n$, which consist of $n$ triangles sharing a common edge, have attr...
Stephen Chung, William J. Wesley· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.