{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,4]],"date-time":"2024-07-04T00:14:18Z","timestamp":1720052058034},"reference-count":8,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,4,4]],"date-time":"2024-04-04T00:00:00Z","timestamp":1712188800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,4]],"date-time":"2024-04-04T00:00:00Z","timestamp":1712188800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Colour the edges of the complete graph with vertex set <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\{1, 2, \\dotsc , n\\}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>{<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u22ef<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>}<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with an arbitrary number of colours. What is the smallest integer <jats:italic>f<\/jats:italic>(<jats:italic>l<\/jats:italic>,\u00a0<jats:italic>k<\/jats:italic>) such that if <jats:inline-formula><jats:alternatives><jats:tex-math>$$n &gt; f(l,k)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>&gt;<\/mml:mo>\n                    <mml:mi>f<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>l<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> then there must exist a monotone monochromatic path of length <jats:italic>l<\/jats:italic> or a monotone rainbow path of length <jats:italic>k<\/jats:italic>? Lefmann, R\u00f6dl, and Thomas conjectured in 1992 that <jats:inline-formula><jats:alternatives><jats:tex-math>$$f(l, k) = l^{k - 1}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>f<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>l<\/mml:mi>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mmultiscripts>\n                      <mml:mi>l<\/mml:mi>\n                      <mml:mrow\/>\n                      <mml:mrow>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mo>-<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:mmultiscripts>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and proved this for <jats:inline-formula><jats:alternatives><jats:tex-math>$$l \\geqslant (3 k)^{2 k}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>l<\/mml:mi>\n                    <mml:mo>\u2a7e<\/mml:mo>\n                    <mml:mmultiscripts>\n                      <mml:mrow>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mn>3<\/mml:mn>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                      <mml:mrow\/>\n                      <mml:mrow>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mi>k<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:mmultiscripts>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We prove the conjecture for <jats:inline-formula><jats:alternatives><jats:tex-math>$$l \\geqslant k^3 (\\log k)^{1 + o(1)}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>l<\/mml:mi>\n                    <mml:mo>\u2a7e<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mn>3<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mmultiscripts>\n                      <mml:mrow>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                      <mml:mrow\/>\n                      <mml:mrow>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:mi>o<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:mmultiscripts>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and establish the general upper bound <jats:inline-formula><jats:alternatives><jats:tex-math>$$f(l, k) \\leqslant k (\\log k)^{1 + o(1)} \\cdot l^{k - 1}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>f<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>l<\/mml:mi>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>\u2a7d<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mmultiscripts>\n                      <mml:mrow>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                      <mml:mrow\/>\n                      <mml:mrow>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:mi>o<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:mmultiscripts>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:mmultiscripts>\n                      <mml:mi>l<\/mml:mi>\n                      <mml:mrow\/>\n                      <mml:mrow>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mo>-<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:mmultiscripts>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This reduces the gap between the best lower and upper bounds from exponential to polynomial in <jats:italic>k<\/jats:italic>. We also generalise some of these results to the tournament setting.<\/jats:p>","DOI":"10.1007\/s00493-024-00090-7","type":"journal-article","created":{"date-parts":[[2024,4,4]],"date-time":"2024-04-04T12:01:41Z","timestamp":1712232101000},"page":"675-690","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Flashes and Rainbows in Tournaments"],"prefix":"10.1007","volume":"44","author":[{"given":"Ant\u00f3nio","family":"Gir\u00e3o","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Freddie","family":"Illingworth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lukas","family":"Michel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Savery","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex","family":"Scott","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,4,4]]},"reference":[{"key":"90_CR1","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1017\/S0017089500000677","volume":"10","author":"I Anderson","year":"1969","unstructured":"Anderson, I.: A variance method in combinatorial number theory. Glasg. Math. J. 10, 126\u2013129 (1969). https:\/\/doi.org\/10.1017\/S0017089500000677","journal-title":"Glasg. Math. J."},{"issue":"1","key":"90_CR2","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1002\/rsa.20780","volume":"54","author":"M Buci\u0107","year":"2019","unstructured":"Buci\u0107, M., Letzter, S., Sudakov, B.: Monochromatic paths in random tournaments. Random Struct. Algorithms 54(1), 69\u201381 (2019). https:\/\/doi.org\/10.1002\/rsa.20780","journal-title":"Random Struct. Algorithms"},{"issue":"23","key":"90_CR3","first-page":"191","volume":"2","author":"NG de Bruijn","year":"1951","unstructured":"de Bruijn, N.G., van Ebbenhorst Tengbergen, Ca., Kruyswijk, D.: On the set of divisors of a number. Nieuw Archief voor Wiskunde 2(23), 191\u2013193 (1951)","journal-title":"Nieuw Archief voor Wiskunde"},{"key":"90_CR4","doi-asserted-by":"publisher","unstructured":"Erd\u0151s, P., Rado, R.: A combinatorial theorem. J. Lond. Math. Soc. s1-25(4), 249\u2013255 (1950). https:\/\/doi.org\/10.1112\/jlms\/s1-25.4.249","DOI":"10.1112\/jlms\/s1-25.4.249"},{"issue":"1","key":"90_CR5","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s004930070037","volume":"20","author":"T Jiang","year":"2000","unstructured":"Jiang, T., Mubayi, D.: New upper bounds for a canonical Ramsey problem. Combinatorica 20(1), 141\u2013146 (2000). https:\/\/doi.org\/10.1007\/s004930070037","journal-title":"Combinatorica"},{"issue":"1","key":"90_CR6","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/BF01294461","volume":"15","author":"H Lefmann","year":"1995","unstructured":"Lefmann, H., R\u00f6dl, V.: On Erd\u0151s-Rado numbers. Combinatorica 15(1), 85\u2013104 (1995). https:\/\/doi.org\/10.1007\/BF01294461","journal-title":"Combinatorica"},{"issue":"4","key":"90_CR7","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/BF02351589","volume":"8","author":"H Lefmann","year":"1992","unstructured":"Lefmann, H., R\u00f6dl, V., Thomas, R.: Monochromatic vs multicolored paths. Graphs Comb. 8(4), 323\u2013332 (1992). https:\/\/doi.org\/10.1007\/BF02351589","journal-title":"Graphs Comb."},{"key":"90_CR8","doi-asserted-by":"publisher","unstructured":"Ramsey, F.P.: On a problem of formal logic. Proc. Lond. Math. Soc. s2-30(1), 264\u2013286 (1930). https:\/\/doi.org\/10.1112\/plms\/s2-30.1.264","DOI":"10.1112\/plms\/s2-30.1.264"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00090-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-024-00090-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00090-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,3]],"date-time":"2024-07-03T11:06:56Z","timestamp":1720004816000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-024-00090-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,4]]},"references-count":8,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["90"],"URL":"https:\/\/doi.org\/10.1007\/s00493-024-00090-7","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,4]]},"assertion":[{"value":"1 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 January 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 February 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 July 2024","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Erratum","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"An Erratum to this paper has been published:","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00493-024-00111-5","URL":"https:\/\/doi.org\/10.1007\/s00493-024-00111-5","order":8,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}