"sparse graphs are locally tree-like" - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T12:10:34Z http://mathoverflow.net/feeds/question/55727 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/55727/sparse-graphs-are-locally-tree-like "sparse graphs are locally tree-like" eddddd84 2011-02-17T12:37:31Z 2012-03-12T14:27:40Z <p>I would like to be able to state with confidence that sparse graphs (graphs with small numbers of edges) are locally tree-like (they have few short cycles). Apparently "Sparse graphs are locally tree like in the sense that the typical size of loops is O(N)" - see citation below. Here I am pretty sure "N" is |V|, the number of nodes. But I can't find any proof or formal statement of this. </p> <p>I am interested in "most" graphs, not all of them, so if my understanding is right this is not a question of extremal graph theory. For example, I would like to be able to say something like: if |E| = O(|V|) then most graphs have girth O(|V|), or most loops have length O(|V|). </p> <p>[Macris 2006, Applications of correlation inequalities to low density graphical codes, www.springerlink.com/index/3416607227705N33.pdf]</p> http://mathoverflow.net/questions/55727/sparse-graphs-are-locally-tree-like/55738#55738 Answer by Aaron Meyerowitz for "sparse graphs are locally tree-like" Aaron Meyerowitz 2011-02-17T14:32:23Z 2011-02-17T14:50:57Z <p>I think you would need a condition something like $|E|&lt;(1+(1-\epsilon)\ln(V))V$. If $|E|=3|V|$ then it could be that every vertex is on $6$ $3$-cycles. That is only one such graph but I would expect the girth would be low. If the graph is regular of degree $3$ (so $|E|=\frac{3}{2}|V|$ ) then every vertex is on a cycle of length shorter than <code>$\log_2(V)$</code>.</p> <p>If I recall correctly, a random tree has expected diameter less than $4\sqrt{V},$ so the expected girth of a graph with $|V|=|E|$ would be $O(\sqrt{V}).$</p> http://mathoverflow.net/questions/55727/sparse-graphs-are-locally-tree-like/55763#55763 Answer by Kevin P. Costello for "sparse graphs are locally tree-like" Kevin P. Costello 2011-02-17T18:16:09Z 2011-02-17T18:16:09Z <p>I don't believe you can say that "most" graphs in this range have small girth, but there is a sense in which you can say they have few short cycles. For example, if you consider the model of random regular graphs of degree $d$ (graphs chosen uniformly from all $d$ regular graphs on $n$ vertices), and let $X_i$ denote the number of cycles of length $i$, then Bollobás and Wormald independently showed that the $X_i$ behaved asymptotically as independent Poisson variables with mean $(d-1)^i/(2i)$. </p> <p>In other words: There's a positive probability that a graph contains each of $3$-cycles, $4$-cycles, etc. Because these events are asymptotically independent, "most" $d-$regular graphs have bounded girth. On the other hand, the number of cycles of each fixed length on average remains bounded even as the size of the graph tends to infinity. So if I fix a single vertex and look in the neighborhood of that vertex, I have to look at farther and farther distance before I see any cycles at all. (But not too far...as Louigi noted, we can't expect to go much past the $\log n$ diameter of the graph). This is the "locally" part of "locally tree-like". </p> <p>A similar situation should hold for Erdős–Rényi graphs like the ones mentioned in Louigi's comment.</p> http://mathoverflow.net/questions/55727/sparse-graphs-are-locally-tree-like/55793#55793 Answer by cscjb for "sparse graphs are locally tree-like" cscjb 2011-02-17T23:12:10Z 2011-02-17T23:12:10Z <p>Your question fits into the area of random graphs, rather than extremal graph theory; and also expander graphs are relevant.</p> <p>As mentioned previously, Erdos-Renyi graphs are a good and simple model for random graphs. For example $G_{n,p}$ has $n$ vertices and each edge is independently randomly determined to exist with probability $p$.</p> <p>If you're talking about sparse graphs, you have to quantify how sparse. Say, for example, $p = \frac{\log n}{n}$? Above a certain point (Alon and Spencer, "The Probabilistic Method", will have many details) there is essentially a single "giant component" to the graph. Below that, there is a transition (which they also understand in detail) and then everything should be a tree below that.</p> <p>Expander graphs (there are many constructions) are typically sparse graphs which however are sufficiently connected that a random walk mixes rapidly. With expanders there should be a result about the typical cycle size and distribution of cycles by length, compared to the second eigenvalue of the Laplacian of the graph, which governs its expansion.</p> <p>It appears you're looking at LDPC codes, whose vertices have (if I recall correctly from undergrad days) edges independently chosen at random, with each vertex choosing a number $d$ as its total number of edges, where $d$ comes from some distribution chosen to maximize efficiency as a code. Mitzenmacher, Luby, and others were involved in their creation and have analyzed the efficiency extensively. "Digital Fountain" is/was a company doing this.</p> <p>LDPC codes offer a bit of independence if they are as described, but locally the edge probabilities will be correlated because of the distribution of $d$.</p> <p>It might be possible to use Janson's inequality (Ch8 of Alon and Spencer) to analyze this, as long as you're in the situation where there are no "negatively correlated" pairs of probabilities in your sum. It only uses the second (and first) probability moments.</p> <p>LDPC codes are probably good expanders, so you could use bounds from expander graph literature if true.</p> <p>Off the top of my head, that's where this problem fits ... maybe I'll be able to fill in more details for some of this later.</p> http://mathoverflow.net/questions/55727/sparse-graphs-are-locally-tree-like/90989#90989 Answer by Francesc Font-Clos for "sparse graphs are locally tree-like" Francesc Font-Clos 2012-03-12T14:27:40Z 2012-03-12T14:27:40Z <p>I think the typical loop-length goes like $\log(N)$ rather than $N$...</p> <p>if $\langle k \rangle$ is the average degree, the number of $l$-distant neighbours is approx $\langle k \rangle^l$, and hence when $k^l=N$ we expect to have a loop, so $l \approx \log(N)/\log(\langle k \rangle)$</p>