Triangle packing and covering in dense random graphs

Abstract

Given a simple graph $G=(V,E)$, a subset of E is called a triangle cover if it intersects each triangle of G. Let $\nu _t(G)$ and $\tau _t(G)$ denote the maximum number of pairwise edge-disjoint triangles in G and the minimum cardinality of a triangle cover of G, respectively. Tuza (in: Finite and infinite sets, proceedings of Colloquia Mathematica Societatis, Janos Bolyai, p 888, 1981) conjectured in 1981 that $\tau _t(G)/\nu _t(G)\le 2$ holds for every graph G. In this paper, we consider Tuza’s Conjecture on dense random graphs. Under $\mathcal {G}(n,p)$ model with a constant p, we prove that the ratio of $\tau _t(G)$ and $\nu _t(G)$ has the upper bound close to 1.5 with high probability. Furthermore, the ratio 1.5 is nearly the best result when $p\ge 0.791$. In some sense, on dense random graphs, these conclusions verify Tuza’s Conjecture.

1 Introduction

The main motivation for this paper is an old conjecture of Tuza about packing and covering of triangles by edges. A triangle packing in a graph G is a set of pairwise edge-disjoint triangles. A triangle edge cover in G is a set of edges meeting all triangles. We denote by $\nu _t(G)$ the maximum cardinality of a triangle packing in G, and by $\tau _t(G)$ the minimum cardinality of a triangle edge cover for G. It is clear that for every graph G we have $1\le \tau _t(G)/\nu _t(G)\le 3$. In 1981, Tuza proposed the following conjecture:

Conjecture 1

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

Related work This conjecture was verified for many classes of graphs. The conjecture is known to be true for certain special classes of graphs, for example, despite having received considerable attention, Tuza’s Conjecture is still open. Tuza’s Conjecture has been studied by many authors. Other authors have pursued the conjecture by showing that the desired bound $\tau _t(G)/\nu _t(G)\le 2$ holds for certain special classes of graphs.

In particular, Tuza (1990) verified it for planar graphs, $K_5$-free chordal graphs and for dense graphs, specifically for graphs on n vertices and with at least $\frac{7}{16}n^{2}$ edges. Haxell and Kohayakawa (1998) proved that if G is a tripartite graph, then $\tau _t(G)/\nu _t(G)\le 1.956$.

The complete graphs $K_4$ and $K_5$ show that this bound is tight. Another generalization of the planar case was given by Krivelevich (1995), who showed that Tuza’s Conjecture holds for graphs with no $K_{3,3}$-subdivision. Krivelevich (1995) also proved that a version of Tuza’s Conjecture holds when $\tau _t(G)$ or $\nu _t(G)$ is replaced by its fractional relaxation $\tau _t^{*}(G)$ or $\nu _t^{*}(G)$, where instead of asking for a set of edges Y or a set of edge-disjoint triangles T, one instead asks for a weight function on the edges or the triangles of G, subject to constraints on the weight function which model the original constraints on Y and T .

Lakshmanan et al. (2012) showed that it holds for the class of triangle-3-colourable graphs, where a graph G is triangle-3-colourable if its edges can be coloured with three colours so that the edges of each triangle receive three distinct colours. This is a direct consequence of the case $r=3$ of Ryser’s Conjecture proved by Aharoni: indeed, if G is triangle-3-colourable, then the triangle hypergraph of G is clearly 3-partite. Since the class of triangle-3-colourable graphs contains that of 4-colourable graphs (Lakshmanan et al. 2012), the previous result is a generalization of the planar case mentioned above.

Weighted versions of the problem were studied in Chapuy et al. (2014). Chapuy et al. (2014) improved Krivelevich’s bound of $\tau _t(G)\le {2}\nu _t^{*}(G)$ to the stronger bound $\tau _t(G)\le {2}\nu _t^{*}(G)-\frac{1}{\sqrt{6}}\sqrt{\nu _t^{*}(G)}$, and proved that this bound is tight. Chapuy, DeVos, McDonald, Mohar, and Schiede also extended Tuza’s result on planar graphs, as well as Haxell’s result, to the context of weighted graphs.

The best general upper bound on $\tau _t(G)$ in terms of $\nu _t(G)$ is due to Haxell (1999), who showed that $\tau _t(G)/\nu _t(G)\le 66/23$ for all graphs G.

Puleo (2015) introduced a set of tools for dealing with graphs that contain vertices of small degree, and verified Tuza’s Conjecture for graphs with maximum average degree less than 7, i.e., for graphs in which every subgraph has average degree less than 7.

