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


1 Answer 1


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

triangle and diamond subgraphs

Showing this is a standard exercise in the second moment method.

  • $\begingroup$ Thanks! I believe I managed to show that the expectation for number of vertices and number of edges in G* are both O(n^3/2) (without using the second moment method). What do you mean by "if both of these approx. match their expected value"? I think I'm missing a hint on how to use the second moment method here. $\endgroup$
    – Andrzej
    Apr 23, 2017 at 13:10
  • $\begingroup$ If $\operatorname{Var}[X] = o(\mathbb E[X]^2)$, then $X \sim \mathbb E[X]$ w.h.p.; this follows from Chebyshev's inequality. (See the fourth chapter of Alon and Spencer.) $\endgroup$ Apr 23, 2017 at 14:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .