Keywords

1 Introduction

Graphs considered in this paper are undirected, finite and may have multiple edges. Given a graph \(G=(V,E)\) with vertex set \(V(G)=V\) and edge set \(E(G)=E\), for convenience, we often identify a triangle in G with its edge set. A subset of E is called a triangle cover if it intersects each triangle of G. Let \(\tau _t(G)\) denote the minimum cardinality of a triangle cover of G, referred to as the triangle covering number of G. A set of pairwise edge-disjoint triangles in G is called a triangle packing of G. Let \(\nu _t(G)\) denote the maximum cardinality of a triangle packing of G, referred to as the triangle packing number of G. It is clear that \(1\le \tau _t(G)/\nu _t(G)\le 3\) holds for every graph G. Our research is motivated by the following conjecture raised by Tuza [25] in 1981, and its weighted generalization by Chapuy et al. [7] in 2014.

Conjecture 1

(Tuza’s Conjecture [25]).\(\tau _t(G)/\nu _t(G)\le 2\) holds for every simple graph G.

To the best of our knowledge, the conjecture is still unsolved in general. If it is true, then the upper bound 2 is sharp as shown by \(K_4\) and \(K_5\) – the complete graphs of orders 4 and 5.

Related Work. The only known universal upper bound smaller than 3 was given by Haxell [14], who shown that \(\tau _t(G)/\nu _t(G)\le 66/{23} =2.8695...\) holds for all simple graphs G. Haxell’s proof [14] implies a polynomial-time algorithm for finding a triangle cover of cardinality at most 66/23 times that of a maximal triangle packing. Other results on Tuza’s conjecture concern with special classes of graphs.

Tuza [26] proved his conjecture holds for planar simple graphs, \(K_{5}\)-free chordal simple graphs and simple graphs with n vertices and at least \(7n^{2}/16\) edges. The proof for planar graphs [26] gives an elegant polynomial-time algorithm for finding a triangle cover in planar simple graphs with cardinality at most twice that of a maximal triangle packing. The validity of Tuza’s conjecture on the class of planar graphs was later generalized by Krivelevich [18] to the class of simple graphs without \(K_{3,3}\)-subdivision. Haxell and Kohayakawa [15] showed that \(\tau _t(G)/\nu _t(G)\le 2-\epsilon \) for tripartite simple graphs G, where \(\epsilon > 0.044\). Haxell, Kostochka and Thomasse [13] proved that every \(K_{4}\)-free planar simple graph G satisfies \(\tau _t(G)/\nu _t(G)\le 1.5\).

Regarding the tightness of the conjectured upper bound 2, Tuza [26] noticed that there exists infinitely many simple graphs G attaining the conjectured upper bound \(\tau _t(G)/\nu _t(G)=2\). Cui et al. [11] characterized planar simple graphs G satisfying \(\tau _t(G)/\nu _t(G)=2\); these graphs are edge-disjoint unions of \(K_4\)’s plus possibly some vertices and edges that are not in triangles. Baron and Kahn [2] proved that Tuza’s conjecture is asymptotically tight for dense simple graphs.

Fractional and weighted variants of Conjecture 1 were studied in literature. Krivelevich [18] proved two fractional versions of the conjecture: \(\tau _t(G)\le 2\nu ^{*}_t(G)\) and \(\tau ^{*}_t(G)\le 2\nu _t(G)\) , where \(\tau ^{*}_t(G)\) and \(\nu ^{*}_t(G)\) are the values of an optimal fractional triangle cover and an optimal fractional triangle packing of simple graph G, respectively. [16] proved if G is a graph with n vertices, then \(\nu _t^*(G)-\nu _t(G)=o(n^2)\).

We can regard the classic random graph models \(\mathcal {G}(n,p)\) and \(\mathcal {G}(n,m)\) as special graph classes, and we can also consider the probabilistic properties between \(\tau _t(G)\) and \(\nu _t(G)\). Bennett et al. [3] showed that \(\tau _t(G)\le 2 \nu _t(G)\) holds with high probability in \(\mathcal {G}(n,m)\) model where \(m\le 0.2403 n^{1.5}\) or \(m\ge 2.1243 n^{1.5}\). Relevant studies in random graph models were discussed in [1, 19, 24]. Other extensions related to Conjecture 1 can be found in [4,5,6, 8,9,10, 12, 17, 20,21,23].

