A do-it-yourself random graph result

May 21st, 2008 ~ Posted in: Mathematics

By way of motivation, if I gave you the graph

z1 = (0,0); z2 = (0,2cm); z3 = (2cm,4cm); z4 = (2cm,2cm); z5 = (2cm,0); z6 = (4cm,2cm); pickup pencircle scaled 2; draw z[1]--z[2]--z[3]--z[4]--z[5]--cycle; draw z[2]--z[4]--z[6]; for i=1 upto 10: draw z[i] withcolor .1 white withpen pencircle scaled 6; endfor

and asked you to identify a relationship between M,n so that a graph with n vertices and M edges is guaranteed to contain it, how would you approach this? Here’s one surprisingly simple approach:

Let G(n,M) be the set of graphs with vertices 1 through n and M edges and introduce the uniform probability P_{M} on G(n,M). Call Q a property of a random matrix if G \in Q and H \simeq G implies H \in Q. A property is increasing if G \in Q and G \subset H implies H \in Q also.

Show that if M_1 < M_2 and Q is increasing then P_{M_1}(Q) \leq P_{M_2}(Q). Now show that in fact P_s(Q) \geq \frac{s!}{(s-k)!} P_{s-k}(Q) . (at least I think this is correct).

With regards to the original problem, this inequality implies some pretty interesting and perhaps nontrivial results: e.g. if I recall correctly, there’s some basic result saying if the average valency of a graph is large enough, it must contain a triangle– this potentially offers a method of generalizing this idea for arbitrary subgraphs.

Mathematics ~

2 Responses to “A do-it-yourself random graph result”

  • 1. Stephen
    May 21st, 2008 at 5:32 pm

    I agree: at some point, s is sufficiently large to guarantee P_s(Q) >= 1. But to be relevant, you still have to show that this is better than the trivial bound (e.g. s = (n+1)*n/2 ), right?

  • 2. Alex
    May 22nd, 2008 at 12:06 pm

    As Mike pointed out P_s(Q) >= 1 doesn’t make sense, so I don’t think the interpretation of the result is that straightforward.

This entry was posted on Wednesday, May 21st, 2008 at 4:08 pm and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply