On edge-ordered Ramsey numbers. (English) Zbl 1454.05076
Summary: An edge-ordered graph is a graph with a linear ordering of its edges. Two edge-ordered graphs are equivalent if there is an isomorphism between them preserving the edge-ordering. The edge-ordered Ramsey number \(r_{\text{edge}}(H; q)\) of an edge-ordered graph \(H\) is the smallest \(N\) such that there exists an edge-ordered graph \(G\) on \(N\) vertices such that, for every \(q\)-coloring of the edges of \(G\), there is a monochromatic subgraph of \(G\) equivalent to \(H\). Recently, M. Balko and M. Vizer [Eur. J. Comb. 87, Article ID 103100, 10 p. (2020; Zbl 1439.05129)] proved that \(r_{\text{edge}}(H; q)\) exists, but their proof gave enormous upper bounds on these numbers. We give a new proof with a much better bound, showing there exists a constant \(c\) such that \(r_{\text{edge}}(H;q) \le 2^{c^q n^{2q-2} \log^q n}\) for every edge-ordered graph \(H\) on \(n\) vertices. We also prove a polynomial bound for the edge-ordered Ramsey number of graphs of bounded degeneracy. Finally, we prove a strengthening for graphs where every edge has a label and the labels do not necessarily have an ordering.
Citations:
Zbl 1439.05129References:
| [1] | M.Balko, J.Cibulka, K.Král, and J.Kyncc̆l, Ramsey numbers of ordered graphs, Electron. Notes Discrete Math.49 (2015), 419-424. · Zbl 1346.05179 |
| [2] | D.Bal and L.DeBiasio. New lower bounds on the size‐Ramsey number of a path, 2019, arXiv preprint arXiv:1909.06354. |
| [3] | M.Balko and M.Vizer, Edge‐ordered Ramsey numbers, Acta Math. Univ. Comenian.88 (2019), 409-414. |
| [4] | J.Balogh, F.C.Clemen, E.Heath, and M.Lavrov, Ordered size Ramsey number of paths, Discrete Appl. Math.276 (2020), 13-18. · Zbl 1435.05138 |
| [5] | J.Beck, On size Ramsey number of paths, trees and cycles I, J. Graph Theory7 (1983), 115-130. · Zbl 0508.05047 |
| [6] | I.Ben‐Eliezer, M.Krivelevich, and B.Sudakov, The size Ramsey number of a directed path, J. Combin. Theory B.102 (2012), 743-755. · Zbl 1245.05041 |
| [7] | C.Borgs, J.Chayes, L.Lovász, V.T.Sós, and K.Vesztergombi, Convergent sequences of dense graphs I. Subgraph frequencies, metric properties and testing, Adv. Math.219 (2008), 1801-1851. · Zbl 1213.05161 |
| [8] | M.Bucic, M.Kwan, A.Pokrovskiy, B.Sudakov, T.Tran, and A.Zsolt Wagner, Nearly‐linear monotone paths in edge‐ordered graphs, Israel J. Math. (to appear). · Zbl 1447.05113 |
| [9] | S.A.Burr and P.Erdős, On the magnitude of generalized Ramsey numbers for graphs. In Infinite and Finite Sets, Vol. 1 (Keszthely, 1973), 214-240, Colloq. Math. Soc. János Bolyai, vol. 10. Amsterdam: North‐Holland, 1975. · Zbl 0316.05110 |
| [10] | A.R.Calderbank, F.R.K.Chung, and D.G.Sturtevant, Increasing sequences with nonzero block sums and increasing paths in edge‐ordered graphs, Discrete Math.50 (1984), 15-28. · Zbl 0542.05058 |
| [11] | V.Chvátal and J.Komlós, Some combinatorial theorems on monotonicity, Can. Math. Bull.14 (1971), 151-157. · Zbl 0214.23503 |
| [12] | D.Conlon, J.Fox, and B.Sudakov, On two problems in graph Ramsey theory, Combinatorica32 (2012), 513-535. · Zbl 1289.05332 |
| [13] | D.Conlon, J.Fox, and B.Sudakov, Recent developments in graph Ramsey theory, Surv. Combin.424 (2015), 49-118. · Zbl 1352.05123 |
| [14] | D.Conlon, J.Fox, C.Lee, and B.Sudakov, Ordered Ramsey numbers, J. Combin. Theory B122 (2017), 353-383. · Zbl 1350.05085 |
| [15] | W.Deuber, A generalization of Ramsey’s theorem. In Infinite and Finite Sets, Vol. 1 (Keszthely, 1973), 323-332, Colloq. Math. Soc. János Bolyai, vol. 10. Amsterdam: North‐Holland, 1975. · Zbl 0301.05103 |
| [16] | R.A.Duke, H.Lefmann, and V.Rödl, A fast approximation algorithm for computing the frequencies of subgraphs in a given graph, SIAM J. Comput.24 (1995), 598-620. · Zbl 0831.68049 |
| [17] | A.Dudek and P.Prałat, On some multicolor Ramsey properties of random graphs, SIAM J. Discrete Math.31 (2017), 2079-2092. · Zbl 1370.05211 |
| [18] | P.Erdős, R.J.Faudree, C.C.Rousseau, and R.H.Schelp, The size Ramsey number, Period. Math. Hungar.9 (1978), 145-161. · Zbl 0331.05122 |
| [19] | P.Erdős, A.Hajnal, and J.Pach, A Ramsey‐type theorem for bipartite graphs, Geombinatorics10 (2000), 64-68. · Zbl 0978.05052 |
| [20] | P.Erdős and R.Rado, Combinatorial theorems on classifications of subsets of a given set, Proc. London Math. Soc.3 (1952), 417-439. · Zbl 0048.28203 |
| [21] | J.Fox and B.Sudakov, Induced Ramsey‐type theorems, Adv. Math.219 (2008), 1771-1800. · Zbl 1152.05054 |
| [22] | J.Friedman and N.Pippenger, Expanding graphs contain all small trees, Combinatorica7 (1987), 71-76. · Zbl 0624.05028 |
| [23] | R.L.Graham and D.J.Kleitman, Increasing paths in edge ordered graphs, Period. Math. Hungar.3 (1973), 141-148. · Zbl 0243.05116 |
| [24] | R.L.Graham and B.L.Rothschild, Ramsey’s theorem for n‐parameter sets, Trans. Amer. Math. Soc.159 (1971), 257-292. · Zbl 0233.05003 |
| [25] | R.Greenwood and A.Gleason, Combinatorial relations and chromatic graphs, Can. J. Math.7 (1955), 1-7. · Zbl 0064.17901 |
| [26] | P.E.Haxell, Y.Kohayakawa, and T.Łuczak, The induced size‐Ramsey number of cycles, Combin. Probab. Comput.4 (1995), 217-239. · Zbl 0839.05073 |
| [27] | W.Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc.58 (1963), 13-30. · Zbl 0127.10602 |
| [28] | J.Hubička and J.Nešetřil, All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms), Adv. Math.356 (2019), 106791. · Zbl 1421.05091 |
| [29] | J.Komlós and M.Simonovits, Szemerédi’s regularity lemma and its applications in graph theory. In Paul Erdős is Eighty, Vol. 2 (Keszthely, 1993), 295-352, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 1996. · Zbl 0851.05065 |
| [30] | M.Lavrov and P.Loh, Hamiltonian increasing paths in random edge orderings, Random Structures Algorithms48 (2016), 588-611. · Zbl 1338.05150 |
| [31] | C.Lee, Ramsey numbers of degenerate graphs, Ann. Math.185 (2017), 791-829. · Zbl 1365.05193 |
| [32] | S.Letzter and B.Sudakov, The oriented size Ramsey number of directed paths, Eur. J. Combin. (2020), 103103. · Zbl 1442.05129 |
| [33] | A.Martinsson, Most edge‐orderings of K_n have maximal altitude, Random Structures Algorithms54 (2019), 559-585. · Zbl 1414.05268 |
| [34] | K.G.Milans, Monotone paths in dense edge‐ordered graphs, J. Combin.8 (2017), 423-437. MR 3668875. · Zbl 1370.05111 |
| [35] | D.Mubayi and A.Suk. A survey of hypergraph Ramsey problems, 2019, arXiv preprint arXiv:1707.04229. |
| [36] | F.P.Ramsey, On a problem of formal logic, J. Lond. Math. Soc.30 (1930), 264-286. · JFM 55.0032.04 |
| [37] | V.Rödl. The dimension of a graph and generalized Ramsey theorems, Master’s thesis, Charles University, 1973. |
| [38] | S.Shelah, Primitive recursive bounds for van der Waerden numbers, J. Amer. Math. Soc.1 (1988), 683-697. · Zbl 0649.05010 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