Our Contributions. We consider Tuza’s conjecture on random graph, under two probability models \(\mathcal {G}(n,p)\) and \(\mathcal {G}(n,m)\).

  • Given \(0\le p\le 1\), under \(\mathcal {G}(n,p)\) model, \(\mathbf {Pr}(\{v_i,v_j\}\in G)=p\) for all \(v_i,v_j\) with these probabilities mutually independent. Our main theorem is following: If \(G\in \mathcal {G}(n,p)\) and \(p=\varOmega (1)\), then for any \( 0<\epsilon <1\), it holds that

    $$\mathbf {Pr}\left[ \tau _t(G)\le 1.5(1+\epsilon )\nu _t(G)\right] =1-o(1).$$

  • Given \(0\le m\le n(n-1)/2\), under \(\mathcal {G}(n,m)\) model, let G be defined by randomly picking m edges from all \(v_i, v_j\) pairs. Our main theorem is following: If \(G\in \mathcal {G}(n,m)\) and \(m=\varOmega (n^2)\), then for any \( 0<\epsilon <1\), it holds that

    $$\mathbf {Pr}\left[ \tau _t(G)\le 1.5(1+\epsilon )\nu _t(G)\right] =1-o(1).$$

The main content of the article is organized as follows: In Sect. 2, the theorem in \(\mathcal {G}(n,p)\) random graph model is proved; In Sect. 3, the theorem in \(\mathcal {G}(n,m)\) random graph model is proved; In Sect. 4, the conclusions are summarized and some future works are proposed. The appendix provides a list of mathematical symbols and classical theorems.

2 \(\mathcal {G}(n,p)\) Random Graph Model

In this section, we discuss the probability properties of graphs in \(\mathcal {G}(n,p)\). Given \(0\le p\le 1\), under \(\mathcal {G}(n,p)\) model, \(\mathbf {Pr}(\{v_i,v_j\}\in G)=p\) for all \(v_i,v_j\) with these probabilities mutually independent. Theorem 1 is our main result: If \(G\in \mathcal {G}(n,p)\) and \(p=\varOmega (1)\), then for any \( 0<\epsilon <1\), it holds that

$$\mathbf {Pr}\left[ \tau _t(G)\le 1.5(1+\epsilon )\nu _t(G)\right] =1-o(1).$$

The primary idea behind the theorem is as follows:

  • First, in Lemma 2, Lemma 3, we prove that \(\tau _t(G)\le (1+\epsilon )\frac{n(n-1)}{4}p\) holds with high probability by combining the Chernoff’s bounds technique;

  • Second, in Lemma 4, Lemma 6, we prove that \(\nu _t(G)\ge (1-\epsilon )\frac{n(n-1)}{6}p\) holds with high probability through combining the Chernoff’s bounds technique and the relationship between \(\nu ^*(G)\) and \(\nu _t(G)\) [16].

  • By using the previous two properties, Theorem 1 holds.

The following simple property will be used frequently in our discussions.

Lemma 1

Let A(n) and B(n) be two events related to parameter n. If \(\mathbf {Pr}[A(n)] = 1 - o(1)\), then \(\mathbf {Pr}[B(n)] \ge \mathbf {Pr}[B(n)|A(n)]-o(1)\) where \(o(1)\rightarrow 0\) as \(n \rightarrow \infty \).

Proof

This can be seen from the fact that \(\mathbf {Pr}[A]\cdot \mathbf {Pr}[B]=\mathbf {Pr}[B]-o(1)\ge \mathbf {Pr}[A\cap B]-o(1)\) and \(o(1)/\mathbf {Pr}[A]=o(1)\).

Denote the edge number of graph G as m. Let b(G) be the maximum number of edges of sub-bipartite in G. There are four basic properties of graph parameters. The first three holds in every graph, while the last one shows the boundary condition of triangle-free in \(\mathcal {G}(n,p)\).

Lemma 2

  1. (i)

    \(b(G)\ge m/2\) for every graph G.

  2. (ii)

    \(\tau _t(G)\le m/2\) for every graph G.

  3. (iii)

    \(\nu _t(G)\le m/3\) for every graph G.

  4. (iv)

    If \(G\in \mathcal {G}(n,p)\) and \(p=o(1/n)\), then G is triangle-free with high probability.

Proof

Suppose \(b(G)<m/2\) and the corresponding sub-bipartite is \(B=(V_1,V_2)\). Thus, there exists one vertex, without loss of generality, \(u\in V_1\) satisfies that \(d_B(u)<d_G(u)/2\). We can move vertex u from \(V_1\) to \(V_2\), and let \(\widetilde{B}=(\widetilde{V}_1,\widetilde{V}_2)\) where \(\widetilde{V}_1=V_1\backslash \{u\}, \widetilde{V}_2=V_2\cup \{u\}\). We have \(|E(\widetilde{B})|>|E(B)|=b(G)\), which contradicts with the definition of b(G). Therefore, statement (i) holds.

