2
$\begingroup$

i want to compute the (Approximated) expected number of edges for a graph to have some triangles (loop with length 3)


i just solved a similar simpler problem:

Generate a random graph on $n$ vertices and probability $p$ for existence of each edge... what is the expected number of triangles? it will be $\frac{(np)^3}{6}$

with some calculus you can derive that if the number of edges is greater than $\frac{n\sqrt[3]6}{2}$ the expected number of triangles is greater than One.

but the Original problem is much harder than this case, However i think it must be some relation between the answer of these two problem. (is there?)

the question is How to solve the Original Problem?


i just wrote a code in MATLAB to simulate the behavior of the answer and the result is a function SomeHow asymptotic to $m=\frac{3n}{5}$ enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ Erm... Since $3/5<\sqrt[3]6/2$, you are getting triangles with high probability while the expected number is below $1$. This looks fishy, doesn't it? Or am I misunderstanding the question? $\endgroup$
    – fedja
    Aug 28, 2016 at 1:36
  • $\begingroup$ @fedja I want to know where 3/5 is come from? $\endgroup$
    – MR_BD
    Aug 28, 2016 at 1:55
  • 1
    $\begingroup$ That depends on how you simulate. Assuming that you just fix $n$, throw in the edges independently at random until you get the first triangle at the $m$-th throw and then take the average of the resulting $m$, you would get about $4/5$. Apparently, you are doing something else, but I cannot figure out what exactly. Can you be more specific about how you run your simulations? $\endgroup$
    – fedja
    Aug 28, 2016 at 2:35
  • $\begingroup$ @fedja I exactly simulate the way you said, but I want a theoretical solution for finding the coefficient of n $\endgroup$
    – MR_BD
    Aug 28, 2016 at 8:08
  • 1
    $\begingroup$ Then it is nearly 4/5 fair and square both theoretically and empirically. Check your program for errors and meanwhile I'll post the argument. $\endgroup$
    – fedja
    Aug 28, 2016 at 10:08

2 Answers 2

6
$\begingroup$

Here is a sketch. Choose a big constant $K$ and put in $Kn$ edges at random. That is essentially the same as to consider the random graph with the edge probability $p=2K/n$. The typical (in all senses of this word, the law of large numbers is on our side as $K\to+\infty$) number of triangles is then $T=\frac{(2K)^3}{6}$. Now, in each typical configuration, let us look at what the average $m$ is going to be if we average over all orders in which we put the edges in. Note that the probability of the event that two triangles share an edge is of order $1/n$, so this event is negligible. Thus, we have essentially $T$ independent triples of edges and we are looking for the minimal time to complete at least one of them. This is essentially equivalent to the problem of evaluating $Kn \mathcal E\min_{t=1}^T(\max_{j=1}^3 x_{i,j})$ where $x_{i,j}$ are independent random points uniformly distributed on $[0,1]$. But the last distribution is easy to evaluate: $$ \mathcal P(\min\max\dots>x)=(1-\mathcal P(\max\dots\le x))^T=(1-x^3)^T\,, $$ so the desired expectation is about $Kn\int_0^1(1-x^3)^T\,dx\approx Kn\int_0^\infty e^{-Tx^3}\,dx=\frac K{\sqrt[3]T}\left(\int_0^\infty e^{-x^3}\,dx\right)n=Fn$ where $$ F=\frac{\sqrt[3]6}2\int_0^\infty e^{-x^3}\,dx=0.811325\dots\,. $$ Note that our approximations get more and more precise as $K$ grows, but as we gain in precision in the law of large numbers, we start slowly losing the precision in the independence assumption mainly because we start getting triangles with common sides. I leave it to you to figure out what the best $K$ is for any fixed (large) $n$ to minimize the combined error term.