For all the classes mentioned so far, the conjecture is tight, since they contain either $K_{4}$ or $K_{5}$. Therefore, a natural question arises: What happens if we forbid $K_{4}$? Haxell et al. (2012b) showed that the constant 2 cannot essentially be improved: for every $\varepsilon >0$ there exists a $K_{4}$-free graph $G_{\varepsilon }$ satisfying $\tau _t(G_{\varepsilon })/\nu _t(G_{\varepsilon })> 2-\varepsilon$. Krivelevich’s result was also extended by Haxell et al. (2012b), who proved a stability theorem: if $\tau _t^{*}(G)\ge \nu _t^{*}(G)-x$, then G contains a family of pairwise edge-disjoint subgraphs consisting of $\nu _t(G)-\lfloor 10x\rfloor$ copies of $K_{4}$ as well as $\lfloor 10x\rfloor$ triangles.

Moreover, several graph classes for which it holds are known. For example, since every graph G has a bipartite subgraph with at least |E(G)|/2 edges and since the complement of this edge set is clearly a triangle-transversal of G, we have that Tuza’s Conjecture holds if G has many edge-disjoint triangles, more precisely at least |E(G)|/4. The result on planar graphs was extended in a different direction by Haxell et al. (2012a), who proved that when G is a $K_{4}$-free planar graph, the stronger inequality $\tau _t(G)/\nu _t(G)\le \frac{3}{2}$ holds.

Haxell and Rödl (2001) showed that if G is an n-vertex graph and $\nu _t^{*}(G)$ is the fractional relaxation of $\nu _t(G)$, then $\nu _t^{*}(G)-\nu _t(G)=o(n^{2})$. As observed by Yuster (2012), this result together with Krivelevich’s result imply $\tau _t(G)\le {2}\nu _t(G)+o(n^{2})$; thus, Tuza’s Conjecture is asymptotically true for graphs containing a quadratic-sized family of edge-disjoint triangles.

The classic random graph models $\mathcal {G}(n,p)$ and $\mathcal {G}(n,m)$ can be regarded as special graph classes, and the probabilistic properties between $\tau _t(G)$ and $\nu _t(G)$ can also be considered. Bennett et al. (2020) 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 Krivelevich (1997), Ruciński (1992) and Baron (2016). Other extensions related to Conjecture 1 can be found in Erdös et al. (1996), Hosseinzadeh and Soltankhah (2015), Lakshmanan et al. (2016), Chen et al. (2016a, 2016b, 2018), Puleo (2015, 2017), Tang and Diao (2020), Botler et al. (2018, 2019), Munaro (2018) and Chalermsook et al. (2020).

Our contributions We consider Tuza’s conjecture on random graph, under the probability model $\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. We use the probabilistic methods to derive the probabilistic properties of the ratio of triangle cover and packing number on dense random graphs. Formally, one of our main theorems is as follows: 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[ \tau _t(G)\le 1.5(1+\epsilon )\nu _t(G)\right] =1-o(1). \end{aligned}$$

• Consider $\mathcal {G}(n,p)$ with a large constant p within value 1, the ratio 1.5 is almost unimprovable: If $G\in \mathcal {G}(n,p)$ and $p\ge 0.791$, then for any $0<\epsilon <1$, it holds that

  $$\begin{aligned} \mathbf {Pr}\left[ \tau _t(G)< 1.5(1-\epsilon )\nu _t(G)\right] =o(1). \end{aligned}$$

The main content of the article is organized as follows: Some definitions and terminologies are introduced in Sect. 2; In Sect. 3, the theorems in $\mathcal {G}(n,p)$ random graph model are 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 Preliminaries

This section will introduce some probabilistic techniques and triangle-related terminologies in graph theory. Firstly, we introduce some symbols in asymptotic analysis as follows.

• $f(n)=O(g(n))$: $\exists ~c>0, n_{0}\in {\mathbb {N}}_{+},\forall n\ge n_{0}$, $0\le f(n)\le cg(n)$.

• $f(n)=\varOmega (g(n))$: $\exists ~c>0, n_{0}\in {\mathbb {N}}_{+},\forall n\ge n_{0}$, $0\le cg(n)\le f(n)$.

• $f(n)=\varTheta (g(n))$: $\exists ~c_2\ge c_{1}>0, n_{0}\in {\mathbb {N}}_{+},\forall n\ge n_{0}$, $0\le c_{1}g(n)\le f(n)\le c_{2}g(n)$.