Statement (ii) follows from the definition of b(G) and the result of statement (i). Statement (iii) is trivial.

Applying Union Bound Inequality, Statement (iv) is due to

$$\mathbf {Pr}[G \text {~contains at least a triangle}]\le {{n}\atopwithdelims (){3}}\cdot p^3=o(1)$$

In view of Lemma 2(iv), we consider henceforth \(\mathcal {G}(n,p)\) with \(p=\varOmega (1/n)\). Under this condition, we give the following upper bounds for \(\tau _t(G)\) and \(\nu _t(G)\) with high probability.

Lemma 3

If \(G\in \mathcal {G}(n,p)\) and \(p=\varOmega (1/n)\), for any \( 0<\epsilon <1\), it holds that

$$\begin{aligned}&\mathbf {Pr}\left[ \tau _t(G)\le (1+\epsilon )\frac{n(n-1)}{4}p\right] =1-o(1). \end{aligned}$$
(1)
$$\begin{aligned}&\mathbf {Pr}\left[ \nu _t(G)\le (1+\epsilon )\frac{n(n-1)}{6}p\right] =1-o(1). \end{aligned}$$
(2)

Proof

For each edge e in complete graph \(K_n\), Let \(X_e\) be the random variable defined by: \(X_e=1\) if \(e\in E(G)\) and \(X_e=0\) otherwise. Then \(X_e\), \(e\in K_n\), are independent 0–1 variables, \(\mathbf{E}[X_e]=p\), \(m= \sum _{e\in K_n}X_e\) and \(\mathbf{E}[m]=n(n-1)p/2=\varOmega (n)\). By Chernoff’s Inequality, for any \(0<\epsilon <1\) we have

$$\begin{aligned} \mathbf {Pr}[m\ge (1+\epsilon )\mathbf{E}[m]]\le \exp \left( -\frac{\epsilon ^2\mathbf{E}[m]}{3}\right) =o(1). \end{aligned}$$

Thus, it follows from Lemma 2(ii) and (iii) that

$$\begin{aligned}&\mathbf {Pr}\left[ \tau _t(G)\le (1+\epsilon )\frac{n(n-1)}{4}p\right] \\ =~&\mathbf {Pr}\left[ 2\tau _t(G)\le (1+\epsilon )\frac{n(n-1)}{2}p\right] \\ \ge ~&\mathbf {Pr}\left[ m\le (1+\epsilon )\frac{n(n-1)}{2}p\right] \\ =~&\mathbf {Pr}\left[ m\le (1+\epsilon )\mathbf{E}(m)\right] \\ =~&1-o(1) \end{aligned}$$

Similarly,

$$\begin{aligned}&\mathbf {Pr}\left[ \nu _t(G)\le (1+\epsilon )\frac{n(n-1)}{6}p\right] \\ =~&\mathbf {Pr}\left[ 3\nu _t(G)\le (1+\epsilon )\frac{n(n-1)}{2}p\right] \\ \ge ~&\mathbf {Pr}\left[ m\le (1+\epsilon )\frac{n(n-1)}{2}p\right] \\ =~&1-o(1) \end{aligned}$$

proving the lemma.

Along a different line, we consider the probability result of the lower bounds of the fractional triangle packing \(\nu _t^*(G)\) as follows:

Lemma 4

If \(G\in \mathcal {G}(n,p)\) and \(p=\varOmega (1)\), then for any \( 0<\epsilon <1\), it holds that

$$\begin{aligned} \mathbf {Pr}\left[ \nu _t^*(G)\ge (1-\epsilon )\frac{n(n-1)p}{6}\right] =1-o(1). \end{aligned}$$

Proof

Consider an arbitrary edge \(uv\in K_n\). For each \(w\in V(G)\setminus \{u,v\}\). Let \(X_w\) be the random variable defined by: \(X_w=1\) if \(uw,vw\in E(G)\) and \(X_w=0\) otherwise. Assuming \(uv\in E(G)\), let \(T_{uv}\) denote the number of triangles of G that contain uv. Notice that \(X_w\), \(w\in V(G)\setminus \{u,v\}\), are independent 0–1 variables, , and \(\mathbf{E}[T_{uv}]=(n-2)p^2\). By Chernoff’s Inequality, we have

