The size Ramsey number of a directed path

DOI10.1016/J.JCTB.2011.10.002MaRDI QIDQ414648zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

Ramsey theorymonochromatic directed pathssize Ramsey number

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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
• Large monochromatic components and long monochromatic cycles in random hypergraphs
• Transference for loose Hamilton cycles in random 3-uniform hypergraphs
• Oriented discrepancy of Hamilton cycles
• 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 Ramsey size number of dipaths
• The connected size Ramsey number for matchings versus small disconnected graphs
• 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
• Note on the multicolour size-Ramsey number for paths
• Long cycles in subgraphs of (pseudo)random directed graphs
• 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
• Submodular functions and rooted trees
• The multicolour size-Ramsey number of powers of paths
• Path-monochromatic bounded depth rooted trees in (random) tournaments
• On-line size Ramsey number for monotone \(k\)-uniform ordered paths with uniform looseness
• Client-waiter games on complete and random graphs
• The largest hole in sparse random graphs
• Ordered size Ramsey number of paths
• Color‐biased Hamilton cycles in random graphs
• 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)