• $f(n)=o(g(n))$: $\forall ~c>0, \exists ~n_{0}\in {\mathbb {N}}_{+},\forall n\ge n_{0}$, $0\le f(n)< cg(n)$.

• $f(n)=\omega (g(n))$: $\forall ~c>0, \exists ~n_{0}\in {\mathbb {N}}_{+},\forall n\ge n_{0}$, $0\le cg(n)< f(n)$.

Next, we introduce three important probabilistic properties, which will be used repeatedly in the proofs of this paper. The following one is simple but valuable.

Lemma 1

A(n) and B(n) are two events with parameter n. If $\mathbf {Pr}[A(n)] = 1 - o(1)$, then $\mathbf {Pr}[B(n)] \ge \mathbf {Pr}[B(n)|A(n)]-o(1)$.

Proof

Since $\mathbf {Pr}[A(n)] = 1 - o(1)$, we have

$$\begin{aligned} \mathbf {Pr}[B(n)]\cdot \mathbf {Pr}[A(n)]= & {} \mathbf {Pr}[B(n)]-\mathbf {Pr}[B(n)]\cdot o(1) \\= & {} \mathbf {Pr}[B(n)]-o(1)\ge \mathbf {Pr}[A(n)\cap B(n)]-o(1). \end{aligned}$$

As $o(1)/\mathbf {Pr}[A(n)]=o(1)$, we derive

$$\begin{aligned} \mathbf {Pr}[B(n)]\ge \mathbf {Pr}[A(n)\cap B(n)]/\mathbf {Pr}[A(n)]-o(1)/\mathbf {Pr}[A(n)] =\mathbf {Pr}[B(n)~|~A(n)]-o(1), \end{aligned}$$

which completes the proof. $\square$

Union Bound Inequality says that for any finite or countable set of events, the probability that at least one of the events happens is no greater than the sum of the probabilities of the individual events.

Lemma 2

(Union Bound Inequality) For any finite or countably infinite sequence of events $E_1,E_2,\dots$, then

$$\begin{aligned} \mathbf {Pr}\left[ ~\bigcup _{i\ge 1} E_i~\right] \le \sum _{i\ge 1} \mathbf {Pr}(E_i). \end{aligned}$$

Chernoff’s Inequalities (Alon and Spencer 2008; Mitzenmacher and Upfal 2005) give exponentially decreasing bounds on tail distributions of sums of independent random variables.

Lemma 3

(Chernoff’s Inequalities) Let $X_1,X_2,\dots ,X_n$ be mutually independent 0-1 random variables with $\mathbf {Pr}[X_i = 1] = p_i$. Let $X = \sum _{i=1}^n X_i$ and $\mu = {\mathbf {E}}[X]$. For $0 < \epsilon \le 1$, then the following bounds hold:

$$\begin{aligned} \mathbf {Pr}[X \ge (1+\epsilon )\mu ] \le e^{-\epsilon ^2 \mu /3},~~~~\mathbf {Pr}[X \le (1-\epsilon )\mu ] \le e^{-\epsilon ^2 \mu /2}. \end{aligned}$$

Furthermore, we give some definitions and terminologies in graph theory. Given a simple graph $G=(V,E)$, denote the vertex number as $n=|V|$ and the edge number as $m=|E|$. $\delta (G)$ is the minimum degree of graph G and b(G) is the maximum number of edges of sub-bipartite in G. An edge subset S is a triangle cover of G if $G-S$ is triangle-free. $\tau _t(G)$ is the minimum cardinality of a triangle cover in G. A collection of pairwise edge-disjoint triangles is called a triangle packing of G. $\nu _t(G)$ is the maximum cardinality of a triangle packing in G. $\tau ^{*}_t(G)$ is the minimum cardinality of a fractional triangle cover in G and $\nu ^{*}_t(G)$ is the maximum cardinality of a fractional triangle packing in G.

The random graph model we consider in this paper is $\mathcal {G}(n,p)$. Given $0\le p\le 1$, $\mathbf {Pr}(\{v_i,v_j\}\in G)=p$ for all $v_i,v_j$ with these probabilities mutually independent.

3 Triangle packing and covering in ${\mathcal {G}}(n,p)$ model

3.1 The ratio with high probability

