Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth

DOI10.1002/RSA.20994MaRDI QIDQ6074650zbMATH OpenOpenAlexFDO

Authors Jiaxi Nie, J. Verstraëte

Publication date 12 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphs with large girthindependent setsrandomized greedy algorithm

Mathematics Subject Classification ID

Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

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 $alpha(G)geq(f(d,r)-epsilon(g,d,r))n$, where $epsilon(g,d,r)$ converges to $0$ as $gightarrowinfty$ for fixed $d$ and $r$, and $f(d,r)$ is determined by a differential equation. This extends earlier results of Gamarnik and Goldberg for graphs. 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.

Recommendations

• A note on the random greedy independent set algorithm
• Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections
• Large independent sets in regular graphs of large girth
• Local algorithms, regular graphs of large girth, and random regular graphs
• Large independent sets in random regular graphs

Cites work

• A note on Ramsey numbers
• A note on the independence number of triangle-free graphs
• A note on the independence number of triangle-free graphs. II
• Extremal uncrowded hypergraphs
• scientific article; zbMATH DE number 3238721 (Why is no real title available?)
• scientific article; zbMATH DE number 7651059 (Why is no real title available?)
• Improved lower bounds on k‐independence
• Large independent sets in regular graphs of large girth
• New lower bounds for the independence number of sparse graphs and hypergraphs
• On uncrowded hypergraphs
• Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections
• The probabilistic method

Cited in

(11)

• The matching process and independent process in random regular graphs and hypergraphs
• A note on the random greedy independent set algorithm
• Random iteration algorithm for graph-directed sets
• scientific article; zbMATH DE number 4149905 (Why is no real title available?)
• Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections
• Experimental and Efficient Algorithms
• Greedy maximal independent sets via local limits
• The low-degree hardness of finding large independent sets in sparse random hypergraphs
• Independent sets in hypergraphs
• Combinatorics. Abstracts from the workshop held January 4--9, 2026
• A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs

This page was built for publication: Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth

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