<p>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 <span class="math-container">$\Delta$</span> and lower bound on the girth <span class="math-container">$g$</span>, there <em>exists</em> graphs of degree at most <span class="math-container">$\Delta$</span> and girth at least <span class="math-container">$g$</span> with independence ratio at most <span class="math-container">$2\log \Delta/\Delta$</span>. In contrast, as you mention, the Frieze and Łuczak paper seems to give <em>concentration</em> of random <span class="math-container">$\Delta$</span>-regular graphs that holds for <span class="math-container">$\Delta=o(n^{1/3})$</span>, so that the desired upper bound holds with probability <span class="math-container">$1-o(1)$</span>. This result is thus incomparable to the Bollobás paper, I think.</p>
<p>For your specific application, I think one can give an upper bound of roughly <span class="math-container">$\alpha(G)\leq O(n/\sqrt{\Delta})=\tilde{O}(n^{3/4})$</span> that holds with probability <span class="math-container">$1-o(1)$</span> (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 <span class="math-container">$\tilde{O}(n^{1/2})$</span> is possible anyway, for any <span class="math-container">$\Delta$</span>-regular graph with <span class="math-container">$\Delta=\tilde{O}(n^{1/2})$</span>-here, I'm using the tilde notation to mean up to logarithmic factors, in either direction).</p>
<p>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 <span class="math-container">$\tilde{O}(n^{3/4})$</span> is <span class="math-container">$1-o(1)$</span>. The reason their bound degrades this much when the degree is not constant is because it incurs a <span class="math-container">$e^{\Delta^2}$</span> loss when moving between simpler random graph models.</p>
<p>Another way to get it is to use <a href="https://arxiv.org/abs/1610.01765" rel="nofollow noreferrer">some recent high-powered results</a> that show that if <span class="math-container">$\Delta\to \infty$</span> with <span class="math-container">$n$</span> but <span class="math-container">$\Delta=o(n^{1-\epsilon})$</span> for some fixed <span class="math-container">$\epsilon&gt;0$</span>, then the spectral radius of the adjacency matrix (excluding the trivial eigenvalue <span class="math-container">$\Delta$</span>) is <span class="math-container">$O(\sqrt{\Delta})$</span> with probability <span class="math-container">$1-o(1)$</span> (where the constant depends on <span class="math-container">$\epsilon$</span>, but not <span class="math-container">$\Delta,n$</span>). If <span class="math-container">$\lambda=\lambda(G):=\max\{\vert \lambda_2(G)\vert,\vert \lambda_n(G)\vert\}$</span> is the second largest eigenvalue of the adjacency matrix of a graph <span class="math-container">$G$</span>, Hoffman's bound asserts that for a <span class="math-container">$\Delta$</span>-regular graph on <span class="math-container">$n$</span> vertices:
<span class="math-container">\begin{equation}
\alpha(G)\leq \frac{\lambda}{\Delta-\lambda}n.
\end{equation}</span>
For <span class="math-container">$\Delta=\tilde{O}(n^{1/2})$</span> and using the estimate above gives with probability <span class="math-container">$1-o(1)$</span> that <span class="math-container">$\alpha(G)\leq O(n/\sqrt{\Delta}) = \tilde{O}(n^{3/4})$</span>.</p>

CC BY-SA 4.0
2020-11-27T13:58:20.170Z
Thanks a lot for clarifying, much for me to ponder and digest... :-)
Giorgio Camerani
CC BY-SA 4.0
2020-12-01T14:04:44.540Z
No problem, I hope this is helpful! Also, sorry, I made a small typo: in the third paragraph, I meant to write "the probability of having an independent set of size greater than $\tilde{O}(n^{3/4})$ is $o(1)$," not "$1-o(1)$." (I would just edit it, but don't want to unnecessarily bump this question to the top for such a small thing).
Jason Gaitonde
CC BY-SA 4.0
2020-11-26T20:39:10.310Z
2020-11-26T20:39:10.310Z
Jason Gaitonde
<p>Let <span class="math-container">$G=(V,E)$</span> be a random <span class="math-container">$\Delta$</span>-regular graph with <span class="math-container">$\Delta \in \Theta(\sqrt{|V|} \log^2 |V|)$</span>. I'm analysing an algorithm having asymptotic running time crucially depending on the Independence Number of such a <span class="math-container">$G$</span>.</p>
<blockquote>
<p><strong>Question</strong><br />
Which is the best known upper bound on the Indipendence Number <span class="math-container">$\alpha(G)$</span> of such a so dense <span class="math-container">$G$</span>?</p>
</blockquote>
<p>The closest references I've found are:</p>
<ol>
<li><a href="https://pdfs.semanticscholar.org/1a1e/68c0f7e9e2c59a50d0e3a2a5ef0eca6f6441.pdf?_ga=2.176624993.533693271.1606382484-125339553.1587455411" rel="nofollow noreferrer">The Independence Ratio of Regular Graphs</a> 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 <span class="math-container">$4$</span> it is written that for a <em>general</em> <span class="math-container">$\Delta$</span> relation the Independence Number is asymptotically upper bounded by <span class="math-container">$\frac{2 \log \Delta}{\Delta}|V|$</span>. This alone should nail down the question. But see below.</li>
<li><a href="https://web.ma.utexas.edu/conferences/simons2016/Slides/Wormald.pdf?" rel="nofollow noreferrer">This presentation</a> where, at slide 16, it is said that <span class="math-container">$\alpha(G) = \frac{2 \log \Delta}{\Delta}|V|(1+O(\xi))$</span> is asymptotically almost surely satisfied, where <span class="math-container">$\xi \to 0$</span> as <span class="math-container">$\Delta \to \infty$</span>. To be noted that such slide says <em>&quot;Fix <span class="math-container">$\Delta \geq 3$</span>...&quot;</em>, the verb <em>&quot;to fix&quot;</em> seems to suggest that <span class="math-container">$\Delta$</span> is a constant. Such slide cites the result here below.</li>
<li><a href="https://www.sciencedirect.com/science/article/pii/009589569290070E" rel="nofollow noreferrer">On the Independence and Chromatic Numbers of Random Regular Graphs</a> by A. M. Frieze and T. Łuczak, May 1988. From the very abstract, it is already clear that they allow <span class="math-container">$\Delta$</span> to grow with <span class="math-container">$|V|$</span>. However: for their result to hold, they require that <span class="math-container">$\Delta \in o(|V|^\theta)$</span> where <span class="math-container">$\theta &lt; \frac{1}{3}$</span>. Such requirement is clearly false in my case. Does it mean that the <em>general</em> <span class="math-container">$\Delta$</span> mentioned by Bolobás is not as general as to encompass the <span class="math-container">$\Theta(\sqrt{|V|} \log^2 |V|)$</span> 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 <span class="math-container">$7$</span> years before by Bolobás? This confusion makes me asymptotically almost sure that I'm missing something here.</li>
</ol>

<reference-request><graph-theory><co.combinatorics><randomness><independent-set>
Upper bound on Independence Number of Random Regular Graph with degree $\Theta(\sqrt{|V|} \log^2 |V|)$
Giorgio Camerani
# Upper bound on Independence Number of Random Regular Graph with degree $\Theta(\sqrt{|V|} \log^2 |V|)$

(Asked by: username_0 on 2020-11-26)

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](https://pdfs.semanticscholar.org/1a1e/68c0f7e9e2c59a50d0e3a2a5ef0eca6f6441.pdf?_ga=2.176624993.533693271.1606382484-125339553.1587455411) 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](https://web.ma.utexas.edu/conferences/simons2016/Slides/Wormald.pdf?) 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](https://www.sciencedirect.com/science/article/pii/009589569290070E) 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.

**Tags:** reference-request, graph-theory, co.combinatorics, randomness, independent-set

---

## 1 answers

### Answer by username_1 on 2020-11-26. Score: 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](https://arxiv.org/abs/1610.01765) 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})$.

> **Comments:**
> **username_0**: Thanks a lot for clarifying, much for me to ponder and digest... :-)  
> **username_1**: No problem, I hope this is helpful! Also, sorry, I made a small typo: in the third paragraph, I meant to write "the probability of having an independent set of size greater than $\tilde{O}(n^{3/4})$ is $o(1)$," not "$1-o(1)$." (I would just edit it, but don't want to unnecessarily bump this question to the top for such a small thing).  

---

