The size Ramsey number of a directed path (Q414648): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Importer (talk | contribs)
Changed an Item
Property / 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.
Property / 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. / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: Boris Bukh / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 05C15 / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 05C55 / rank
 
Normal rank
Property / zbMATH DE Number
 
Property / zbMATH DE Number: 6033283 / rank
 
Normal rank
Property / zbMATH Keywords
 
Ramsey theory
Property / zbMATH Keywords: Ramsey theory / rank
 
Normal rank
Property / zbMATH Keywords
 
size Ramsey number
Property / zbMATH Keywords: size Ramsey number / rank
 
Normal rank
Property / zbMATH Keywords
 
monochromatic directed paths
Property / zbMATH Keywords: monochromatic directed paths / rank
 
Normal rank

Revision as of 19:20, 29 June 2023

scientific article
Language Label Description Also known as
English
The size Ramsey number of a directed path
scientific article

    Statements

    The size Ramsey number of a directed path (English)
    0 references
    0 references
    0 references
    0 references
    11 May 2012
    0 references
    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.
    0 references
    0 references
    Ramsey theory
    0 references
    size Ramsey number
    0 references
    monochromatic directed paths
    0 references

    Identifiers