Ramsey-type problems in orientations of graphs

MaRDI QIDQ6315118zbMATH OpenFDO

Authors Bruno Pasqualotto Cavalar

Publication date 5 March 2019

Abstract: Given an acyclic oriented graph $vecH$ and a graph $G$, we write $GovecH$ if every orientation of $G$ has an oriented copy of $vecH$. We define $vecR(vecH)$ as the smallest number $n$ such that there exists a graph $G$ satisfying $GovecH$. Denoting by $R(H)$ the classical Ramsey number of a graph $H$, we show that $vecR(vecH)leq2R(H{)}^{clo{g}^{2}h}$ for every acyclic oriented graph $vecH$ with $h$ vertices, where $H$ is its underlying undirected graph. We also study the threshold function for the event $G(n,p)ovecH$ in the binomial random graph $G(n,p)$. Finally, we consider the isometric case, in which we require that, for every two vertices $x,yinV(vecH)$ and their respective copies $x^{\prime },y^{\prime }$ in $vecG$, the distance between $x$ and $y$ is equal to the distance between $x^{\prime }$ and $y^{\prime }$. We prove an upper bound for the isometric Ramsey number of an acyclic orientation of the cycle, applying the hypergraph container lemma in random graphs.

This page was built for publication: Ramsey-type problems in orientations of graphs

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