Geodesic
The matching process and independent process in random regular graphs and hypergraphs
Deepak Bal1 ; Patrick Bennett
1Montclair State University
The electronic journal of combinatorics, Tome 30 (2023) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/10698
Classification : 05C70, 05C65, 05C80, 05C85, 05C30
Mots-clés : matching process, independent process, random regular graph, random regular hypergraphs

Deepak Bal  1   ; Patrick Bennett 

1 Montclair State University 
@article{10_37236_10698,
     author = {Deepak Bal and Patrick Bennett},
     title = {The matching process and independent process in random regular graphs and hypergraphs},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {1},
     doi = {10.37236/10698},
     zbl = {1506.05167},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10698/}
}
TY  - JOUR
AU  - Deepak Bal
AU  - Patrick Bennett
TI  - The matching process and independent process in random regular graphs and hypergraphs
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10698/
DO  - 10.37236/10698
ID  - 10_37236_10698
ER  - 
%0 Journal Article
%A Deepak Bal
%A Patrick Bennett
%T The matching process and independent process in random regular graphs and hypergraphs
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10698/
%R 10.37236/10698
%F 10_37236_10698
Deepak Bal; Patrick Bennett. The matching process and independent process in random regular graphs and hypergraphs. The electronic journal of combinatorics, Tome 30 (2023) no. 1. doi: 10.37236/10698

Cité par Sources :