Bounds on the independence ratio of random regular graphs

You can use this page to compute the lower bounds on the independence ratio of random regular graphs given by the paper:
Boosted second moment method in random regular graphs
by Balázs Gerencsér and Viktor Harangi.

Hit 'Go' and compute our lower bound for a specific degree deg ≤ 500,000. First the density of the "Markovian" independent set is computed, then the density of the augmented independent set (which is our best lower bound). For comparison, the 1-RSB upper bound is also displayed (which is actually conjectured to be sharp for deg ≥ 20). The optimality percentage shows the relative size of our lower bound compared to the upper bound.

Tick the box show_plot to visually confirm that the required condition of the second moment method is satisfied by checking that the local maximum corresponding to the independent coupling (red dot on the plot) is the global maximum of the plotted function. Note that the plot is trimmed: the function is not plotted where the function value is more than some ε below the red dot.

Range of degrees

Hit 'Go' to compute our lower bounds for a range of degrees.

Thin independent sets

We say that an independent set A is t-thin if every vertex outside A has at most t neighbors in A. Such thin independent sets can be used to prove the existence of star decompositions.

Hit 'Go' to compute the density of t-thin independent sets.