The Kőnig graph process

DOI10.1002/RSA.20969MaRDI QIDQ3386537zbMATH OpenOpenAlexFDO

Authors Nina Kamčev, Michael Krivelevich, Natasha Morrison, Benny Sudakov

Publication date 5 January 2021

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.04806

zbMATH Keywords

matchingrandom graphperfect matchingvertex coverrandom process

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Say that a graph G has property $mathcalK$ if the size of its maximum matching is equal to the order of a minimal vertex cover. We study the following process. Set $$ and let $e_1,e_2,dots{e}_N$ be a uniformly random ordering of the edges of $K_n$, with $n$ an even integer. Let $G_0$ be the empty graph on $n$ vertices. For $mgeq0$, $G_{m+1}$ is obtained from $G_m$ by adding the edge $e_{m+1}$ exactly if $G_{m}cup{e}_{m+1}$ has property $mathcalK$. We analyse the behaviour of this process, focusing mainly on two questions: What can be said about the structure of $G_N$ and for which $m$ will $G_m$ contain a perfect matching?

Recommendations

• The random \(k\)-matching-free process
• Perfect matchings in random subgraphs of regular bipartite graphs
• Forbidden subgraphs and the Kőnig property
• Publication:5750892
• scientific article; zbMATH DE number 3950585

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3943863 (Why is no real title available?)
• scientific article; zbMATH DE number 3950585 (Why is no real title available?)
• Avoiding a giant component
• Concentration of Measure for the Analysis of Randomized Algorithms
• Dynamic concentration of the triangle-free process
• Freedman's inequality for matrix martingales
• Hamiltonicity thresholds in Achlioptas processes
• Hoeffding's inequality for supermartingales
• Introduction to Random Graphs
• Lower bounds for the size of random maximal \(H\)-free graphs
• On large matchings and cycles in sparse random graphs
• On the connectivity threshold of Achlioptas processes
• On the existence of a factor of degree one of a connected random graph
• On the random satisfiable process
• On the size of a random maximal graph
• Pseudo-random graphs
• Random Graph Processes with Degree Restrictions
• Random graphs.
• The early evolution of the \(H\)-free process
• The random \(k\)-matching-free process
• The random planar graph process
• The triangle-free process
• The triangle-free process and the Ramsey number \(R(3,k)\)

Cited in

(2)

• The Early Evolution of the Random Graph Process in Planar Graphs and Related Classes
• The random \(k\)-matching-free process

This page was built for publication: The Kőnig graph process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386537)