The size Ramsey number of a directed path

Abstract: Given a graph

H

, the size Ramsey number

r_{e} (H, q)

is the minimal number

m

for which there is a graph

G

with

m

edges such that every

q

-coloring of

G

contains a monochromatic copy of

H

. We study the size Ramsey number of the directed path of length

n

in oriented graphs, where no antiparallel edges are allowed. We give nearly tight bounds for every fixed number of colors, showing that for every

q g e q 1

there are constants

c_{1} = c_{1} (q), c_{2}

such that

frac{c_1(q) n^{2q}(log n)^{1/q}}{(loglog n)^{(q+2)/q}} leq r_e(overrightarrow{P_n},q+1) leq c_2 n^{2q}(log {n})^2.

Our results show that the path size Ramsey number in oriented graphs is asymptotically larger than the path size Ramsey number in general directed graphs. Moreover, the size Ramsey number of a directed path is polynomially dependent in the number of colors, as opposed to the undirected case. Our approach also gives tight bounds on

r_{e} (o v e r r i g h t a r r o w P_{n}, q)

for general directed graphs with

q g e q 3

, extending previous results.

Review text

For a graph (resp. oriented graph) \(G\) let \(r_e(G,q)\) be the smallest number of edges in a graph (resp. oriented graph) \(H\) such that every \(q\)-edge-coloring of \(H\) contains a monochromatic copy of \(G\). \textit{J. Beck} [``On size Ramsey number of paths, trees, and circuits. I, J. Graph Theory 7, 115--129 (1983; Zbl 0508.05047)] proved that for the \(n\)-vertex path \(r_e(P_n,q)\leq c_q n\). In this paper it is shown that \[ \frac{c_1 n^{2q}(\log n)^{1/q}}{(\log \log n)^{(q+2)/q}} \leq r_e(\vec{P}_n,q+1)\leq c_2 n^{2q}(\log n)^2. \] Interestingly, in the category of directed graphs, i.e., graphs with antiparallel edges, the answer is different. Generalizing the works of \textit{H. Raynaud} [``Sur le circuit hamiltonien bi-colore dans les graphes orientes, Period. Math. Hung. 3, 289--297 (1973; Zbl 0267.05114)] and \textit{D. Reimer} [``The Ramsey size number of dipaths, Discrete Math. 257, No.\,1, 173--175 (2002; Zbl 1012.05116)] for \(q=1\), it is proved that \(r_e(\vec{P}_n,q+1)=\Theta(n^{2q})\) for digraphs.

Recommendations

Cites work

Cited in

(45)

This page was built for publication: The size Ramsey number of a directed path

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