Return to Answer

deleted 1 character in body

Source Link

edited Aug 28, 2016 at 13:41

61.9k
11
160
302

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{(2Kn)^3}{6}$$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.

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{(2Kn)^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.

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.

Source Link

created Aug 28, 2016 at 10:47

fedja

61.9k
11
160
302

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{(2Kn)^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.