Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth. Issue 1 (19th January 2021)

• Record Type: Journal Article
• Authors: Nie, Jiaxi; Verstraëte, Jacques
• Is Part Of: Random structures & algorithms. Volume 59:Issue 1(2021)
• Page Start: 79
• Page End: 95
• Publication Date: 2021-01-19
• Subjects: hypergraphs with large girth -- independent sets -- randomized greedy algorithm; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20994
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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.