drevicko
Reputation
Top tag
Next privilege 250 Rep.
 Dec 3 comment How can a set contain itself? @AsafKaragila ah! good! It's a quirky notion, that of sets including other sets as elements - I guess my surprise (and perhaps the typo?) reflect a more prosaic notion asserting itself in the mental image - that of sets as subsets of each other :) Dec 2 comment How can a set contain itself? no infinite decreasing chains of inclusion?? What about rational number intervals? $x_n = [0,1+1/n]$? Jul 12 awarded Tumbleweed 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? 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 rejected edit on does a power law degree distribution imply graphs are sparse? Jun 12 revised does a power law degree distribution imply graphs are sparse? fixed typo