Ordered size Ramsey number of paths
| Autor: | Emily Heath, József Balogh, Mikhail Lavrov, Felix Christian Clemen |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Simple graph
Applied Mathematics Ordered graph 0211 other engineering and technologies 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Combinatorics Monotone polygon 010201 computation theory & mathematics Path (graph theory) Discrete Mathematics and Combinatorics Ramsey's theorem Absolute constant Mathematics |
| Zdroj: | Discrete Applied Mathematics. 276:13-18 |
| ISSN: | 0166-218X |
| Popis: | An ordered graph is a simple graph with an ordering on its vertices. Define the ordered path P n to be the monotone increasing path with n edges. The ordered size Ramsey number r ( P r , P s ) is the minimum number m for which there exists an ordered graph H with m edges such that every two-coloring of the edges of H contains a red copy of P r or a blue copy of P s . For 2 ≤ r ≤ s , we show 1 8 r 2 s ≤ r ( P r , P s ) ≤ C r 2 s ( log s ) 3 , where C > 0 is an absolute constant. This problem is motivated by the recent results of Bucic et al. (2019) and Letzter and Sudakov (2019) for oriented graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect