Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-02-11T01:14:25.349Z Has data issue: false hasContentIssue false
  • English
  • Français

Extending Wormald’s differential equation method to one-sided bounds

Part of: Stochastic processes Combinatorial probability

Published online by Cambridge University Press:  06 February 2025

Patrick Bennett Open the ORCID record for Patrick Bennett [Opens in a new window]  and
Calum MacRury
Patrick Bennett*
Affiliation:
Department of Mathematics, Western Michigan University, Kalamazoo, MI, USA
Calum MacRury
Affiliation:
Graduate School of Business, Columbia University, New York, USA
*
Corresponding author: Patrick Bennett; Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this note, we formulate a ‘one-sided’ version of Wormald’s differential equation method. In the standard ‘two-sided’ 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’s 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.

Keywords

Differential equation methoddynamic concentrationprobabilistic combinatoricsrandom processes

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 60G42: Martingales with discrete parameter
Type
Paper
Information
Combinatorics, Probability and Computing , First View , pp. 1 - 14
Check for updates
Copyright
© The Author(s), 2025. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bennett, P. and Dudek, A. (2022) A gentle introduction to the differential equation method and dynamic concentration. Discrete Math. 345 113071.CrossRefGoogle Scholar
Bohman, T, Frieze, A and Lubetzky, E (2015) Random triangle removal. Adv. Math 280 379–438.CrossRefGoogle Scholar
Fata, E., Ma, W and Simchi-Levi, D. (2019) Multi-stage and multi-customer assortment optimization with inventory constraints. http://dx.doi.org/10.2139/ssrn.3443109CrossRefGoogle Scholar
Feldman, M., Svensson, O. and Zenklusen, R. (2021) Online contention resolution schemes with applications to bayesian selection problems. SIAM J. Comput. 50 255–300.CrossRefGoogle Scholar
Freedman, D. A. (1975) On tail probabilities for martingales. Ann. Probab. 3 100–118.CrossRefGoogle Scholar
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 – Leibniz-Zentrum für Informatik, pp. 68:1–68:20.Google Scholar
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–Leibniz-Zentrum fuer Informatik, pp. 57:1–57:14.Google Scholar
MacRury, C. and Ma, W. (2024) Random-order contention resolution via continuous induction: Tightness for bipartite matching under vertex arrivals. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC. 2024, (Mohar, B., Shinkar, I. and O’Donnell, R., eds), Vancouver, BC, Canada, pp. ACM, 1629–1640,CrossRefGoogle Scholar
MacRury, C., Ma, W. and Grammel, N. (2024) On (random-order) online contention resolution schemes for the matching polytope of (bipartite) graphs. Oper. Res. https://doi.org/10.1287/opre.2023.0339 CrossRefGoogle Scholar
Petrovitch, M. M. (1901) Sur une manière d’étendre le théorème de la moyenne aux équations différentielles du premier ordre. Math. Ann. 54 417–436.CrossRefGoogle Scholar
Telcs, A., Wormald, N. and Zhou, S. (2007) Hamiltonicity of random graphs produced by 2-processes. Random Struct. Algor. 31 450–481.CrossRefGoogle Scholar
Walter, W. (1997) Differential inequalities and maximum principles: theory, new methods and applications. In Proceedings of the Second World Congress of Nonlinear Analysts, Part 8 (Athens, 1996), Vol. 30, pp. 4695–4711.CrossRefGoogle Scholar
Warnke, L.(2019) On Wormald’s differential equation method. Accepted to Combinatorics, Probability, and Computing. https://arxiv.org/abs/1905.08928 Google Scholar
Wormald, N. C. (1995) Differential equations for random processes and random graphs. The Annals of Applied Probability 5 1217–1235.CrossRefGoogle Scholar