Premium
Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
Author(s) -
Nie Jiaxi,
Verstraëte Jacques
Publication year - 2021
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.20994
Subject(s) - mathematics , girth (graph theory) , combinatorics , bounded function , greedy algorithm , randomized algorithm , discrete mathematics , algorithm , mathematical analysis
In this paper, we consider a randomized greedy algorithm for independent sets in r ‐uniform d ‐regular hypergraphs G on n vertices with girth g . By analyzing the expected size of the independent sets generated by this algorithm, we show that α ( G ) ≥ ( f ( d , r ) − ϵ ( g , d , r ) ) n , where ϵ ( g , d , r ) converges to 0 as g → ∞ for fixed d and r , and f ( d , r ) is determined by a differential equation. This extends earlier results of Garmarnik and Goldberg for graphs [8]. We also prove that when applying this algorithm to uniform linear hypergraphs with bounded degree, the size of the independent sets generated by this algorithm concentrate around the mean asymptotically almost surely.