$\endgroup$
5
  • $\begingroup$ Thanks for this brilliant idea... is there any other idea to deal with problems like this? the MinMax trick was awesome... can you remember some other problem that solved with that? $\endgroup$
    – MR_BD
    Aug 28, 2016 at 12:17
  • $\begingroup$ i Checked my Code and i didn't found any fault... is it possible that $|V|=300$ is not enough to reach 0.8 ? $\endgroup$
    – MR_BD
    Aug 28, 2016 at 12:18
  • $\begingroup$ Are you sure that $T=\frac{(2kn)^3}{6}$ ? i think $n$ must be Canceled... $\endgroup$
    – MR_BD
    Aug 28, 2016 at 12:20
  • 1
    $\begingroup$ @BD Yes, that was a typo :-). I edited. As to the code, I ran the simulations myself and got the result quite close to 4/5 starting with 20 or so (if anything, it was typically above 4/5 for small $n$ rather than below). So you definitely have an error. You should detect some non-existing triangles somewhere. If you want, you can post the code and I'll take a look. $\endgroup$
    – fedja
    Aug 28, 2016 at 13:45
  • $\begingroup$ Thank you... sorry , the code is not good looking $\endgroup$
    – MR_BD
    Aug 28, 2016 at 14:00
0
$\begingroup$

@fedja : Thanks for your Kindness. this is my Code. i'm not Expert in Programming So i'll be very pleased if you send me your code too, for me improve my Skills.

in Addition is there any good way to Depict the Graph in a figure? i plot the graph with random position for vertices and it is ambiguous...

i really enjoyed the MinMax Trick. is it a well-Known way for solving problems? is there some similar problem in your mind which can be solved this way?


thanks again.

the main code:

clc;

u=[];

for n=3:300

n

d=[];

for i=1:50

A=zeros(n,n);

A0=sparse(A);

c=0;

while haveTri(A0)==0

x=randi(n-1)+1;

y=randi(x-1);

if A0(x,y)==0

A0(x,y)=1;

A0(y,x)=1;

c=c+1;

end

end

d=[d c];

end

u=[u mean(d)];

end

figure(2);

bar(u);


haveTri Function:

function bou= haveTri(I)

M=sparse(I);

S=M*M;

T=M.*S;

if nnz(T)>0

bou=1;

else

bou=0;

end

return

$\endgroup$
5
  • 1
    $\begingroup$ Aha, here is the problem: you shouldn't put anything on the diagonal $x=y$ and you never prevent this explicitly, as far as I can tell (+1 on the x assignment is totally ridiculous and does nothing ("random plus one" is still just "random"). So, you stop if you either have a triangle, or you get at least one diagonal entry and an edge on the corresponding vertex. The second case is what is driving you down, so, remove +1 and replace "if A0(x,y)==0" with "if A0(x,y)==0 & x!=y" (or whatever is the right syntax in Maple; I usually use C), and you'll be fine. $\endgroup$
    – fedja
    Aug 28, 2016 at 15:25
  • 1
    $\begingroup$ Actually, not even an edge is needed: just one non-zero diagonal entry stops the process. $\endgroup$
    – fedja
    Aug 28, 2016 at 15:34
  • $\begingroup$ @fedja I prevent the diagonal ones. x=randi(n-1)+1 and y=randi(x-1) So x begins at 2 and y is at most x-1 ... So all ones is above the diagonal... $\endgroup$
    – MR_BD
    Aug 28, 2016 at 16:26
  • 1
    $\begingroup$ Sorry, I misread that (alas, it will soon be time when I will need glasses to read...). But then it creates another obvious error: the distribution you create this way is not uniform on edges. Indeed, the probability of the edge $x-y$ to be added is about $1/n(x-1)$ instead of the correct $2/n(n-1)$. So you get rather heavy on edges with small indices, which also significantly increases the chance to create a triangle somewhere. $\endgroup$
    – fedja
    Aug 28, 2016 at 17:04
  • $\begingroup$ @fedja Oooops. Yes. That's it... Dear fedja: a Big Thanks For Your Kindness... i really enjoyed talking to you... BEST WISHES $\endgroup$
    – MR_BD
    Aug 28, 2016 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.