In this section, we discuss the probability properties of graphs in ${\mathcal {G}}(n,p)$. The following result shows the high probability of the relationship between $\tau _t(G)$ and $\nu _t(G)$ for $G\in {\mathcal {G}}(n,p)$ with $p=\varOmega (1)$. The proof can be found in the conference version of this paper (Tang and Diao 2020).

Theorem 1

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[ \tau _t(G)\le 1.5(1+\epsilon )\nu _t(G)\right] =1-o(1). \end{aligned}$$

3.2 The ratio with small probability

In this section, we will prove under $\mathcal {G}(n,p)$ model with $p=\varOmega (1),p\ge 0.791$, the ratio 1.5 is nearly the best result, which means for any real number $0<\epsilon <1$, $\tau _t(G)< 1.5(1-\epsilon )\nu _t(G)$ holds with small probability (see Theorem 2). Theorem 2 is our main result: If $G\in \mathcal {G}(n,p)$ and $p\ge 0.791$, then for any $0<\epsilon <1$, it holds that

$$\begin{aligned} \mathbf {Pr}\left[ \tau _t(G)< 1.5(1-\epsilon )\nu _t(G)\right] =o(1). \end{aligned}$$

The primary idea behind the theorem is as follows:

• First, in Lemma 7, we prove that $b(G)\le (1+\epsilon )\frac{n^2}{4}p$ holds with high probability by using the Chernoff’s bounds technique;

• Second, in Lemma 8, we prove that $\tau _t(G)\ge (1-\epsilon )\frac{n(n-1)}{4}p$ holds with high probability through combining the Chernoff’s bounds technique and the relationship between b(G) and $\tau _t(G)$ when the graph is dense enough in Balogh et al. (2006).

• Combining the results in Lemmas 5 and 8, Theorem 2 holds.

Recall that b(G) is the maximum number of edges of sub-bipartite in G. There are four basic properties of graph parameters in Lemma 4. The first three holds in every graph, while the last one shows the boundary condition of triangle-free in ${\mathcal {G}}(n,p)$. The result of Lemma 5 gives an upper bound for $\nu _t(G)$ with high probability. The proofs of Lemmas 4 and 5 can be found in Tang and Diao (2020).

Lemma 4

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

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

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

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

Lemma 5

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

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

Clearly, for complete graph $K_n$, then $\displaystyle \tau _t(K_n)={n\atopwithdelims ()2}-b(K_n)$. Let $\rho$ be the least number so that any graph G with $\delta (G)\ge \rho |V(G)|$ has $\tau _t(G)=|E(G)|-b(G)$.

Lemma 6

(Balogh et al. 2006) $\rho <0.791$.

We know that $b(G)\ge m/2$ from Lemma 4(i). Additionally, in ${\mathcal {G}}(n,p)$ model, we give the upper bound of b(G) with high probability.

Lemma 7

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

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

Proof

Applying Union Bound Inequality, we have

$$\begin{aligned}&\mathbf {Pr}\left[ b(G)>(1+\epsilon )\frac{n^2p}{4}\right] \\&\quad =~ \mathbf {Pr}\left[ ~\exists ~ S\subseteq V~ d(S)>(1+\epsilon )\frac{n^2p}{4}\right] \\&\quad \le ~ \sum _{S\subseteq V}\mathbf {Pr}\left[ d(S)>(1+\epsilon )\frac{n^2p}{4}\right] \\&\quad =~ \sum _{k=1}^{n-1}\sum _{|S|=k}\mathbf {Pr}\left[ d(S)>(1+\epsilon )\frac{n^2p}{4}\right] \\&\quad \le ~ \sum _{k=1}^{n-1}\sum _{|S|=k}\mathbf {Pr}\left[ d(S)>(1+\epsilon )k(n-k)p\right] \\&\quad =~ \sum _{k=1}^{n-1}{n\atopwithdelims ()k}\mathbf {Pr}\left[ d(S)>(1+\epsilon )k(n-k)p \text {~with~} |S| = k\right] , \end{aligned}$$

where d(S) is the number of edges between S and $V\backslash S$. For a subset $S\subseteq V$ with $|S|=k$, we have

$$\begin{aligned} {\mathbf {E}}[d(S)]=k(n-k)p. \end{aligned}$$

Using Chernoff’s Inequality,

$$\begin{aligned} \mathbf {Pr}\left[ d(S)>(1+\epsilon )k(n-k)p\right] \le \exp \left\{ -\frac{\epsilon ^2p}{3}k(n-k)\right\} . \end{aligned}$$

Define function f(k):

