Expected Number of edges for a graph to have a Triangle?

Question

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

Answer 1

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.

Answer 2

@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