$$\mathbf {Pr}\left[ T_{uv}\ge \left( 1+\frac{\epsilon }{2}\right) (n-2)p^2\right] \le \exp \left( -\frac{\epsilon ^2(n-2)p^2}{12}\right) , $$

and by using Union Bound Inequality

$$\begin{aligned} \mathbf {Pr}\left[ T_{e}\ge \left( 1+\frac{\epsilon }{2}\right) (n-2)p^2\text { for some }e\in E(G)\right] \le n^2\cdot \exp \left( -\frac{\epsilon ^2(n-2)p^2}{12}\right) =o(1). \end{aligned}$$

Now taking every triangle of G with an amount of \(\displaystyle \frac{1}{(1+\frac{\epsilon }{2})(n-2)p^2}\), we obtain a feasible fractional triangle packing of G with high probability, giving

$$\begin{aligned} \begin{aligned}&\mathbf {Pr}\!\left[ \nu _t^*(G)\ge \sum \limits _{T\in \mathcal {T}(G)}\frac{1}{(1+\frac{\epsilon }{2})(n-2)p^2}\right] \\ =~&\mathbf {Pr}\!\left[ \nu _t^*(G)\ge \frac{\mathcal {T}(G)}{(1+\frac{\epsilon }{2})(n-2)p^2}\right] \\ =~&1-o(1) \end{aligned} \end{aligned}$$
(3)

For each triangle \(T\in K_n\), let \(X_T\) be the random variable defined by: \(X_T=1\) if \(T\subseteq G\) and \(X_T=0\) otherwise. Then

$$ \mathbf{E}[X_T]=\mathbf {Pr}[X_T=1]=p^3\text { and }\mathbf {Var}[X_T]=p^3(1-p^3). $$

For any two distinct triangles \(T_1,T_2\) in \(K_n\), we have

Denote \(\mathcal {T}(G)=\sum _{T\in \mathscr {T}(K_n)}X_T\). Combining \(p=\varOmega (1)\), we can compute

$$\begin{aligned} \mathbf{E}[\mathcal {T}(G)]&={n\atopwithdelims ()3}p^3 = \varTheta (n^3).\\ \mathbf {Var}[\mathcal {T}(G)]&={n\atopwithdelims ()3}p^3(1-p^3)+2{n\atopwithdelims ()2}{n-2\atopwithdelims ()2}(p^5-p^6) = \varTheta (n^4). \end{aligned}$$

Thus, Chebyshev’s Inequality gives

$$\begin{aligned} \begin{aligned}&\mathbf {Pr}\left[ \mathcal {T}(G)\le \left( 1-\frac{\epsilon }{2}\right) \mathbf{E}[\mathcal {T}(G)]\right] \\ \le ~&\mathbf {Pr}\left[ |\mathcal {T}(G)-\mathbf{E}[\mathcal {T}(G)]|\ge \frac{\epsilon }{2} \mathbf{E}[\mathcal {T}(G)]\right] \\ \le ~&\frac{4\mathbf {Var}[\mathcal {T}(G)]}{\epsilon ^2(\mathbf{E}[\mathcal {T}(G)])^2}\\ =~&o(1) \end{aligned} \end{aligned}$$
(4)

Then, since \(\displaystyle \frac{1- {\epsilon }/{2}}{1+ {\epsilon }/{2}}>1-\epsilon \) when \(0<\epsilon <1\), we obtain

$$\begin{aligned}&\mathbf {Pr}\left[ \nu _t^*(G)\ge (1-\epsilon )\frac{n(n-1)}{6}p\right] \\\ge & {} \mathbf {Pr}\left[ \nu _t^*(G)\ge \frac{1- {\epsilon }/{2}}{1+ {\epsilon }/{2}}\cdot \frac{n(n-1)}{6}p\right] \\\ge & {} \mathbf {Pr}\left[ \nu _t^*(G)\ge \frac{1- {\epsilon }/{2}}{1+ {\epsilon }/{2}}\cdot \frac{n(n-1)}{6}p ~\left| ~ \nu _t^*(G)\ge \frac{\mathcal {T}(G)}{(1+ {\epsilon }/{2})(n-2)p^2}\right. \right] -o(1)\\\ge & {} \mathbf {Pr}\left[ \frac{\mathcal {T}(G)}{(1+ {\epsilon }/{2})(n-2)p^2}\ge \frac{1- {\epsilon }/{2}}{1+ {\epsilon }/{2}}\cdot \frac{n(n-1)}{6}p\right] -o(1)\\= & {} \mathbf {Pr}\left[ \mathcal {T}(G)\ge \left( 1- {\epsilon }/{2}\right) \mathbf{E}[\mathcal {T}(G)]\right] -o(1)\\= & {} 1-o(1), \end{aligned}$$

