Report
Ordered Ramsey numbers of graphs with $m$ edges
| العنوان: | Ordered Ramsey numbers of graphs with $m$ edges |
|---|---|
| المؤلفون: | Bradač, Domagoj, Morawski, Patryk, Sudakov, Benny, Wigderson, Yuval |
| سنة النشر: | 2024 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics |
| الوصف: | Given a vertex-ordered graph $G$, the ordered Ramsey number $r_<(G)$ is the minimum integer $N$ such that every $2$-coloring of the edges of the complete ordered graph $K_N$ contains a monochromatic ordered copy of $G$. Motivated by a similar question posed by Erd\H{o}s and Graham in the unordered setting, we study the problem of bounding the ordered Ramsey number of any ordered graph $G$ with $m$ edges and no isolated vertices. We prove that $r_<(G) \leq e^{10^9 \sqrt{m} (\log \log m)^{3/2}}$ for any such $G$, which is tight up to the $(\log \log m)^{3/2}$ factor in the exponent. As a corollary, we obtain the corresponding bound for the oriented Ramsey number of a directed graph with $m$ edges. Comment: 13 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2412.17599 |
| رقم الانضمام: | edsarx.2412.17599 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |