128 reputation
18
bio website
location
age 47
visits member for 2 years, 10 months
seen Jul 9 at 21:42

Jul
12
awarded  Tumbleweed
Jul
9
revised Simplification of a power weighted alternating binomial sum
added extra term to the sum
Jul
5
revised Simplification of a power weighted alternating binomial sum
deleted 12 characters in body
Jul
5
asked Simplification of a power weighted alternating binomial sum
Jun
20
comment does a power law degree distribution imply graphs are sparse?
Great! You should add that it's known that $1/H^1_n\in O(1/{\log n})$, as we can find a lower bound linear in $\log n$, perhaps with references.. Maybe also worth noting that finding a similar lower bound for $H^\gamma_n$ with $1\lt\gamma\lt 2$ would resolve the question for those values. Year, needless attention to detail is my downfall! Perhaps I should return to maths ;)
Jun
19
comment does a power law degree distribution imply graphs are sparse?
Ok, so we're settled for $\gamma\ge 2$ and $\gamma = 1$. Care to add the results to the answer? (edits I make will probably not be accepted). There are probably similar results for $1\lt\gamma\lt 2$, based around an analysis of $O(1/H^\gamma_n)$ (a proof could probably be modelled on that for $\gamma=1$), but I'm satisfied with what we have already. Thx! It's been fun to put my head back in math mode for a moment :)
Jun
18
comment Determining the Asymptotic Order of Growth of the Generalized Harmonic Function?
Beware: the notation $H^{(r)}_n$ in the question is that used in wikipedia for Hyperharmonic Numbers. Wikipedia uses $H_{n,r}$ for harmonic numbers, and I've seen $H_n^r$ also (where $r$ is the exponent: $H_{n,r}:=\sum_{k=1}^n k^{-r}$
Jun
18
comment does a power law degree distribution imply graphs are sparse?
Apostol's Introduction to Analytic Number Theory, Theorem 3.2 (b) (ref'd here) gives an upper bound, but not a lower one...
Jun
18
comment does a power law degree distribution imply graphs are sparse?
Or maybe we can: mathhelpforum.com/calculus/…, rgmia.org/papers/v6n2/harmonic-ser.pdf and math.stackexchange.com/questions/620400/…
Jun
18
comment does a power law degree distribution imply graphs are sparse?
I think the $\gamma=1$ case has a problem: $H^1_n\in O(\log n)$ does not imply $1/H^1_n\in O(1/\log n)$. To be in $O(1/\log n)$ we need an upper bound $1/H^1_n\le M \frac{1}{\log n}$ for some $M$ (and $n\gt n_0$ for some $n_0$), and so a lower bound $H^1_n \ge M' \log n$ (eg: $M'=1/M$). It's not clear that we can do that.
Jun
17
awarded  Commentator
Jun
17
comment does a power law degree distribution imply graphs are sparse?
Oops! You're right, an extra $n$ snuck in for $\gamma=2$. I was thinking of a potential lower bound $H^\gamma_n\ge M\log n$ for some $M$ so $1/H_n\in O(1/\log n)$, but now that I think more, that seems unlikely.. Do you agree for $\gamma\gt 2$?
Jun
14
comment does a power law degree distribution imply graphs are sparse?
And for $\gamma=1$ we end up with $(n-1)/H_{n-1} \in O(n/\log n)$ (for that we need to lower bound $H_{n-1}$ with $\log n$, but I think we can, or no?). In summary, we would now have $\mathbb{E}[m] \in O(n), O(n^2\log n), O(n^2/ \log n)$ for $\gamma >2$, $\gamma=2$ and $\gamma=1$ respectively. Thoughts?
Jun
14
awarded  Informed
Jun
13
comment does a power law degree distribution imply graphs are sparse?
For $\gamma>2$, $\mathbb{E}[d(v)]$ converges as $n\rightarrow \infty$, so is in $O(1)$, or have I missed something?? For $\gamma=2$, it's as $H_{n-1}\in O(\log n)$ (I'm guessing we can't do much better there).
Jun
13
revised does a power law degree distribution imply graphs are sparse?
minor typo
Jun
12
awarded  Scholar
Jun
12
accepted does a power law degree distribution imply graphs are sparse?
Jun
12
comment does a power law degree distribution imply graphs are sparse?
Yes, $C(n)$ decreases monotonically, so in the inequality for $\mathbb{E}[d(v)]$, we can replace $C$ by its first term $C(2)=1$. I've edited the answer to accordingly. Thx (:
Jun
12
suggested suggested edit on does a power law degree distribution imply graphs are sparse?