where the second inequality is implied by Lemma 1 and (3), and the last equality is implied by (4). The lemma is established.

We take advantage of the following result in [16] to bridge the relationship of \(\nu _t^*(G)\) and \(\nu _t(G)\). This result shows that the gap between these two parameters is very small when graph G is dense.

Lemma 5

( [16]). If G is a graph with n vertices, then \(\nu _t^*(G)-\nu _t(G)=o(n^2)\).

Combining the above lemma, we derive naturally the lower bound of \(\nu _t(G)\) with high probability.

Lemma 6

If \(G\in \mathcal {G}(n,p)\) and \(p=\varOmega (1)\), then for any \( 0<\epsilon <1\), it holds that

$$\begin{aligned} \mathbf {Pr}\left[ \nu _t(G)\ge (1-\epsilon )\cdot \frac{n(n-1)p}{6}\right] =1-o(1). \end{aligned}$$

Proof

Using Lemma 5, when n is sufficiently large we have

$$\begin{aligned}&\mathbf {Pr}\left[ \nu _t(G)\ge (1-\epsilon )\cdot \frac{n(n-1)p}{6}\right] \\= & {} \mathbf {Pr}\left[ \nu _t^*(G)\ge (1-\epsilon )\cdot \frac{n(n-1)p}{6}+o(n^2)\right] \\\ge & {} \mathbf {Pr}\left[ \nu _t^*(G)\ge (1-\epsilon )\cdot \frac{n(n-1)p}{6}+\frac{\epsilon }{2}\cdot \frac{n(n-1)p}{6}\right] \\= & {} \mathbf {Pr}\left[ \nu _t^*(G)\ge \left( 1-\frac{\epsilon }{2}\right) \frac{n(n-1)p}{6}\right] . \end{aligned}$$

The result follows from Lemma 4.

Now we are ready to prove one of the two main theorems:

Theorem 1

If \(G\in \mathcal {G}(n,p)\) and \(p=\varOmega (1)\), then for any \( 0<\epsilon <1\), it holds that

$$\mathbf {Pr}\left[ \tau _t(G)\le 1.5(1+\epsilon )\nu _t(G)\right] =1-o(1).$$

Proof

Let A denote the event that

$$\displaystyle \tau _t(G)\le \left( 1+\frac{\epsilon }{3}\right) \frac{n(n-1)}{4}p \text {~~and~~} \displaystyle \nu _t(G)\ge \left( 1-\frac{\epsilon }{3}\right) \frac{n(n-1)p}{6}.$$

Combining Lemmas 3 and 6 we have \(\mathbf {Pr}[A]=1-o(1)\). Note that \(\displaystyle 1+\epsilon > \frac{1+ {\epsilon }/{3}}{1- {\epsilon }/{3}}\). Therefore, recalling Lemma 1, we deduce that

$$\begin{aligned}&\mathbf {Pr}\left[ \tau _t(G)\le 1.5(1+\epsilon )\nu _t(G)\right] \\\ge & {} \mathbf {Pr}\left[ \tau _t(G)\le 1.5\cdot \frac{1+ {\epsilon }/{3}}{1- {\epsilon }/{3}}\nu _t(G)\right] \\\ge & {} \mathbf {Pr}\left[ \left. \tau _t(G)\le 1.5\cdot \frac{1+ {\epsilon }/{3}}{1- {\epsilon }/{3}}\nu _t(G)~\right| A \right] -o(1)\\= & {} 1-o(1), \end{aligned}$$

which establishes the theorem.

Remark 1

In \(\mathcal {G}(n,p)\), \(p=\varOmega (1)\) implies \(\mathbf{E}[m]={n\atopwithdelims ()2}p=n(n-1)p/2=\varOmega (n^{2})\), thus our main theorem is a result in dense random graphs.

3 \(\mathcal {G}(n,m)\) Random Graph Model

In this section, we discuss the probability properties of graphs in \(\mathcal {G}(n,m)\). Given \(0\le m\le n(n-1)/2\), under \(\mathcal {G}(n,m)\) model, let G be defined by randomly picking m edges from all \(v_i, v_j\) pairs. Theorem 2 is our main result: If \(G\in \mathcal {G}(n,m)\) and \(m=\varOmega (n^2)\), then for any \( 0<\epsilon <1\), it holds that

$$\mathbf {Pr}\left[ \tau _t(G)\le 1.5(1+\epsilon )\nu _t(G)\right] =1-o(1).$$

