Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Let $G$ be the random graph $G(n,100/\sqrt n)$, i.e. it is a graph on $n$ vertices with each edge chosen randomly, independetly with probability $100/\sqrt n$.
How can I show that as $n\to\infty$, there exists a set of at least $k$ edge-disjoint triangles in the graph, and $k=\Omega(n^{3/2})$?
A well-known result says that a graph with $n$ vertices and average degree $d$ has an independent set of size $\frac{n}{d+1}$. To prove this, sort the vertices in random order and take as your independent set the set of vertices sorted before all their neighbors. The average size of the result is $$\sum_{i=1}^n \frac{1}{1 + \deg v_i} = \frac{n}{\operatorname{HM}\{1 + \deg v_i\}} \ge \frac{n}{\operatorname{AM}\{1 + \deg v_i\}} = \frac{n}{1+d}$$ where the inequality follows from the arithmetic-harmonic mean inequality.
In your case, a set of edge-disjoint triangles in $G$ is an independent set in the auxiliary graph $G^*$ whose vertices are triangles of $G$, and whose edges are pairs of triangles in $G$ sharing an edge.
If $G = G(n, 100/\sqrt n)$, then the expected number of vertices in $G^*$ and the expected number of edges are both $\mathcal O(n^{3/2})$. If both of these approximately match their expected values, then the average degree is $\mathcal O(1)$, and the result you want follows from the lemma above.
So all you have to do is prove concentration for the number of vertices and edges in $G^*$. This follows, respectively, from concentration for the number of copies of the following graphs in $G$:
Showing this is a standard exercise in the second moment method.
