DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kim, Jaehoon | ko |
dc.contributor.author | Lee, Joonkyung | ko |
dc.contributor.author | Liu, Hong | ko |
dc.contributor.author | Tran, Tuan | ko |
dc.date.accessioned | 2024-09-10T06:00:11Z | - |
dc.date.available | 2024-09-10T06:00:11Z | - |
dc.date.created | 2024-06-08 | - |
dc.date.issued | 2024-08 | - |
dc.identifier.citation | COMBINATORICA, v.44, no.4, pp.909 - 919 | - |
dc.identifier.issn | 0209-9683 | - |
dc.identifier.uri | http://hdl.handle.net/10203/322859 | - |
dc.description.abstract | We prove that every properly edge-colored n-vertex graph with average degree at least 32 ( log 5 n ) 2 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$32(\log 5n)<^>2$$\end{document} contains a rainbow cycle, improving upon the ( log n ) 2 + o ( 1 ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(\log n)<^>{2+o(1)}$$\end{document} bound due to Tomon. We also prove that every properly edge-colored n-vertex graph with at least 10 5 k 3 n 1 + 1 / k \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$10<^>5 k<^>3 n<^>{1+1/k}$$\end{document} edges contains a rainbow 2k-cycle, which improves the previous bound 2 c k 2 n 1 + 1 / k \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2<^>{ck<^>2}n<^>{1+1/k}$$\end{document} obtained by Janzer. Our method using homomorphism inequalities and a lopsided regularization lemma also provides a simple way to prove the Erd & odblac;s-Simonovits supersaturation theorem for even cycles, which may be of independent interest. | - |
dc.language | English | - |
dc.publisher | SPRINGER HEIDELBERG | - |
dc.title | Rainbow Cycles in Properly Edge-Colored Graphs | - |
dc.type | Article | - |
dc.identifier.wosid | 001218758100001 | - |
dc.identifier.scopusid | 2-s2.0-85191968168 | - |
dc.type.rims | ART | - |
dc.citation.volume | 44 | - |
dc.citation.issue | 4 | - |
dc.citation.beginningpage | 909 | - |
dc.citation.endingpage | 919 | - |
dc.citation.publicationname | COMBINATORICA | - |
dc.identifier.doi | 10.1007/s00493-024-00101-7 | - |
dc.contributor.localauthor | Kim, Jaehoon | - |
dc.contributor.nonIdAuthor | Lee, Joonkyung | - |
dc.contributor.nonIdAuthor | Liu, Hong | - |
dc.contributor.nonIdAuthor | Tran, Tuan | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | Rainbow cycles | - |
dc.subject.keywordAuthor | Turan problem | - |
dc.subject.keywordAuthor | Extremal number | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.