4
$\begingroup$

Wikipedia says that "a dense graph is a graph in which the number of edges is close to the maximal number of edges." and "The maximum number of edges for an undirected graph is $|V|(|V|-1)/2$". Then why do even use $ |E| = \Theta (|V|^2)$?, understand that $\Theta$ is the correct(tightest) bound in asymptomatic notation. It seems to me that $|E| = \Theta (|V|^2)$ can never happen, so why do we use it?

$\endgroup$
4
$\begingroup$

Note that asymptotic bounds only apply to infinite sequences.

In this case, $|E| = \Theta(|V|^2)$ applies to an implicit infinite sequence of graphs $G_i=(V_i,E_i)$, meaning that there are two positive constants $c,c'$ such that, $c\cdot|V_i|^2 \leq |E_i| \leq c'\cdot|V_i|^2$ whenever $i$ is large enough.

This constraint can be satisfied. For every $i\in \mathbb N$, take $G_i$ to be the complete graph on $\{1,\ldots, i\}$. Hence, $G_i$ has exactly $i\cdot(i-1)/2$ edges. For large enough $i$, we have $$ \frac{1}{4}i^2 \leq \frac{i\cdot(i-1)}{2} \leq \frac{1}{2}i^2 $$ So, we can say that $|E| = \Theta(|V|^2)$.

Another sequence could be constructed taking "almost complete" graphs, where we remove one edge from each complete graph $G_i$ in the previous sequence. This would still satisfy the bound.

We could even remove, say, $100*i$ edges from each $G_i$ (when possible) and still satisfy the bound. This is because we only care about $|E_i|$ growing with "quadratic speed".

$\endgroup$
1
  • 1
    $\begingroup$ Balanced complete bipartite graphs $K_{\lceil n/2\rceil,\lfloor n/2\rfloor}$ (with about $n^2/4$ edges) are a good example to show that there are dense graphs that aren't just "cliques with a few edges removed". $\endgroup$ – David Richerby Jan 14 '19 at 16:50
4
$\begingroup$

You're absolutely right that $\Theta$ is the tightest asymptotic bound. But it's still asymptotic, and that means that we don't care about constant factors or terms of lower degree: when $n$ (or $v$ or whatever) gets big enough, the smaller terms become negligible.

In this case, $\frac{v(v-1)}{2} = \frac{1}{2} v^2 + \frac{-1}{2} v$. So removing the constant factors and lower terms leaves us with $v^2$.

$\endgroup$
4
  • 1
    $\begingroup$ I don't understand your last paragraph. It doesn't make sense to use $\Theta$ on a single graph anyway, since there's nothing to go to infinity. But $\Theta$ absolutely includes a lower bound. $\endgroup$ – David Richerby Jan 14 '19 at 15:16
  • $\begingroup$ @DavidRicherby Sorry, let me rephrase: using $\Theta$ implies that you can put a lower bound on how many edges are in a graph, in terms of the number of vertices. But the lower bound is always zero. So I would use $O$, which is only concerned with the upper bound (and it is in fact bounded above in terms of the number of vertices). $\endgroup$ – Draconis Jan 14 '19 at 16:43
  • $\begingroup$ But asymptotic bounds don't apply to single graphs. We need to be talking about classes of graphs being dense and, in that case, we absolutely need to use $\Theta$ because it's precisely the lower-bound that defines density. If we just said "A class of graphs is dense if the $n$-vertex members of the class have $O(n^2)$ edges", then every class would be dense. $\endgroup$ – David Richerby Jan 14 '19 at 16:49
  • $\begingroup$ @DavidRicherby Ahh, I see what you mean, I misread the question. I thought they were saying the number of edges in a general simple undirected graph was $\Theta(n^2)$ (not specifically in a dense graph), which makes no sense because there isn't a lower bound there. $\endgroup$ – Draconis Jan 14 '19 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.