The primary idea behind the theorem is as follows:

  • First, in Lemma 2, \(\tau _t(G)\le m/2\) holds;

  • Second, in Lemma 7, Lemma 8, we prove that \(\nu _t(G)\ge (1-\epsilon )m/3\) holds with high probability through combining the Chernoff’s bounds technique and the relationship between \(\nu ^*(G)\) and \(\nu _t(G)\) [16];

  • By using the previous two properties, Theorem 2 holds.

For easy of presentation, we use N to denote \(\displaystyle {n\atopwithdelims ()2}\).

Now we give the high probability result of the lower bound of \(\nu _t^*(G)\) in \(\mathcal {G}(n,m)\) model:

Lemma 7

If \(G\in \mathcal {G}(n,m)\) and \(m=\varOmega (n^2)\), then for any \( 0<\epsilon <1\), it holds that

$$\mathbf {Pr}[\nu _t^*(G)\ge (1-\epsilon ){m}/{3}]=1-o(1).$$

Proof

Consider an arbitrary edge \(uv\in K_n\). For each \(w\in V(G)\setminus \{u,v\}\). Let \(X_w\) be the random variable defined by; \(X_w=1\) if \(uw,vw\in E(G)\) and \(X_w=0\) otherwise. Assuming \(uv\in E(G)\), let \(T_{uv}\) denote the number of triangles of G that contain uv. Then we have

