{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T05:47:11Z","timestamp":1775800031161,"version":"3.50.1"},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T00:00:00Z","timestamp":1738800000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>In this note, we formulate a \u2018one-sided\u2019 version of Wormald\u2019s differential equation method. In the standard \u2018two-sided\u2019 method, one is given a family of random variables that evolve over time and which satisfy some conditions, including a tight estimate of the expected change in each variable over one-time step. These estimates for the expected one-step changes suggest that the variables ought to be close to the solution of a certain system of differential equations, and the standard method concludes that this is indeed the case. We give a result for the case where instead of a tight estimate for each variable\u2019s expected one-step change, we have only an upper bound. Our proof is very simple and is flexible enough that if we instead assume tight estimates on the variables, then we recover the conclusion of the standard differential equation method.<\/jats:p>","DOI":"10.1017\/s0963548325000033","type":"journal-article","created":{"date-parts":[[2025,2,5]],"date-time":"2025-02-05T23:39:06Z","timestamp":1738798746000},"page":"545-558","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Extending Wormald\u2019s differential equation method to one-sided bounds"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3147-4690","authenticated-orcid":false,"given":"Patrick","family":"Bennett","sequence":"first","affiliation":[{"name":"Western Michigan University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Calum","family":"MacRury","sequence":"additional","affiliation":[{"name":"Columbia University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2025,2,6]]},"reference":[{"key":"S0963548325000033_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2022.113071"},{"key":"S0963548325000033_ref14","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177004612"},{"key":"S0963548325000033_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20133"},{"key":"S0963548325000033_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01454261"},{"key":"S0963548325000033_ref3","doi-asserted-by":"publisher","DOI":"10.2139\/ssrn.3443109"},{"key":"S0963548325000033_ref13","unstructured":"[13] Warnke, L. (2019) On Wormald\u2019s differential equation method. Accepted to Combinatorics, Probability, and Computing. https:\/\/arxiv.org\/abs\/1905.08928"},{"key":"S0963548325000033_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/18M1226130"},{"key":"S0963548325000033_ref9","article-title":"On (random-order) online contention resolution schemes for the matching polytope of (bipartite) graphs","author":"MacRury","year":"2024","journal-title":"Oper. Res."},{"key":"S0963548325000033_ref7","unstructured":"[7] Lee, E. and Singla, S. (2018) Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities. In 26th Annual European Symposium on Algorithms (ESA 2018), ( Azar, Y. , Bast, H. and Herman, G. , eds), Vol. 112 of Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, pp. 57:1\u201357:14."},{"key":"S0963548325000033_ref5","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996452"},{"key":"S0963548325000033_ref6","unstructured":"[6] Fu, H. , Tang, Z. G. , Wu, H. , Wu, J. and Zhang, Q. (2021) Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), ( Bansal, N. , Merelli, E. and Worell, J. , eds), Vol. 198 of Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, pp. 68:1\u201368:20."},{"key":"S0963548325000033_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2015.04.015"},{"key":"S0963548325000033_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0362-546X(96)00259-3"},{"key":"S0963548325000033_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649788"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548325000033","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T04:49:45Z","timestamp":1775796585000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548325000033\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,6]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["S0963548325000033"],"URL":"https:\/\/doi.org\/10.1017\/s0963548325000033","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,6]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution-NonCommercial-ShareAlike licence (https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/), which permits non-commercial re-use, distribution, and reproduction in any medium, provided the same Creative Commons licence is included and the original work is properly cited. The written permission of Cambridge University Press must be obtained for commercial re-use.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}