Upper bound on Independence Number of Random Regular Graph with degree $\Theta(\sqrt{|V|} \log^2 |V|)$

Question

Let $G=(V,E)$ be a random $\Delta$-regular graph with $\Delta \in \Theta(\sqrt{|V|} \log^2 |V|)$. I'm analysing an algorithm having asymptotic running time crucially depending on the Independence Number of such a $G$.

Question
Which is the best known upper bound on the Indipendence Number $\alpha(G)$ of such a so dense $G$?

The closest references I've found are:

1. The Independence Ratio of Regular Graphs by Béla Bolobás, October 1981. Here there is no random restriction, and the degree is considered to be a constant. But at top of page $4$ it is written that for a general $\Delta$ relation the Independence Number is asymptotically upper bounded by $\frac{2 \log \Delta}{\Delta}|V|$. This alone should nail down the question. But see below.
2. This presentation where, at slide 16, it is said that $\alpha(G) = \frac{2 \log \Delta}{\Delta}|V|(1+O(\xi))$ is asymptotically almost surely satisfied, where $\xi \to 0$ as $\Delta \to \infty$. To be noted that such slide says "Fix $\Delta \geq 3$...", the verb "to fix" seems to suggest that $\Delta$ is a constant. Such slide cites the result here below.
3. On the Independence and Chromatic Numbers of Random Regular Graphs by A. M. Frieze and T. Łuczak, May 1988. From the very abstract, it is already clear that they allow $\Delta$ to grow with $|V|$. However: for their result to hold, they require that $\Delta \in o(|V|^\theta)$ where $\theta < \frac{1}{3}$. Such requirement is clearly false in my case. Does it mean that the general $\Delta$ mentioned by Bolobás is not as general as to encompass the $\Theta(\sqrt{|V|} \log^2 |V|)$ case...? For if it encompasses it (as I hope), then why Frieze and Łuczak would have proven a result less powerful than the result already proven $7$ years before by Bolobás? This confusion makes me asymptotically almost sure that I'm missing something here.

Answer 1

I don't think the Bollobás paper asserts the bound on the independence number; rather, it seems to me that it asserts that for any given maximum degree $\Delta$ and lower bound on the girth $g$, there exists graphs of degree at most $\Delta$ and girth at least $g$ with independence ratio at most $2\log \Delta/\Delta$. In contrast, as you mention, the Frieze and Łuczak paper seems to give concentration of random $\Delta$-regular graphs that holds for $\Delta=o(n^{1/3})$, so that the desired upper bound holds with probability $1-o(1)$. This result is thus incomparable to the Bollobás paper, I think.

For your specific application, I think one can give an upper bound of roughly $\alpha(G)\leq O(n/\sqrt{\Delta})=\tilde{O}(n^{3/4})$ that holds with probability $1-o(1)$ (in fact, at least inverse polynomial error probability). I have no idea if this bound is closer to the truth for this regime, and this is of course much weaker than the bound that you want (note that no bound better than $\tilde{O}(n^{1/2})$ is possible anyway, for any $\Delta$-regular graph with $\Delta=\tilde{O}(n^{1/2})$-here, I'm using the tilde notation to mean up to logarithmic factors, in either direction).

Here's two ways that I hope work to get this bound: one is to note that the Frieze and Łuczak paper upper bound does not seem to rely on the constant degree restriction. In particular, just mimicking their proof of the upper bound (which is by far the easier direction in their concentration result), it seems to me like everything should go through to show that the probability of having an independent set of size greater than $\tilde{O}(n^{3/4})$ is $1-o(1)$. The reason their bound degrades this much when the degree is not constant is because it incurs a $e^{\Delta^2}$ loss when moving between simpler random graph models.

Another way to get it is to use some recent high-powered results that show that if $\Delta\to \infty$ with $n$ but $\Delta=o(n^{1-\epsilon})$ for some fixed $\epsilon>0$, then the spectral radius of the adjacency matrix (excluding the trivial eigenvalue $\Delta$) is $O(\sqrt{\Delta})$ with probability $1-o(1)$ (where the constant depends on $\epsilon$, but not $\Delta,n$). If $\lambda=\lambda(G):=\max\{\vert \lambda_2(G)\vert,\vert \lambda_n(G)\vert\}$ is the second largest eigenvalue of the adjacency matrix of a graph $G$, Hoffman's bound asserts that for a $\Delta$-regular graph on $n$ vertices: \begin{equation} \alpha(G)\leq \frac{\lambda}{\Delta-\lambda}n. \end{equation} For $\Delta=\tilde{O}(n^{1/2})$ and using the estimate above gives with probability $1-o(1)$ that $\alpha(G)\leq O(n/\sqrt{\Delta}) = \tilde{O}(n^{3/4})$.