$$\begin{aligned} f(k) = {n\atopwithdelims ()k}\exp \left\{ -\frac{\epsilon ^2p}{3}k(n-k)\right\} . \end{aligned}$$

We only need to prove:

$$\begin{aligned} \sum _{k=1}^{n-1}f(k) \le n\max _{k} f(k)\le o(1). \end{aligned}$$

(1)

Since $f(k) = f(n-k)$, without loss of generality, we assume that the maximum value of f(k) achieves when $1\le k \le \lfloor n/2\rfloor$. Let $\displaystyle a=\frac{\epsilon ^2p}{3}>0$ and notice that

$$\begin{aligned} {n\atopwithdelims ()k}\le \left( \frac{en}{k}\right) ^k. \end{aligned}$$

Define function g(x) in $x\in [1,n/2]$:

$$\begin{aligned} g(x)=~&\ln \left( \left( \frac{en}{x}\right) ^x\exp \{-ax(n-x)\}\right) \\ =~&x(\ln n + 1) - x\ln x - ax(n-x). \end{aligned}$$

We know that

$$\begin{aligned} \max _{1\le k \le \lfloor n/2\rfloor } f(k)\le \max _{1\le x \le n/2} \exp \{g(x)\}. \end{aligned}$$

Let $\displaystyle l = \frac{x}{n}$ and compute derivative of g(x):

$$\begin{aligned} g^\prime (x)=\ln (1/l)+an(2l-1)=0. \end{aligned}$$

As $n\rightarrow \infty$, we know that $\lim _{n\rightarrow \infty } l = \frac{1}{2}$. Since the maximum value of function achieves at the boundaries or stationary points,

$$\begin{aligned} \max _{1\le x \le n/2} g(x) = \max \{g(1),g(n/2-o(n))\}. \end{aligned}$$

Thus,

$$\begin{aligned} n\max _{k} f(k)\le \max \{n\cdot \exp \{g(1)\},n\cdot \exp \{g(n/2-o(n))\}\}. \end{aligned}$$

Compute the value of $n\cdot \exp \{g(1)\}$:

$$\begin{aligned}&n\cdot \exp \{g(1)\}\\&\quad =~en^2\cdot \exp \{-a(n-1)\}\\&\quad =~o(1). \end{aligned}$$

Compute the value of $n\cdot \exp \{g(n/2-o(n))\}$ and notice that $o(n)\le n/6$ when n is sufficiently large.

$$\begin{aligned}&n\cdot \exp \{g(n/2-o(n))\}\\&\quad =~n\cdot \left( \frac{en}{n/2-o(n)}\right) ^{n/2-o(n)}\exp \{-a(n/2+o(n))(n/2-o(n))\}\\&\quad \le ~n\cdot \left( \frac{en}{n/3}\right) ^{n/2}\exp \{-a(n^2/4-o(n^2))\}\\&\quad \le ~n\cdot (3e)^{n/2}\exp \{-a(n^2/4-n^2/36)\}\\&\quad =~ n\cdot (3e)^{n/2}\exp \left\{ -\frac{2a}{9}n^2\right\} \\&\quad =o(1). \end{aligned}$$

Therefore, (1) holds, which completes the proof. $\square$

It is worth noting that the 1.5 in Theorem 1 is nearly the best possible whenever $p\ge 0.791$, which is a corollary of the following lemma.

Lemma 8

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

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

Proof

Consider an arbitrary vertex $v\in V(G)$. For each $u\in V(G)\setminus \{v\}$, let $X_u$ be the random variable defined by $X_u=1$ if $uv\in E(G)$ and $X_u=0$ otherwise. Note that $X_u$, $u\in V(G)\setminus \{v\}$ are independent 0-1 variables satisfying ${\mathbf {E}}[X_u]=p$, and the degree of v, written as d(v) satisfies $d(v)=\sum _{u\in V(G)\setminus \{v\}}X_u$ and ${\mathbf {E}}[d(v)]=(n-1)p$. By Theorem 6, we know that $\rho <0.791$. Let $\displaystyle \epsilon _0=\frac{1}{2}(1-\frac{\rho }{0.791})$. So $\displaystyle 0.791(1-\epsilon _0) = \frac{1}{2}(0.791+\rho )>\rho$. We can choose sufficiently large n to make $\displaystyle p(1-\epsilon _0)(n-1)\ge 0.791(1-\epsilon _0)(n-1)=\frac{1}{2}(0.791+\rho )(n-1)\ge \rho n$. Using Chernoff’s Inequality and Union Bound Inequality, we obtain

