The matching process and independent process in random regular graphs and hypergraphs

DOI10.37236/10698zbMATH Open1506.05167arXiv1603.09232OpenAlexW3200241936MaRDI QIDQ2111785FDOQ2111785

Patrick Bennett, Deepak Bal

Publication date: 17 January 2023

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: In this note, we analyze two random greedy processes on sparse random graphs and hypergraphs with a given degree sequence. First we analyze the matching process, which builds a set of disjoint edges one edge at a time; then we analyze the independent process, which builds an independent set of vertices one vertex at a time. We use the differential equations method and apply a general theorem of Warnke. Our main contribution is to significantly reduce the associated systems of differential equations and simplify the expression for the final size of the matching or independent set.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• A natural barrier in random greedy hypergraph matching
• A note on the random greedy independent set algorithm
• Almost perfect matchings in random uniform hypergraphs
• Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
• Random hypergraph processes with degree restrictions

zbMATH Keywords

random regular graphindependent processmatching processrandom regular hypergraphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Enumeration in graph theory (05C30) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Random graphs.
• Title not available (Why is that?)
• Random parking, sequential adsorption, and the jamming limit
• Title not available (Why is that?)
• Title not available (Why is that?)
• On colouring random graphs
• Cliques in random graphs
• Perfect Matchings in Random r-regular, s-uniform Hypergraphs
• Title not available (Why is that?)
• Asymptotic enumeration of sparse uniform hypergraphs with given degrees
• Differential equations for random processes and random graphs
• Large independent sets in regular graphs of large girth
• Almost all regular graphs are hamiltonian
• Almost all cubic graphs are Hamiltonian
• Karp–Sipser on Random Graphs with a Fixed Degree Sequence
• Maximum matchings in regular graphs of high girth
• The cook-book approach to the differential equation method
• Controllability and matchings in random bipartite graphs
• The average performance of the greedy matching algorithm
• The Greedy Independent Set in a Random Graph with Given Degrees
• Title not available (Why is that?)
• Randomized greedy matching
• A natural barrier in random greedy hypergraph matching
• Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections
• Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
• Local algorithms, regular graphs of large girth, and random regular graphs
• Hamilton Cycles in Random Lifts of Directed Graphs
• Random Sequential Adsorption on Graphs

Cited In (4)

• Title not available (Why is that?)
• A stochastic matching model on hypergraphs
• On the random greedy \(F\)-free hypergraph process
• Random hypergraph processes with degree restrictions

This page was built for publication: The matching process and independent process in random regular graphs and hypergraphs

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