Premium
Large deviations of the greedy independent set algorithm on sparse random graphs
Author(s) -
Kolesnik Brett
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21064
Subject(s) - rate function , mathematics , function (biology) , simple (philosophy) , greedy algorithm , set (abstract data type) , random graph , combinatorics , algorithm , random function , set function , independent set , large deviations theory , discrete mathematics , random variable , mathematical optimization , computer science , graph , statistics , philosophy , epistemology , evolutionary biology , biology , programming language
We study the greedy independent set algorithm on sparse Erdős–Rényi random graphs G ( n , c / n ) . A large deviation principle was recently established by Bermolen et al. in 2020, however, the proof and rate function are somewhat involved. Upper bounds for the rate function were obtained earlier by Pittel in 1982. Using discrete calculus, we identify the optimal trajectory realizing a given large deviation and obtain the rate function in a simple closed form. In particular, we show that Pittel's bounds are sharp. The proof is brief and elementary. We think the methods presented here will be useful in analyzing the tail behavior of other random processes.