dc.contributor.author | Balko, Martin | |
dc.contributor.author | Poljak, Marian | |
dc.contributor.editor | Král’, Daniel | |
dc.contributor.editor | Nešetřil, Jaroslav | |
dc.date.accessioned | 2024-05-30T07:40:41Z | |
dc.date.available | 2024-05-30T07:40:41Z | |
dc.date.issued | 2023 | |
dc.identifier.uri | https://hdl.handle.net/20.500.14178/2491 | |
dc.description.abstract | For graphs $G^<$ and $H^<$ with linearly ordered vertex sets, the \emph{ordered Ramsey number} $r_<(G^<,H^<)$ is the smallest positive integer $N$ such that any red-blue coloring of the edges of the complete ordered graph $K^<_N$ on $N$ vertices contains either a blue copy of $G^<$ or a red copy of $H^<$.Motivated by a problem of Conlon, Fox, Lee, and Sudakov (2017), we study the numbers $r_<(M^<,K^<_3)$ where $M^<$ is an ordered matching on $n$ vertices.We prove that almost all $n$-vertex ordered matchings $M^<$ with interval chromatic number 2 satisfy $r_<(M^<,K^<_3) \in \Omega((n/\log n)^{5/4})$ and $r_<(M^<,K^<_3) \in O(n^{7/4})$, improving a recent result by Rohatgi (2019).We also show that there are $n$-vertex ordered matchings $M^<$ with interval chromatic number at least 3 satisfying $r_<(M^<,K^<_3) \in \Omega((n/\log n)^{4/3})$, which asymptotically matches the best known lower bound on these off-diagonal ordered Ramsey numbers for general $n$-vertex ordered matchings. | en |
dc.language.iso | en | |
dc.publisher | Masaryk University Press | |
dc.relation.url | https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-013 | |
dc.rights | Creative Commons Uveďte původ-Neužívejte dílo komerčně-Nezpracovávejte 4.0 International | cs |
dc.rights | Creative Commons Attribution-NonCommercial-NoDerivativeWorks 4.0 International | en |
dc.title | On ordered Ramsey numbers of matchings versus triangles | en |
dcterms.accessRights | openAccess | |
dcterms.license | https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode | |
dc.date.updated | 2024-05-30T07:40:41Z | |
dc.subject.keyword | ordered Ramsey numbers | en |
dc.subject.keyword | matchings | en |
dc.subject.keyword | triangles | en |
dc.publisher.publicationPlace | Praha | |
dc.relation.fundingReference | info:eu-repo/grantAgreement/GA0/GX/GX23-04949X | |
dc.relation.fundingReference | info:eu-repo/grantAgreement/UK/UNCE/SCI/UNCE/SCI/004 | |
dc.relation.fundingReference | info:eu-repo/grantAgreement/EU/FP8/DYNASNET | |
dc.relation.fundingReference | info:eu-repo/grantAgreement/UK/COOP/COOP | |
dc.date.embargoStartDate | 2024-05-30 | |
dc.type.obd | 57 | |
dc.type.version | info:eu-repo/semantics/acceptedVersion | |
dc.identifier.doi | 10.5817/CZ.MUNI.EUROCOMB23-013 | |
dc.identifier.obd | 641134 | |
dc.identifier.riv | RIV/00216208:11320/23:10473473 | |
dc.subject.rivPrimary | 10000::10200::10201 | |
dc.description.edition | 1 | |
dcterms.isPartOf.name | Proceedings of the 12th European Conference onCombinatorics, Graph Theory and Applications | |
dcterms.isPartOf.eissn | 2788-3116 | |
dcterms.isPartOf.journalYear | 2023 | |
dcterms.isPartOf.isbn | 978-80-280-0344-9 | |
uk.faculty.primaryId | 116 | |
uk.faculty.primaryName | Matematicko-fyzikální fakulta | cs |
uk.faculty.primaryName | Faculty of Mathematics and Physics | en |
uk.department.primaryId | 1293 | |
uk.department.primaryName | Katedra aplikované matematiky | cs |
uk.department.primaryName | Department of Applied Mathematics | en |
uk.department.secondaryId | 2110 | |
uk.department.secondaryName | Informatický ústav UK | cs |
uk.department.secondaryName | Informatický ústav UK | en |
uk.event.name | 12th European Conference on Combinatorics, Graph Theory and Applications | |
dc.description.pageRange | 94-100 | |
dc.type.obdHierarchyCs | PŘÍSPĚVEK V KONFERENČNÍM SBORNÍKU::příspěvek v konferenčním sborníku::příspěvek v recenzovaném konferenčním sborníku | cs |
dc.type.obdHierarchyEn | PAPER IN CONFERENCE PROCEEDINGS::article in proceedings::article in reviewed proceedings | en |
dc.type.obdHierarchyCode | 57::148::499 | en |
uk.displayTitle | On ordered Ramsey numbers of matchings versus triangles | en |