drevicko
Reputation
Top tag
Next privilege 250 Rep.
 Dec3 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 :) Dec2 comment How can a set contain itself? no infinite decreasing chains of inclusion?? What about rational number intervals? $x_n = [0,1+1/n]$? Jul12 awarded Tumbleweed Jul9 revised Simplification of a power weighted alternating binomial sum added extra term to the sum Jul5 revised Simplification of a power weighted alternating binomial sum deleted 12 characters in body Jul5 asked Simplification of a power weighted alternating binomial sum Jun20 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 ;) Jun19 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 :) Jun18 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}$ Jun18 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... Jun18 comment does a power law degree distribution imply graphs are sparse? Jun18 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. Jun17 awarded Commentator Jun17 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$? Jun14 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? Jun14 awarded Informed Jun13 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). Jun13 revised does a power law degree distribution imply graphs are sparse? minor typo Jun12 awarded Scholar Jun12 accepted does a power law degree distribution imply graphs are sparse?