The random k‐matching‐free process

Krivelevich M, Kwan MA, Loh P, Sudakov B. 2018. The random k‐matching‐free process. Random Structures and Algorithms. 53(4), 692–716.


Journal Article | Published | English

Scopus indexed
Author
Krivelevich, Michael; Kwan, Matthew AlanIST Austria; Loh, Po‐Shen; Sudakov, Benny
Abstract
Let P be a graph property which is preserved by removal of edges, and consider the random graph process that starts with the empty n-vertex graph and then adds edges one-by-one, each chosen uniformly at random subject to the constraint that P is not violated. These types of random processes have been the subject of extensive research over the last 20 years, having striking applications in extremal combinatorics, and leading to the discovery of important probabilistic tools. In this paper we consider the k-matching-free process, where P is the property of not containing a matching of size k. We are able to analyse the behaviour of this process for a wide range of values of k; in particular we prove that if k=o(n) or if n−2k=o(n−−√/logn) then this process is likely to terminate in a k-matching-free graph with the maximum possible number of edges, as characterised by Erdős and Gallai. We also show that these bounds on k are essentially best possible, and we make a first step towards understanding the behaviour of the process in the intermediate regime.
Publishing Year
Date Published
2018-12-01
Journal Title
Random Structures and Algorithms
Volume
53
Issue
4
Page
692-716
ISSN
eISSN
IST-REx-ID

Cite this

Krivelevich M, Kwan MA, Loh P, Sudakov B. The random k‐matching‐free process. Random Structures and Algorithms. 2018;53(4):692-716. doi:10.1002/rsa.20814
Krivelevich, M., Kwan, M. A., Loh, P., & Sudakov, B. (2018). The random k‐matching‐free process. Random Structures and Algorithms. Wiley. https://doi.org/10.1002/rsa.20814
Krivelevich, Michael, Matthew Alan Kwan, Po‐Shen Loh, and Benny Sudakov. “The Random K‐matching‐free Process.” Random Structures and Algorithms. Wiley, 2018. https://doi.org/10.1002/rsa.20814.
M. Krivelevich, M. A. Kwan, P. Loh, and B. Sudakov, “The random k‐matching‐free process,” Random Structures and Algorithms, vol. 53, no. 4. Wiley, pp. 692–716, 2018.
Krivelevich M, Kwan MA, Loh P, Sudakov B. 2018. The random k‐matching‐free process. Random Structures and Algorithms. 53(4), 692–716.
Krivelevich, Michael, et al. “The Random K‐matching‐free Process.” Random Structures and Algorithms, vol. 53, no. 4, Wiley, 2018, pp. 692–716, doi:10.1002/rsa.20814.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1708.01054

Search this title in

Google Scholar