$$\begin{aligned} \mathbf {Pr}[d(v)\le \rho n]\le & {} \mathbf {Pr}[d(v)\le (1-\epsilon _0)(n-1)p]\le \exp \left( -\frac{\epsilon _0^2(n-1)p}{2}\right) ,\\ \mathbf {Pr}[\delta (G)\le \rho n]= & {} \mathbf {Pr}[d(w)\le \rho n\text { for some }w\in V(G)]\\\le & {} n\cdot \exp \left( -\frac{\epsilon _0^2(n-1)p}{2}\right) =o(1). \end{aligned}$$

In turn, the definition of $\rho$ gives $\mathbf {Pr}[\tau _t(G)\ne m-b(G)]\le \mathbf {Pr}[\delta (G)\le \rho n] =o(1)$. It follows that

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

(2)

Let A denote the event that

$$\begin{aligned} m\ge \left( 1-\frac{\epsilon }{4}\right) \frac{n(n-1)p}{2}~\text {and}~b(G)\le \left( 1+\frac{\epsilon }{4}\right) \frac{n^2p}{4}. \end{aligned}$$

Applying Lemma 7 and Chernoff’s Inequality, we obtain

$$\begin{aligned}&\mathbf {Pr}\left[ b(G)\ge \left( 1+\frac{\epsilon }{4}\right) \frac{n^2p}{4}\right] =o(1),\\&\quad \mathbf {Pr}\left[ m\le \left( 1-\frac{\epsilon }{4}\right) \frac{n(n-1)p}{2}\right] \\&\qquad =~\mathbf {Pr}\left[ m\le \left( 1-\frac{\epsilon }{4}\right) {\mathbf {E}}[m]\right] \\&\qquad \le ~\exp \left( -\frac{\epsilon ^2{\mathbf {E}}[m]}{32}\right) =o(1), \end{aligned}$$

which imply $\mathbf {Pr}[A]=1-o(1)$. Therefore, it follows from Lemma 1 that

$$\begin{aligned}&\mathbf {Pr}\left[ m-b(G)\ge \frac{(1-\epsilon )n(n-1)p}{4}\right] \\&\quad =\mathbf {Pr}\left[ \left. m-b(G)\ge \frac{(1-\epsilon )n(n-1)p}{4}~\right| A\right] -o(1)\\&\quad \ge \mathbf {Pr}\left[ \left( 1-\frac{\epsilon }{4}\right) \frac{n(n-1)p}{2}-\left( 1+\frac{\epsilon }{4}\right) \frac{n^2p}{4}\ge \frac{(1-\epsilon )n(n-1)p}{4}\right] -o(1) \\&\quad =\mathbf {Pr}\left[ \left( 1+\frac{\epsilon }{2}\right) (n-1)\ge \left( 1+\frac{\epsilon }{4}\right) n\right] -o(1). \end{aligned}$$

Since $(1+{\epsilon }/{2})(n-1)\ge (1+{\epsilon }{/4})n$ holds for sufficiently large n, we deduce from (2) that

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

as desired. $\square$

Theorem 2

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

$$\begin{aligned} \mathbf {Pr}\left[ \tau _t(G)< 1.5(1-\epsilon )\nu _t(G)\right] = o(1). \end{aligned}$$

Proof

Let A denote the event that

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

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

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

which establishes the theorem. $\square$

4 Conclusion and future work

We consider Tuza’s conjecture on random graphs, under the probability model $\mathcal {G}(n,p)$. Two results are following:

• 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[ \tau _t(G)\le 1.5(1+\epsilon )\nu _t(G)\right] =1-o(1). \end{aligned}$$

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

  $$\begin{aligned} \mathbf {Pr}\left[ \tau _t(G)< 1.5(1-\epsilon )\nu _t(G)\right] =o(1). \end{aligned}$$

Combining the above two probability results, we show that the ratio of $\tau _t(G)$ and $\nu _t(G)$ is approximately equal to 1.5 when p is a large constant: If $G\in \mathcal {G}(n,p)$ and $p\ge 0.791$, then for any $0<\epsilon <1$, it holds that

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

To a certain extent, these inequalities are stronger than that of Tuza’s conjecture on dense random graph.

Future work In dense random graphs, it is worth noting these results nearly imply the ratio of $\tau _t(G)/ \nu _t(G)$ is 1.5 holds with high probability. It is interesting to consider the same problem in sparse random graphs.