The Kőnig graph process

DOI10.1002/RSA.20969zbMATH Open1454.05112arXiv1906.04806OpenAlexW3003849163MaRDI QIDQ3386537FDOQ3386537

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)

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?

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

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

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)

Cites Work

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

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)