10
$\begingroup$

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.

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|)$.

N. Macris, Applications of correlation inequalities to low density graphical codes, The European Physical Journal B - Condensed Matter and Complex Systems, 2006; or the arXiv version

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ I think N is $\log_2 |V|$, or something like that, in that paper. They consider binary vectors of length $N$. Furthermore, "most" sparse graphs have logarithmic diameter (say, random regular graphs of constant degree $d \geq 3$, or the giant component of Erdos-Rényi random graphs with $p=c/n$ and $c>1$ a constant), rather than linear. $\endgroup$
    – Louigi Addario-Berry
    Commented Feb 17, 2011 at 14:34
  • $\begingroup$ [Thanks to everyone who has answered or commented - I am going to need to take some time to think about these answers, but they look very helpful.] $\endgroup$
    – user13038
    Commented Feb 21, 2011 at 16:47

4 Answers 4

Reset to default
6
$\begingroup$

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)$.

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".

A similar situation should hold for Erdős–Rényi graphs like the ones mentioned in Louigi's comment.

Improve this answer
$\endgroup$
4
$\begingroup$

I think you would need a condition something like $|E|<(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 $\log_2(V)$.

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}).$

Improve this answer
$\endgroup$
3
$\begingroup$

Your question fits into the area of random graphs, rather than extremal graph theory; and also expander graphs are relevant.

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$.

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.

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.

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.

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$.

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.

LDPC codes are probably good expanders, so you could use bounds from expander graph literature if true.

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.

Improve this answer
$\endgroup$
1
$\begingroup$

I think the typical loop-length goes like $\log(N)$ rather than $N$...

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)$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .