The size Ramsey number of a directed path

DOI10.1016/J.JCTB.2011.10.002zbMATH Open1245.05041arXiv1005.5171OpenAlexW2066508430MaRDI QIDQ414648FDOQ414648

Authors: Ido Ben-Eliezer, Michael Krivelevich, Benny Sudakov 

Publication date: 11 May 2012

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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 $qgeq1$ there are constants $c_1=c_1(q),c_2$ such that ${\displaystyle }$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.${\displaystyle }$ 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(overrightarrow{P}_n,q)$ for general directed graphs with $qgeq3$, extending previous results.

Full work available at URL: https://arxiv.org/abs/1005.5171

Recommendations

• The oriented size Ramsey number of directed paths
• The Ramsey size number of dipaths
• The size‐Ramsey number of powers of paths
• Size-Ramsey numbers of cycles versus a path

zbMATH Keywords

Ramsey theorymonochromatic directed pathssize Ramsey number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

Cites Work

• Expanding graphs contain all small trees
• The size Ramsey number
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Acyclic systems of representatives and acyclic colorings of digraphs
• On size Ramsey number of paths, trees, and circuits. I
• Title not available (Why is that?)
• Explicit construction of linear sized tolerant networks
• Sur le circuit hamiltonien bi-colore dans les graphes orientes
• Vertex coverings by monochromatic paths and cycles
• Nombre chromatique et plus longs chemins d'un graphe
• On a Ramsey type theorem
• Title not available (Why is that?)
• Global connectivity and expansion: long cycles and factors in \(f\)-connected graphs
• 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• The Ramsey size number of dipaths
• Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors

Cited In (39)

• The \(m\)-degenerate chromatic number of a digraph
• Lower bounds of size Ramsey number for graphs with small independence number
• Perfect matchings and Hamiltonian cycles in the preferential attachment model
• An analogue of the Erdős-Gallai theorem for random graphs
• Partitioning a graph into a cycle and a sparse graph
• Monochromatic paths in 2-edge-coloured graphs and hypergraphs
• Transference for loose Hamilton cycles in random 3-uniform hypergraphs
• Oriented discrepancy of Hamilton cycles
• Large monochromatic components and long monochromatic cycles in random hypergraphs
• Longest cycles in sparse random digraphs
• On some multicolor Ramsey properties of random graphs
• Monochromatic trees in random tournaments
• Turán‐type problems for long cycles in random and pseudo‐random graphs
• Cycle lengths in randomly perturbed graphs
• Last passage percolation on the complete graph
• The connected size Ramsey number for matchings versus small disconnected graphs
• The Ramsey size number of dipaths
• Fast strategies in maker-breaker games played on random boards
• On oriented cycles in randomly perturbed digraphs
• A strengthening of the Erdős-Szekeres theorem
• Hamilton cycles in pseudorandom graphs
• Long cycles in subgraphs of (pseudo)random directed graphs
• Note on the multicolour size-Ramsey number for paths
• On edge-ordered Ramsey numbers
• A note on non-isomorphic edge-color classes in random graphs
• The multicolor size-Ramsey numbers of cycles
• The size-Ramsey number of 3-uniform tight paths
• 2-universality in randomly perturbed graphs
• Path-monochromatic bounded depth rooted trees in (random) tournaments
• Submodular functions and rooted trees
• The largest hole in sparse random graphs
• The multicolour size-Ramsey number of powers of paths
• On-line size Ramsey number for monotone \(k\)-uniform ordered paths with uniform looseness
• Color‐biased Hamilton cycles in random graphs
• Client-waiter games on complete and random graphs
• Ordered size Ramsey number of paths
• Size-Ramsey numbers of cycles versus a path
• The oriented size Ramsey number of directed paths
• Ramsey goodness of clique versus paths in random graphs

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)