Vizer, Máté and Balko, Martin (2019) EDGE-ORDERED RAMSEY NUMBERS. ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, 88 (3). pp. 409-414. ISSN 0862-9544
|
Text
Balko Vizer Edge ordered Ramsey EUROCOMB.pdf Download (365kB) | Preview |
Abstract
We introduce and study a variant of Ramsey numbers for edge-ordered graphs, that is, graphs with linearly ordered sets of edges. The edge-ordered Ramsey number R_e(G) of an edge-ordered graph G is the minimum positive integer N such that there exists an edge-ordered complete graph K_N on N vertices such that every 2-coloring of the edges of K_N contains a monochromatic copy of G as an edge-ordered subgraph of K_N. We prove that the edge-ordered Ramsey number R_e(G) is finite for every edge-ordered graph G and we obtain better estimates for special classes of edge-ordered graphs. In particular, we prove R_e(G) <= 2^{O(n^3\log{n})} for every bipartite edge-ordered graph G on n vertices. We also introduce a natural class of edge-orderings, called \emph{lexicographic edge-orderings}, for which we can prove much better upper bounds on the corresponding edge-ordered Ramsey numbers.
| Item Type: | Article |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
| Depositing User: | Máté Vizer |
| Date Deposited: | 28 Sep 2020 05:47 |
| Last Modified: | 03 Apr 2023 07:00 |
| URI: | http://real.mtak.hu/id/eprint/114997 |
Actions (login required)
 |
Edit Item |