$$\mathbf{E}[X_w]=\frac{m(m-1)}{N(N-1)},$$
$$\mathbf {Var}[X_w]=\frac{m(m-1)}{N(N-1)}(1-\frac{m(m-1)}{N(N-1)} )$$
$$\mathbf {Cov}[X_w,X_{w'}]=\frac{m(m-1)(m-2)(m-3)}{N(N-1)(N-2)(N-3)}-(\frac{m(m-1)}{N(N-1)})^2\le 0$$

where \(w,w'\in V(G)\setminus \{u,v\}\). It follows from \(T_{uv}=\sum _{w\in V(G)\setminus \{u,v\}}X_w\) that

$$\begin{aligned} \mathbf{E}[T_{uv}]= & {} (n-2)\frac{m(m-1)}{N(N-1)}=\varTheta (n). \end{aligned}$$

Using Chernoff’s Inequality, we derive

$$\begin{aligned}\begin{gathered} \mathbf {Pr}\left[ T_{uv}\ge \left( 1+\frac{\epsilon }{2}\right) \frac{(n-2)m(m-1)}{N(N-1)}\right] \le \exp \left( -\frac{\epsilon ^2\mathbf{E}[T_{uv}]}{12}\right) \le \exp \left( -\frac{\epsilon ^2\varTheta (n)}{12}\right) ;\\ \mathbf {Pr}\left[ T_{e}\ge \left( 1+\frac{\epsilon }{2}\right) \frac{(n-2)m(m-1)}{N(N-1)} ~\exists ~ e\in E(G)\right] \le n^2\exp \left( -\frac{\epsilon ^2\varTheta (n)}{12}\right) =o(1). \end{gathered}\end{aligned}$$

So taking every triangle of G with an amount of \(\displaystyle \left[ (1+\frac{\epsilon }{2})\cdot \frac{(n-2)m(m-1)}{N(N-1)}\right] ^{-1}\) makes a feasible fractional packing of G with high probability. Thus

$$\begin{aligned} \begin{aligned}&\mathbf {Pr}\left[ \nu _t^*(G)\ge \sum \limits _{\forall T}\displaystyle \frac{1}{(1+\frac{\epsilon }{2})\cdot \frac{(n-2)m(m-1)}{N(N-1)}}\right] \\ =~&\mathbf {Pr}\left[ \nu _t^*(G)\ge \frac{\mathcal {T}(G)}{(1+\frac{\epsilon }{2})\cdot \frac{(n-2)m(m-1)}{N(N-1)}}\right] \\ =~&1-o(1). \end{aligned} \end{aligned}$$
(5)

For each triangle \(T\in K_n\), let \(X_T\) be the random variable defined by: \(X_T=1\) if \(T\subseteq G\) and \(X_T=0\) otherwise. Then

$$\begin{aligned} \mathbf{E}[X_T]=\frac{m(m-1)(m-2)}{N(N-1)(N-2)}. \end{aligned}$$
$$\begin{aligned} \mathbf {Var}[X_T]=\frac{m(m-1)(m-2)}{N(N-1)(N-2)}\left( 1-\frac{m(m-1)(m-2)}{N(N-1)(N-2)}\right) . \end{aligned}$$

For any two distinct triangles \(T_1,T_2\) in \(K_n\), we have

$$\begin{aligned}&\mathbf {Cov}(X_{T_1},X_{T_2})\\= & {} \mathbf{E}[X_{T_1}X_{T_2}]-\mathbf{E}[X_{T_1}]\cdot \mathbf{E}[X_{T_2}]\\= & {} {\left\{ \begin{array}{ll} \displaystyle \frac{m(m-1)(m-2)(m-3)(m-4)}{N(N-1)(N-2)(N-3)(N-4)}&{} \displaystyle -\left( \frac{m(m-1)(m-2)}{N(N-1)(N-2)}\right) ^2,\\ &{}\text {if~} E(T_1)\cap E( T_2)\ne \emptyset ; \\ 0, &{}\text {otherwise}. \end{array}\right. } \end{aligned}$$

Notice that

$$\begin{aligned} \mathbf{E}[\mathcal {T}(G)]={n\atopwithdelims ()3}\frac{m(m-1)(m-2)}{N(N-1)(N-2)}=\varTheta (n^3) \end{aligned}$$
$$\begin{aligned}&\mathbf {Var}[\mathcal {T}(G)]={n\atopwithdelims ()3}\frac{m(m-1)(m-2)}{N(N-1)(N-2)}\left( 1-\frac{m(m-1)(m-2)}{N(N-1)(N-2)}\right) +\\&2{n\atopwithdelims ()2}{n-2\atopwithdelims ()2}\left( \frac{m(m-1)(m-2)(m-3)(m-4)}{N(N-1)(N-2)(N-3)(N-4)}-\left( \frac{m(m-1)(m-2)}{N(N-1)(N-2)}\right) ^2\right) \\&=\varTheta (n^4). \end{aligned}$$

By Chebyshev’s Inequality, we have:

$$\begin{aligned} \begin{aligned}&\mathbf {Pr}\left[ \mathcal {T}(G)\le \left( 1-\frac{\epsilon }{4}\right) \mathbf{E}[\mathcal {T}(G)]\right] \\ \le ~&\mathbf {Pr}\left[ |\mathcal {T}(G)-\mathbf{E}[\mathcal {T}(G)]|\ge \frac{\epsilon }{4} \mathbf{E}[\mathcal {T}(G)]\right] \\ \le ~&\frac{16\mathbf {Var}[\mathcal {T}(G)]}{\epsilon ^2(\mathbf{E}[\mathcal {T}(G)])^2}=o(1). \end{aligned} \end{aligned}$$
(6)

Since \(\displaystyle \frac{1-{\epsilon }/{2}}{1+{\epsilon }/{2}}>1-\epsilon \), we deduce from (5) and Lemma 1 that

$$\begin{aligned}&\mathbf {Pr}\left[ \nu _t^*(G)\ge (1-\epsilon )\frac{m}{3}\right] \\\ge & {} \mathbf {Pr}\left[ \nu _t^*(G)\ge \frac{1-{\epsilon }/{2}}{1+{\epsilon }/{2}}\cdot \frac{m}{3}\right] \\\ge & {} \mathbf {Pr}\left[ \nu _t^*(G)\ge \frac{1-{\epsilon }/{2}}{1+{\epsilon }/{2}}\cdot \frac{m}{3} ~\left| ~ \nu _t^*(G)\ge \frac{\mathcal {T}(G)}{(1+\frac{\epsilon }{2})\frac{(n-2)m(m-1)}{N(N-1)}}\right. \right] -o(1)\\\ge & {} \mathbf {Pr}\left[ \frac{\mathcal {T}(G)}{(1+\frac{\epsilon }{2})\frac{(n-2)m(m-1)}{N(N-1)}}\ge \frac{1-{\epsilon }/{2}}{1+{\epsilon }/{2}}\cdot \frac{m}{3}\right] -o(1)\\= & {} \mathbf {Pr}\left[ \mathcal {T}(G)\ge \left( 1-\frac{\epsilon }{2}\right) \left( {\begin{array}{c}n\\ 3\end{array}}\right) \frac{m^2(m-1)}{N^2(N-1)}\right] -o(1) \end{aligned}$$

As \(\displaystyle (1+\frac{\epsilon }{4})\frac{m-2}{N-2}>\frac{m}{N}\) holds for sufficiently large n, we have

$$\begin{aligned}&\mathbf {Pr}\left[ \nu _t^*(G)\ge (1-\epsilon )\frac{m}{3}\right] \\\ge & {} \mathbf {Pr}\left[ \mathcal {T}(G)\ge \left( 1-\frac{\epsilon }{2}\right) \left( 1+\frac{\epsilon }{4}\right) \left( {\begin{array}{c}n\\ 3\end{array}}\right) \frac{m(m-1)(m-2)}{N(N-1)(N-2)}\right] -o(1)\\\ge & {} \mathbf {Pr}\left[ \mathcal {T}(G)\ge \left( 1-\frac{\epsilon }{4}\right) \mathbf{E}[\mathcal {T}(G)]\right] -o(1) \\ {}= & {} 1-o(1), \end{aligned}$$

where the second inequality is implied by \((1-\epsilon /2)(1+\epsilon /4)\le 1-\epsilon /4\), and the last equality is guaranteed by (6). This complete the proof of the lemma.

Similar to the the proof of Lemma 6, the combination of Lemma 5 and Lemma 7 gives the following Lemma 8.

Lemma 8

If \(G\in \mathcal {G}(n,m)\) and \(m=\varOmega (n^2)\), then for any \( 0<\epsilon <1\), it holds that

$$\mathbf {Pr}[\nu _t(G)\ge (1-\epsilon ){m}/{3}]=1-o(1).$$

Proof

Using Lemma 5, when n is sufficiently large we have

$$\begin{aligned}&\mathbf {Pr}\left[ \nu _t(G)\ge (1-\epsilon )m/3\right] \\= & {} \mathbf {Pr}\left[ \nu _t^*(G)\ge (1-\epsilon )m/3+o(n^2)\right] \\\ge & {} \mathbf {Pr}\left[ \nu _t^*(G)\ge (1-\epsilon )m/3+\frac{\epsilon }{2}\cdot m/3\right] \\= & {} \mathbf {Pr}\left[ \nu _t^*(G)\ge \left( 1-\frac{\epsilon }{2}\right) m/3\right] . \end{aligned}$$

The result follows from Lemma 7.

Now, we are ready to prove the main theorem in \(\mathcal {G}(n,m)\) as follows:

Theorem 2

If \(G\in \mathcal {G}(n,m)\) and \(m=\varOmega (n^2)\), then for any \( 0<\epsilon <1\), it holds that

$$\mathbf {Pr}\left[ \tau _t(G)\le 1.5(1+\epsilon )\nu _t(G)\right] =1-o(1).$$

Proof

Let A denote the event that

$$\tau _t(G)\le \frac{m}{2} \text {~~and~~} \nu _t(G)\ge (1-\frac{\epsilon }{2})\frac{m}{3}.$$

It follows from Lemmas 2(ii) and 8 that \(\mathbf {Pr}[A]=1-o(1)\). Since \(1+\epsilon >(1-\epsilon /2)^{-1}\), we deduce from Lemma 1 that

$$\begin{aligned}&\mathbf {Pr}[\tau _t(G)\le 1.5(1+\epsilon )\nu _t(G)]\\\ge & {} \mathbf {Pr}\left[ (1-\epsilon /2)\cdot \tau _t(G)\le {1.5\nu _t(G)}\right] \\\ge & {} \mathbf {Pr}\left[ \left. (1-\epsilon /2)\cdot \tau _t(G)\le {1.5\nu _t(G)}~\right| A\right] -o(1)\\= & {} 1-o(1) \end{aligned}$$

verifying the theorem.

Remark 2

In \(\mathcal {G}(n,m)\), the condition \(m=\varOmega (n^{2})\) implies that our main theorem is a result in dense random graphs.

4 Conclusion and Future Work

We consider Tuza’s conjecture on random graphs, under two probability models \(\mathcal {G}(n,p)\) and \(\mathcal {G}(n,m)\). Two results are following:

  • If \(G\in \mathcal {G}(n,p)\) and \(p=\varOmega (1)\), then for any \( 0<\epsilon <1\), it holds that

    $$\mathbf {Pr}\left[ \tau _t(G)\le 1.5(1+\epsilon )\nu _t(G)\right] =1-o(1).$$

  • If \(G\in \mathcal {G}(n,m)\) and \(m=\varOmega (n^2)\), then for any \( 0<\epsilon <1\), it holds that

    $$\mathbf {Pr}\left[ \tau _t(G)\le 1.5(1+\epsilon )\nu _t(G)\right] =1-o(1).$$

In some sense, on dense random graph, these two inequalities verify Tuza’s conjecture.

Future work: In dense random graphs, these two results nearly imply \(\tau _t(G)\le 1.5 \nu _t(G)\) holds with high probability. It is interesting to consider the same problem in sparse random graphs.