Maximum chordal subgraphs of random graphs

Abstract

We find asymptotics of the maximum size of a chordal subgraph in a binomial random graph $G(n,p)$, for $p=\mathrm{const}$ and $p=n^{-\alpha +o(1)}$.

1. Introduction

A chordal graph is a graph with no induced cycles of length at least 4. Chordal graphs are one of the most studied classes of perfect graphs and graphs in general due to their beautiful characterisations, useful and diverse properties, and various applications: chordal graphs arise in constraint programming, relational databases, Bayesian networks for probabilistic reasoning, register allocation, etc. In particular, chordal completions of graphs are used to characterise some graph classes, to define the treewidth, and are related to important computational problems (see [17]). Structural properties of this family of graphs help in solving hard problems (such as proper colouring, maximum clique, and independent set) efficiently. Chordal graphs are also used for reconstructing evolutionary trees [7] and are applied for semidefinite optimisation [31]. We refer the reader to [20, 21] for comprehensive surveys on chordal graphs.

Given the prominence of chordal graphs, it is natural to expect extremal problems involving them to be studied. For example, in 1985, Erdős and Laskar [15] posed the question about the maximum integer $\ell (n,m)$ such that every graph on $[n]:=\{1,\ldots,n\}$ with $m$ edges contains a chordal subgraph with at least $\ell (n,m)$ edges. The question was answered by Gishboliner and Sudakov in [19] – they determined the value of $f(n,m)$ for all $m$ up to a $O(\sqrt{n})$ additive term and found the exact value for all $m\leq \frac{n^2}{3}+1$ . In particular, if $m\lt (1-\varepsilon )\tiny\left(\begin{array}{c}n\\2\end{array}\right)$ , then $f(n,m)\lt Cn$ for some $C=C(\varepsilon )\gt 0$ , and this is not surprising since a $K_s$ -free graph on $n$ vertices does not contain a chordal subgraph with more than $(s-2)n$ edges, and for $s$ large enough, there are $K_s$ -free graphs with $m$ edges.

In the last decades, there has been a great interest in investigating (or even transferring results related to) extremal combinatorial questions in random graph settings. Most attention was given to the Turán’s problem (see, e.g. [6, 9, 11, 22, 25, 30]), and, more generally, to determining the maximum number of edges in a subgraph of random graph that belongs to a given family of graphs (see, e.g. [2, 5, 8, 12, 16]).

Here we consider an extremal question about chordal subgraphs in a random setting. Gishboliner in his talk [18] asked the following average-case question: what is the size $X_n$ of a largest chordal subgraph in the binomial random graph $G(n,p=\mathrm{const})$ ? In the paper, we answer this question asymptotically. We also find asymptotics of the maximum size of a chordal subgraph in $G(n,n^{-\alpha +o(1)})$ for all $\alpha \neq \frac{1+k}{1+2k}$ , $k\in \mathbb{Z}_{\geq 0}$ .

We will make use of an equivalent definition of chordal graphs. In particular, it can be used to get a simple upper bound on the maximum size of a chordal subgraph in a random graph, as we show below. Let us recall that a perfect elimination ordering $v_1\prec \ldots \prec v_n$ of the vertices of a graph $H$ satisfies the following requirement: for every $i\in [n]$ , the set of outgoing neighbours (i.e. the neighbours of $v_i$ among $v_1,\ldots,v_{i-1}$ ) induces a clique in $H$ . It is easy to see that the existence of a perfect elimination ordering implies that $H$ is chordal. The opposite is also true; thus, a graph is chordal if and only if it admits a perfect elimination ordering of its vertices [14], [32, Chapter 5].

Assuming that a chordal graph $H$ on $[n]$ has $\ell$ edges, we get that for any perfect elimination ordering, a certain vertex has at least $\ell/n$ outgoing neighbours; thus $H$ has a clique with more than $\ell/n$ vertices. Therefore, bounding the clique number of a graph provides an immediate upper bound on the maximum size of its chordal subgraph. Let $p=\mathrm{const}\in (0,1)$ . Let us recall that whp1 the clique number of $G_n\sim G(n,p)$ equals $(2-o(1))\log _{1/p}n$ , and one can cover $n(1-o(1))$ vertices by cliques of about this size [23, Theorem 7.1, Lemma 7.13]. On the one hand, it immediately implies that whp $X_n\leq 2n\log _{1/p}n$ . On the other hand, since a disjoint union of cliques is chordal, we get $X_n\geq (1-o(1))n\log _{1/p}n$ whp. We shall prove that neither of these bounds is asymptotically tight.

Let $\gamma$ be the unique solution in $(\max \{1,2p\},2)$ of the equation

(1) \begin{equation} \gamma \ln \frac{2}{\gamma }+(2-\gamma )\ln \frac{2}{2-\gamma }=(2-\gamma )\ln \frac{1}{1-p}-(1-\gamma )\ln \frac{1}{p}. \end{equation}

Note that a solution in $(\max \{1,2p\},2)$ of (1) is indeed unique: denote the difference between the left-hand side and the right-hand side in (1) by $g(\gamma )$ . Since $g^{\prime}(\gamma )=\ln \frac{(2-\gamma )p}{\gamma (1-p)}$ , thus $g$ decreases on $(2p,2)$ . On the other hand, the values of this difference at $2p$ and $1$ equal $g(2p)=\ln \frac{1}{p}\gt 0$ and $g(1)=\ln (4(1-p))$ , which is positive whenever $p\lt \frac{3}{4}$ . It remains to observe that $\max \{1,2p\}=2p$ when $p\geq \frac{3}{4}$ and that $g(2^-)=-\ln \frac{1}{p}\lt 0$ .

Theorem 1. Let $p=\mathrm{const}\in (0,1)$ . Then whp $\left |X_n-\gamma n\log _{1/p} n\right |\leq 10n\log _{1/p}\log n$ .

Note that $\gamma \gt 1$ , so a union of disjoint cliques of size $(2-o(1))\log _{1/p}n$ is indeed not an asymptotically optimal choice of a chordal subgraph. In particular, when $p=1/2$ , then $\gamma =1.7799\ldots$ satisfies $\gamma \ln \frac{2}{\gamma }+(2-\gamma )\ln \frac{2}{2-\gamma }=\ln 2.$ We prove Theorem 1 in Section 2. Note that $\gamma$ is chosen so that $\mathbb{P}(\mathrm{Bin}(k,p)=s)=n^{-1+o(1)}$ for $k\sim 2\log _{1/p}n$ and $s\sim \gamma \log _{1/p}n$ – see Claim 2.2. This equality is crucial for both the upper and the lower bounds on $X_n$ that are proven in Sections 2.2 and 2.3, respectively. In particular, it guarantees that, for an appropriately chosen $k$ and $s$ as above, whp every vertex of $[n]\setminus [n/\ln n]$ has $s$ neighbours in some $k$ -clique which is entirely inside $[n/\ln n]$ . This observation facilitates proving the lower bound – see Section 2.2 for details.

We then investigate the problem of tractability of searching for large chordal subgraphs in random graphs. In Section 3, we show that there is a polynomial-time algorithm that finds in $G_n$ a chordal subgraph with $(1-o(1))n\log _{1/p}n$ edges whp and that a further improvement of this result is quite unlikely.

We also study maximum sizes of chordal subgraphs in sparse random graphs. Note that, when $p\lt n^{-\varepsilon }$ for some constant $\varepsilon \gt 0$ , whp $G_n\sim G(n,p)$ does not contain cliques of size $\lceil 2/\varepsilon \rceil +1$ implying that whp $G_n$ does not contain chordal graphs with at least $\lceil 2/\varepsilon \rceil n$ edges. We found asymptotics of the maximum size of a chordal subgraph of $G(n,n^{-\alpha +o(1)})$ for all positive constants $\alpha \neq \frac{1+k}{1+2k}$ , $k\in \mathbb{Z}_{\geq 0}$ .

First of all, for the very sparse case $p\leq c/n$ , for some constant $0\lt c\lt 1$ , recall that whp all (for $p=o(1/n)$ ) or nearly all (for $p=\Theta (1/n)$ ) edges of $G_n$ lie in tree components. Thus, by taking $F$ to be a maximal spanning forest of $G_n$ , we conclude that in this regime whp $X_n=\binom{n}{2}p(1+o(1))$ (unless $p=\Theta (n^{-2})$ – in that case the number of edges is not concentrated, and $X_n$ equals the number of edges, which is bounded in probability).

The following theorem establishes the limit in probability of $X_n/n$ when $p=n^{-\alpha +o(1)}$ , for $\alpha \in (0,1]$ such that $\alpha \neq \frac{1+k}{1+2k}$ , for all $k\in \mathbb{Z}_{\geq 0}$ .

Theorem 2. Let $p=n^{-\alpha +o(1)}$ , for a constant $\alpha \gt 0$ .

1. 1. If $\alpha \in (1/2,1]$ and $\alpha \notin \left \{\frac{1+k}{1+2k}:\,k\in \mathbb{Z}_{\geq 0}\right \}$ , then $X_n/n\stackrel{\mathbb{P}}\to \frac{1+2k_{\alpha }}{1+k_{\alpha }}$ , where $k_{\alpha }$ is the largest integer such that $\alpha \lt \frac{1+k_{\alpha }}{1+2k_{\alpha }}$ .

2. 2. For any $\alpha \in (0,1/2]$ , we have that $X_n/n\stackrel{\mathbb{P}}\to 1/\alpha$ .

The proof of Theorem 2 appears in Section 4. In Section 5, we pose several further questions.

2. Dense random graphs: proof of Theorem 1

2.1. Preliminaries

Let $p=\mathrm{const}\in (0,1)$ ,

\begin{equation*} k_+=k_+(n,p)=\lceil 2\log _{1/p}n\rceil, \quad k_-=k_-(n,p)=\lceil 2\log _{1/p}n-9\log _{1/p}\log _{1/p} n\rceil . \end{equation*}

We will use the following well-known bounds on the maximum size of a clique in $G_n$ (see, e.g. [23, Theorem 7.1, Lemma 7.13]).

Claim 2.1. Whp in $G_n$

1. 1. there are no cliques of size $k_+$ ;

2. 2. every set of vertices of size at least $\frac{n}{\ln ^2 n}$ contains a clique of size $k_-$ .

Also, for technical reasons, we need to estimate the probability that a fixed vertex sends $s=(\gamma +o(1))\log _{1/p} n$ edges to a fixed set of size about $(2+o(1))\log _{1/p}n$ . Note that, as follows from the claim below, $\gamma$ is defined in (1) in such a way that $\mathbb{P}[\mathrm{Bin}(k,p)=s]=n^{-1+o(1)}$ .

Claim 2.2. Let $x\neq \frac{1}{2(1-\log _{1/p}2/\gamma )}$ be an arbitrary (not necessarily positive) real number,

\begin{equation*} k=2\log _{1/p}n-x\log _{1/p}\log n +O(1),\quad s=\gamma \log _{1/p}n-x\log _{1/p}\log n +O(1) \end{equation*}

be integers. Then

\begin{equation*} \mathbb {P}[\mathrm {Bin}(k,p)=s]=\frac {1}{n}\exp \biggl [\ln \ln n\left (x\left (1-\log _{1/p}\frac {2}{\gamma }\right )-\frac {1}{2}\right )(1+o(1))\biggr ]. \end{equation*}

Proof. Set $\varepsilon =x\frac{\ln \ln n}{\ln n}$ . Then

\begin{align*}\tiny\left(\begin{array}{c}k\\s\end{array}\right) & =\Theta \left (\frac{1}{\sqrt{\ln n}}\left (\frac{k^k}{s^s(k-s)^{k-s}}\right )\right ) =\Theta \left (\frac{1}{\sqrt{\ln n}}\left (\frac{k}{s}\right )^s\left (\frac{k}{k-s}\right )^{k-s}\right )\\ &= \Theta \left (\frac{1}{\sqrt{\ln n}}\left (\frac{2-\varepsilon }{\gamma -\varepsilon }\right )^{(\gamma -\varepsilon )\log _{1/p} n}\left (\frac{2-\varepsilon }{2-\gamma }\right )^{(2-\gamma )\log _{1/p} n}\right )\\ &=\exp \left [\log _{1/p} n\left ((\gamma -\varepsilon )\ln \frac{2-\varepsilon }{\gamma -\varepsilon }+(2-\gamma )\ln \frac{2-\varepsilon }{2-\gamma }\right )-\frac{1}{2}\ln \ln n(1+o(1)))\right ]. \end{align*}

Since

\begin{align*} (\gamma -\varepsilon )\ln \frac{2-\varepsilon }{\gamma -\varepsilon } & +(2-\gamma )\ln \frac{2-\varepsilon }{2-\gamma } = (\gamma -\varepsilon )\ln \frac{2}{\gamma }+(\gamma -\varepsilon )\ln \left (1-\frac{\varepsilon }{2}\right )\\& -(\gamma -\varepsilon )\ln \left (1-\frac{\varepsilon }{\gamma }\right )+(2-\gamma )\ln \frac{2}{2-\gamma }+(2-\gamma )\ln \left (1-\frac{\varepsilon }{2}\right )\\[4pt]& =\gamma \ln \frac{2}{\gamma }+(2-\gamma )\ln \frac{2}{2-\gamma }-\varepsilon \ln \frac{2}{\gamma }+O(\varepsilon ^2), \end{align*}

we get that

\begin{align*}\tiny\left(\begin{array}{c}k\\s\end{array}\right) &=\exp \left [\log _{1/p} n\left (\gamma \ln \frac{2}{\gamma }+(2-\gamma )\ln \frac{2}{2-\gamma }-\varepsilon \ln \frac{2}{\gamma }\right )-\frac{1}{2}\ln \ln n(1+o(1))\right ]\\[4pt] &\stackrel{(1)}=\exp \left [\log _{1/p} n\left ((2-\gamma )\ln \frac{1}{1-p}-(1-\gamma )\ln \frac{1}{p}-\varepsilon \ln \frac{2}{\gamma }\right )-\frac{1}{2}\ln \ln n(1+o(1))\right ].\\ \end{align*}

Thus,

\begin{align*} \mathbb{P}[\mathrm{Bin}(k,p)=s]&=\tiny\left(\begin{array}{c}k\\s\end{array}\right)p^s(1-p)^{k-s}\\[4pt] &=\exp \biggl [\ln n\left ((2-\gamma )\log _{1/p}\frac{1}{1-p}+\gamma -\varepsilon \log _{1/p}\frac{2}{\gamma }-1\right )\\[4pt] &\quad \quad \quad \quad \quad -s\ln \frac{1}{p}-(k-s)\ln \frac{1}{1-p}-\left (\frac{1}{2}+o(1)\right )\ln \ln n\biggr ]\\[4pt] &=\frac{1}{n}\exp \biggl [\varepsilon \left (1-\log _{1/p}\frac{2}{\gamma }\right )\ln n-\frac{1}{2}\ln \ln n(1+o(1))\biggr ], \end{align*}

as needed.

Remark 2.1. In order to justify the choice of the constant factor in the second-order term in the definition of $k_-$ , let us observe that (1) implies

\begin{equation*} \log _{1/p}\frac {2}{\gamma }=1-\frac {1}{\gamma }-\frac {2-\gamma }{\gamma }\log _{1/p}\frac {2(1-p)}{2-\gamma }\lt \frac {1}{2} \end{equation*}

since $\gamma \lt 2$ and $\frac{2(1-p)}{2-\gamma }\gt 1$ . Thus, we get that there exists $\varepsilon =\varepsilon (p)\gt 0$ such that

\begin{align*} \mathbb{P}[\mathrm{Bin}(k,p)=s]\geq \frac{1}{n}\exp [\ln \ln n(x+\varepsilon -1-o(1))/2],\quad \textrm{if }x\gt 0,\\ \mathbb{P}[\mathrm{Bin}(k,p)=s]\leq \frac{1}{n}\exp [\ln \ln n(x-\varepsilon -1-o(1))/2],\quad \textrm{if }x\lt 0. \end{align*}

2.2. Lower bound

We let $n^{\prime}= \lfloor n/\ln n\rfloor$ and $k=k_-(n^{\prime},p)$ . Note that $k=(2-o(1))\log _{1/p}n$ . We then divide $[n]$ into two parts $V\sqcup U$ , where $V$ has size $n^{\prime}$ . Expose first the edges of $G_n$ spanned by $V$ . Due to Claim 2.1, whp there exists a set $V_0\subset V$ of size at most $n/\ln ^2 n$ such that $G(n,p)[V\setminus V_0]$ can be partitioned into cliques of size $k$ . Let $K_1,\ldots,K_m$ be such cliques, where

\begin{equation*} m=(1+o(1))\frac {n}{2\ln n\log _{1/p}n}. \end{equation*}

Let us now expose edges of $G_n$ between $V$ and $U$ . Let $s$ be the maximum integer such that

\begin{equation*} \mathbb {P}[\mathrm {Bin}(k,p)\geq s]\geq \mathbb {P}[\mathrm {Bin}(k,p)=s]\geq \frac {\ln ^4 n}{n}. \end{equation*}

Then a vertex $u\in U$ has at least $s$ neighbours in some $K_j$ , $j\in [m]$ , with probability at least

\begin{equation*} 1-\left (1-\frac {\ln ^4 n}{n}\right )^m=1- e^{-\Omega (\ln ^2n)}=1-o(1/n). \end{equation*}

By the union bound, whp, for every vertex $u\in U$ , there is $j\in [m]$ such that $u$ has at least $s$ neighbours in $K_j$ .

Consider a subgraph $H$ of $G_n$ obtained from the disjoint union of cliques $K_1,\ldots,K_m$ with vertices from $U$ , each sending $s$ edges to exactly one of the cliques. This graph has

\begin{equation*} m\tiny\left(\begin{array}{c}k\\2\end{array}\right)+s|U|\geq \gamma n\log _{1/p}n-9n\log _{1/p}\log n+O(n) \end{equation*}

edges due to Claim 2.2. Indeed, letting $x=9$ , we get from Claim 2.2, Remark 2.1, and the definition of $s$ that $s\gt \gamma \log _{1/p}n-9\log _{1/p}\log n +O(1)$ .

It remains to prove that $H$ is chordal. Consider any ordering of vertices of $H$ , where each vertex of $V$ precedes any vertex of $U$ . Obviously, this is a perfect elimination ordering implying that $H$ is chordal.

2.3. Upper bound

Let $k=k_+(n,p)$ . Letting

\begin{equation*} s=\gamma \log _{1/p}n+3\log _{1/p}\log n +O(1) \end{equation*}

to be an integer, we get that

(2) \begin{equation} \mathbb{P}[\mathrm{Bin}(k,p)=s]\leq \mathbb{P}[\mathrm{Bin}(\lfloor k+3\log _{1/p}\log n\rfloor,p)=s]\leq \frac{1}{n}\exp [-2\ln \ln n]. \end{equation}

The first inequality holds true since $\gamma \gt 2p$ and thus $\mathbb{P}[\mathrm{Bin}(y,p)=s]$ increases in $y$ on $[s,k+\delta (k)]$ for any choice of $\delta (k)=o(k)$ : indeed

\begin{equation*} \frac {\mathbb {P}[\mathrm {Bin}(y+1,p)=s]}{\mathbb {P}[\mathrm {Bin}(y,p)=s]}=\frac {(y+1)(1-p)}{y+1-s}\gt \frac {k(1+o(1))(1-p)}{k(1+o(1))-s}=\frac {2(1-p)+o(1)}{2-\gamma }\gt 1. \end{equation*}

The second inequality in (2) holds true due to Claim 2.2 and Remark 2.1. Let

\begin{equation*} \ell =sn=\gamma n\log _{1/p}n+3n\log _{1/p}\log n +O(n). \end{equation*}

We will prove that whp the maximum number of edges in a chordal subgraph of $G_n$ is less than $\ell$ , and this immediately implies the desired upper bound.

Let $H$ be a chordal graph, and assume we are given a perfect elimination ordering $v_1\prec \ldots \prec v_n$ of the vertices of $H$ . For every vertex $v_i$ , let $d(v_i)$ be the outdegree of $v_i$ , that is, the number of outgoing neighbours of $v_i$ , and let $K_{v_i}$ be the clique induced by $v_i$ and its outgoing neighbours. For every $i$ such that $d(v_i)\gt 0$ , let $\nu (v_i)$ be the last outgoing neighbour of $v_i$ in the given perfect elimination ordering. Consider a graph $T_{\prec }(H)$ on the vertex set $V(H)$ consisting of all edges $\{v_i,\nu (v_i)\}$ . Note that $T_{\prec }(H)$ is 1-degenerate; thus it is a forest.

We further assume that $H$ is connected. In this case, for any perfect elimination ordering $\prec$ , we have that $T=T_{\prec }(H)$ is a tree. Indeed, it is sufficient to show that, for every pair of vertices $v_j\prec v_i$ forming an edge of $H$ , there is a path in $T$ from $v_i$ to $v_j$ . If $\nu (v_i)=v_j$ , then $\{v_j,v_i\}$ is an edge of $T$ itself. Otherwise, $v_j\prec \nu (v_i)\prec v_i$ , $\{v_i,\nu (v_i)\}$ is an edge of both $T$ and $H$ , and thus $\{v_j,\nu (v_i)\}$ is an edge of $H$ . By induction, we eventually will get a path from $v_i$ to $v_j$ in $T$ . Let us call $T$ a perfect elimination tree of $H$ , and let $v_1$ be the root of $T$ . Note that any layer-preserving ordering of the vertices of $T$ (i.e. vertices that are further from the root in $T$ occur later in this ordering) is a perfect elimination ordering of $H$ .

For any rooted tree $T$ on $[n]$ , there is at least one connected chordal graph $H$ such that $T$ is its perfect elimination tree (actually we may take $H=T$ ). In order to recover an $H$ (uniquely) from $T$ , we also equip $T$ with additional data: assume that $v_1\prec \ldots \prec v_n$ is a layer-preserving ordering of the vertices of $T$ and assign to each vertex $v_i$ , $i\geq 2$ , a vector $\textbf{e}_i\in \{0,1\}^{k_i}$ that encodes the outgoing neighbourhood of the vertex $i$ in $H$ , where $k_i=|K_{\nu (v_i)}|-1$ (see Fig. 1). Thus, in $H$ , the vertex $i$ is adjacent to a vertex $j\lt \nu (v_i)$ if and only if $j\in K_{\nu (v_i)}$ and the respective coordinate of $\textbf{e}_i$ equals 1. Note that $k_2=0$ , and for every $i\geq 3$ , vectors $\textbf{e}_j$ , $j\leq i-1$ , define $k_i$ uniquely.

Figure 1. Reconstruction of $H$ from $T$ .

We can now estimate the expected number of rooted trees $T$ on $[n]$ such that in $G_n$ there exists a connected chordal subgraph $H$ with the following properties:

• $H$ has at least $\ell$ edges,

• $H$ does not have cliques of size $k$ ,

• $T$ is a perfect elimination tree of $H$ .

For our goal, it is sufficient to prove that this expectation approaches 0 due to Claim 2.1.1. In particular, since whp $G_n$ is connected, a chordal subgraph with the maximum number of edges is also connected (any disconnected chordal subgraph on $[n]$ can be supplemented by an edge between any pair of connected components); thus the connectivity assumption does not cause a loss of generality. There are $n^{n-1}$ ways to construct a rooted tree $T$ . Take a rooted tree $T$ and consider any layer-preserving ordering $\prec$ . Without loss of generality, we assume that this ordering is defined by the identity permutation on $[n]$ . Thus, the desired expectation is bounded from above by $\rho n^{n-1}$ , where $\rho$ is the maximum (over $T$ ) probability that $G_n$ has a chordal subgraph $H$ with $T=T_{\prec }(H)$ , at least $\ell$ edges, and without cliques of size $k$ . Let us expose the edges of $G_n$ in the following order that $\prec$ induces on the pairs $u\lt v$ of vertices in $[n]$ : $(u,v)\lt (u^{\prime},v+1)$ for any $u^{\prime}$ , and $(u,v)\lt (u+1,v)$ . For any $v\geq 2$ , as soon as $G_n[\leq v-1]$ is exposed, the outdegree of $v$ to the clique $K_{\nu (v)}$ (note that $\nu (v)$ is defined by $T$ ) has binomial distribution with $k_{\nu }(v)+1$ trials, and $k_{\nu }(v)+1$ is uniquely defined by $G_n[\leq v-1]$ . Let us also recall that each $k_{\nu (v)}+1$ should be at most $k$ . We then get that $d(2)+\ldots +d(n)$ is stochastically dominated by the sum of $n-1$ independent $\mathrm{Bin}(k,p)$ random variables implying

\begin{align*} \rho \leq \mathbb{P}[d(2)+\ldots +d(n)\geq \ell ]\leq \mathbb{P}[\mathrm{Bin}(kn,p)\geq \ell ]&\stackrel{(*)}\leq kn\mathbb{P}[\mathrm{Bin}(kn,p)=\ell ]\\ &= kn\tiny\left(\begin{array}{c}kn\\\ell\end{array}\right)p^{\ell }(1-p)^{kn-\ell }. \end{align*}

The inequality (*) holds since $\ell \gt (1+\varepsilon )knp$ for a sufficiently small constant $\varepsilon \gt 0$ (that follows immediately from $p\lt \gamma/2$ ), and so $\tiny\left(\begin{array}{c}kn\\x\end{array}\right)\left (\frac{p}{1-p}\right )^x$ decreases on $[\ell,kn]$ (see, e.g. [4, Chapter 1.2]). Let us note that, for all $n$ large enough,

\begin{align*}\tiny\left(\begin{array}{c}kn\\\ell\end{array}\right)=\tiny\left(\begin{array}{c}kn\\sn\end{array}\right) &=\frac{(1+o(1))\sqrt{k}}{\sqrt{2\pi s(k-s)n}}\cdot \frac{(kn)^{kn}}{(sn)^{sn}(kn-sn)^{n(k-s)}}\\ & \leq \left (\frac{k^k}{s^s(k-s)^{k-s}}\right )^n \\ &=\left ((1+o(1))\frac{\sqrt{2\pi s(k-s)}}{\sqrt{k}}\tiny\left(\begin{array}{c}k\\s\end{array}\right)\right )^n \leq \left (\tiny\left(\begin{array}{c}k\\s\end{array}\right)\ln n\right )^n \end{align*}

implying that

\begin{equation*} \rho \leq kn(\ln n)^n\biggl (\mathbb {P}[\mathrm {Bin}(k,p)=s]\biggr )^n. \end{equation*}

Thus, the desired expectation is upper bounded by

\begin{equation*} k (n\ln n)^n \biggl (\mathbb {P}[\mathrm {Bin}(k,p)=s]\biggr )^n\leq k\exp [-n\ln \ln n]=o(1). \end{equation*}

The last inequality follows from (2), completing the proof.

3. Efficient search for large chordal graphs

Chordality of graphs can be efficiently tested, and a perfect elimination ordering of vertices of a chordal graph can be found in linear time [28]. Thus, if with bounded away from 0 probability it is possible to find in $G_n$ a chordal graph of size at least $(1+\varepsilon )n\log _{1/p}n$ in polynomial time, then it is also possible to find a clique of size $(1+\varepsilon )\log _{1/p}n$ in polynomial time, but the latter is an open problem that has received a lot of attention in the past (see, e.g. [3, 10, 24, 26]). We show that a chordal graph of size $(1+o(1))n\log _{1/p}n$ can be found in $G_n$ in polynomial time whp which is, as observed, asymptotically tight unless the mentioned large clique search problem can be efficiently solved.

Let $m=\lfloor \ln ^2 n\rfloor$ , $k=\lfloor \log _{1/p}n-4\log _{1/p}\ln n\rfloor$ . For brevity, we call a path consisting of $m$ vertices, an $m$ -path.

Claim 3.1. There is a polynomial-time algorithm that finds in $G_n$ a union of $\lfloor n/m\rfloor$ disjoint $k$ -th powers of $m$ -paths whp.

Proof. We use an algorithm proposed by Alon and Füredi [1]. Let $n^{\prime}=\lfloor n/m\rfloor$ . Consider any balanced partition $[mn^{\prime}]=V_1\sqcup \ldots \sqcup V_m$ . We will order the vertices in every $V_i$ sequentially starting from $V_1$ . The first set is ordered arbitrarily: $V_1=\{v^1_1,\ldots,v^1_{n^{\prime}}\}$ . Let $i\in \{2,\ldots,m\}$ , and assume that, for every $i^{\prime}\leq i-1,$ $V_{i^{\prime}}=\{v^{i^{\prime}}_1,\ldots,v^{i^{\prime}}_{n^{\prime}}\}$ is already ordered in such a way that, for every $j\in [n^{\prime}]$ , the vertex $v^{i^{\prime}}_{j}$ is adjacent to each of $v^{\max \{1,i^{\prime}-k\}}_{j},\ldots,v^{i^{\prime}-1}_{j}$ . Consider an auxiliary bipartite graph $H_i$ with equal parts $V_i=\{v_1,\ldots,v_{n^{\prime}}\}$ (the order is initially arbitrary), $U_i$ , where the $j$ -th vertex of $U_i$ is

\begin{equation*} \textbf {u}^i_j=\left \{v^{\max \{1,i-k\}}_j,\ldots,v^{i-1}_j\right \}. \end{equation*}

We draw an edge between $v_{j^{\prime}}$ and $\textbf{u}^i_j$ if and only if $v_{j^{\prime}}$ is adjacent to each of $v^{\max \{1,i-k\}}_j,\ldots,v^{i-1}_j$ in $G_n$ . Note that, if we find a perfect matching $M_i$ (which is known to be solvable in polynomial time [27]) in $H_i$ , then we get the desired ordering of $V_i$ , and, eventually, $\cup _i M_i$ corresponds to a union of $k$ -th powers of $m$ -paths in $G_n$ as needed.

Observe that $H_i$ is a binomial bipartite graph with edges appearing with probability at least $p^k\geq \frac{\ln ^4 n}{n}$ . Thus, with probability $1-o(1/n)$ , it has a perfect matching (see, e.g. [4, Corollary 7.13]). By the union bound, every $H_i$ , $i\in [m]$ , contains a perfect matching $M_i$ , and we can order every $V_i$ in the desired way.

It remains to notice that a union of $\lfloor n/m\rfloor$ disjoint $k$ -th powers of $m$ -paths is a chordal graph with more than $\lfloor n/m\rfloor \left (m-k\right )k=kn(1-o(1))$ edges.

4. Sparse random graphs: proof of Theorem 2

For a sequence of graphs $G_n$ on $[n]$ and a fixed graph $F$ , an almost $F$ -tiling of $G_n$ is a sequence of subgraph $H_n\subset G_n$ on $n(1-o(1))$ vertices formed by disjoint unions of graphs isomorphic to $F$ . We need to recall the result of Ruciński [29] about the threshold for the existence of almost tilings in the random graph. Let us recall that the 1-density of $F$ is $\rho (F)=\frac{|E(F)|}{|V(F)|-1}$ . Let us call $F$ strictly 1-balanced, if every proper subgraph of $F$ has 1-density strictly less than $\rho (F)$ . The maximum 1-density of a graph $F$ is the maximum 1-density over all its subgraphs: $\rho ^*(F)=\max _{H\subseteq F}\rho (H)$ .

Theorem 4.1 (Ruciński [29])

Let $F$ be a graph with a maximum 1-density $\rho ^*$ and $p\gg n^{-1/\rho ^*}$ . Then whp $G(n,p)$ has an almost $F$ -tiling.

Let $p=n^{-\alpha +o(1)}$ , for a constant $\alpha \gt 0$ . We consider two cases from the statement of Theorem 2 separately: in Section 4.1, we denote by $k:=k_{\alpha }$ the largest integer such that $\alpha \lt \frac{1+k}{1+2k}$ and prove the theorem for $\alpha \in (1/2,1]$ ; in Section 4.2, we address the case $\alpha \in (0,1/2]$ .

4.1. $\alpha \gt 1/2$

If $\frac{1}{n}\ll p\ll n^{-2/3}$ , then whp $G_n$ has a connected component of size $n(1-o(1))$ (see, e.g. [4, 23]) implying that whp $X_n\geq n-o(n)$ (a tree that covers almost all vertices of $G_n$ is chordal). On the other hand, the expected number of triangles is $o(n)$ , and the expected number of 4-cliques is $o(1)$ implying that whp there are $o(n)$ triangles and no 4-cliques by Markov’s inequality. Then, whp for any chordal graph $H\subset G_n$ and its perfect elimination ordering, no vertices have outdegree 3, and $o(n)$ vertices have outdegree 2. Thus, whp $X_n\leq n+o(n)$ . We eventually get that $X_n/n\stackrel{\mathbb{P}}\to 1$ .

Other $\alpha \gt \frac{1}{2}$ can be handled similarly: let $n^{-\frac{1+k}{1+2k}}\ll p \ll n^{-\frac{2+k}{3+2k}}$ for some integer $k\geq 1$ . Let $H$ be the square of a path of length $k+1$ . Consider a graph $F=F(M)$ obtained by gluing sequentially $M$ copies of $H$ : the first vertex of the $i$ -th copy is glued with the last vertex of the $(i-1)$ -th copy. Note that $F$ is chordal and its maximum 1-density equals $\rho ^*(F)=\rho ^*(H)=\frac{1+2k}{1+k}$ . By Theorem 4.1, whp there exists an almost $F$ -tiling in $G_n$ . In other words, whp there is a disjoint union of copies of $F$ (which is chordal) that cover $n(1-o(1))$ vertices of $G_n$ . Clearly, for every $\varepsilon \gt 0$ , there exists $M$ such that an almost $F$ -tiling has at least $(\frac{1+2k}{1+k}-\varepsilon )n$ edges for $n$ large enough. Thus, whp $X_n/n\geq \frac{1+2k}{1+k}-o(1)$ .

It remains to show that whp $X_n/n\leq \frac{1+2k}{1+k}+o(1)$ . For every positive integer $i$ , let $\mathcal{H}_i$ be the family of all chordal graphs on $0\sqcup [i]$ that can be obtained in the following way:

• $0$ and $1$ are adjacent,

• for every $j\in [i-1]$ , the vertex $j+1$ is adjacent to at least 2 vertices in $0\sqcup [j]$ ,

• for every $j\in [i-1]$ , the neighbours of $j+1$ in $0\sqcup [j]$ , form a clique.

Note that each graph from $\mathcal{H}_i$ has $i+1$ vertices and at least $2i-1$ edges. Set $\mathcal{H}=\sqcup _{i\geq 1}\mathcal{H}_i$ .

Claim 4.2. Every 2-connected chordal graph $H$ is isomorphic to a graph from $\mathcal{H}$ .

Proof. Assume that $H$ does not have a copy in $\mathcal{H}$ . Let $\prec$ be a perfect elimination ordering of $H$ , and let $T$ be the respective perfect elimination tree of $H$ (see Section 2.3 for the definition of a perfect elimination tree). Without loss of generality, assume that $V(H)=\{0,1,\ldots,i\}$ , and $0\prec 1\prec \ldots \prec i$ . We then get that there exists a vertex $j\in \{2,\ldots,i\}$ such that its outdegree is at most 1. Let $\nu (j)$ be the parent of $j$ in $T$ . Let us consider a subtree $T^{\prime}$ of $T$ that is induced by $\nu (j)$ , $j$ , and all descendants of $j$ . We get that there are no edges between $V(T)\setminus V(T^{\prime})$ and $V(T^{\prime})\setminus \{\nu (j)\}$ in $H$ . Indeed, otherwise, let $j^{\prime}$ be the minimum vertex from $V(T^{\prime})\setminus \{\nu (j)\}$ that is adjacent to a vertex $u$ from $V(T)\setminus V(T^{\prime})$ . We have $j^{\prime}\neq j$ , and the parent $\nu (j^{\prime})$ of $j^{\prime}$ in $T^{\prime}$ is smaller than $j^{\prime}$ and should be adjacent to $u$ as well due to chordality – a contradiction.

Note that, for $i\gt i^{\prime}$ , if $H\in \mathcal{H}_i$ , then $H[\leq i^{\prime}]\in \mathcal{H}_{i^{\prime}}$ . Recall that every graph from $\mathcal{H}_i$ has at least $2i-1$ edges. Thus, by Markov’s inequality, there exists $M=M(k)$ such that whp $G_n$ does not have a copy of any graph from $\mathcal{H}_M$ , and, therefore, whp $G_n$ does not have a copy of any graph from $\mathcal{H}_{\geq M}$ . Let $\mathcal{H}^{\prime}\subset \sqcup _{i=1}^{k+1}\mathcal{H}_i$ be the set of all graphs $H$ from $\sqcup _{i=1}^{k+1}\mathcal{H}_i$ that have at least $2|V(H)|$ edges (i.e. $H\in \mathcal{H}_i$ belongs to $\mathcal{H}^{\prime}$ if and only if there exists $j\leq i$ sending at least 3 edges to $0\sqcup [j-1]$ in $H$ ). Let $\mathcal{H}^{\prime\prime}=\sqcup _{i=k+2}^{M-1}\mathcal{H}_i$ . We then observe that, for every graph $H\in \mathcal{H}^{\prime}\sqcup \mathcal{H}^{\prime\prime}$ , the expected number of subgraphs isomorphic to $H$ in $G_n$ is $o(n)$ : a graph $H\in \mathcal{H}^{\prime}$ on $i+1$ vertices has at least $2i$ edges, and thus the expected number of copies of $H$ in $G_n$ is $O(n^{i+1}n^{-2i\alpha })=O(n^{1+i(1-2\alpha )})=o(n)$ . In the same way, a graph $H\in \mathcal{H}^{\prime\prime}$ on $i+1$ vertices has at least $2i-1$ edges; thus the expected number of copies of $H$ in $G_n$ is $O(n^{i+1}n^{-(2i-1)\alpha })=O(n^{1+(k+2)-(2k+3)\alpha })=o(n)$ . By Markov’s inequality, whp there are $o(n)$ subgraphs isomorphic to a graph from $H\in \mathcal{H}^{\prime}\sqcup \mathcal{H}^{\prime\prime}$ in $G_n$ .

Now, let us consider an arbitrary chordal subgraph $F\subset G_n$ , and let $\Sigma$ be the set of all its non-empty blocks (i.e. inclusion-maximal 2-connected subgraphs and edges that do not belong to any cycle, see [13, Chapter 3.1]). Without loss of generality, we may assume that $F$ is connected (in particular, there are no empty blocks) since whp $G_n$ is connected, and so the same is true for any its inclusion-maximal chordal subgraph. Note that every edge of $F$ belongs to some graph in $\Sigma$ . By Claim 4.2, we get that whp all graphs from $\Sigma$ have copies in $\sqcup _{i=1}^{M-1}\mathcal{H}_i$ . Moreover, whp the total number of edges in the graphs from $\Sigma$ that have copies in $\mathcal{H}^{\prime}\sqcup \mathcal{H}^{\prime\prime}$ is $o(n)$ . For every $H\in \Sigma$ that has a copy in $\sqcup _{i=1}^{k+1}\mathcal{H}_i\setminus \mathcal{H}^{\prime}$ , we get that $H$ has at most $k+2$ vertices, and $|E(H_i)|=2|V(H_i)|-3$ . Since the block-cutpoint graph is a tree, we get that there is an ordering of graphs from $\Sigma =\{H_1,\ldots,H_K\}$ such that, for every $i$ , $H_i$ has at most 1 common vertex with $H_1\cup \ldots \cup H_{i-1}$ . So, $|E(H_i)\setminus E(H_1\cup \ldots \cup H_{i-1})|=|E(H_i)|$ while $|V(H_i)\setminus V(H_1\cup \ldots \cup H_{i-1})|\geq |V(H_i)|-1=i$ . Letting $x_H$ be the number of graphs from $\Sigma$ isomorphic to $H$ , we get that whp

\begin{equation*} \rho (F)\leq \frac {o(n)+\sum _{i=1}^{k+1}\sum _{H\in \mathcal {H}_i\setminus \mathcal {H}^{\prime}}(2i-1)x_H}{\sum _{i=1}^{k+1}\sum _{H\in \mathcal {H}_i\setminus \mathcal {H}^{\prime}}ix_H}\leq \frac {1+2k}{1+k}+o(1). \end{equation*}

The latter inequality hods true since $F$ is connected implying that the denominator in the left-hand side fraction is linear in $n$ . Thus, the number of edges in $F$ is at most $\frac{1+2k}{1+k}n+o(n)$ , completing the proof.

4.2. $\alpha \leq 1/2$

We first prove the upper bound: let us fix $\varepsilon \gt 0$ and prove that whp $X_n\leq (1/\alpha +\varepsilon )n$ . Since whp $G_n$ does not have $(\lceil 2/\alpha \rceil +1)$ -cliques, whp in a chordal subgraph of $G_n$ every vertex has outdegree at most $\lceil 2/\alpha \rceil$ . Moreover, arguing similarly to the proof of the upper bound of Theorem 1 from Section 2.3, we see that the expected number of chordal subgraphs of $G_n$ with at least $(1/\alpha +\varepsilon )n$ edges and outdegrees at most $\lceil 2/\alpha \rceil$ (for some perfect elimination ordering) can be upper bounded by

\begin{equation*} n^{n-1}A^n p^{(1/\alpha +\varepsilon )n}\leq (An^{1-1-\alpha \varepsilon +o(1)})^n=o(1) \end{equation*}

for some constant $A\gt 0$ . Here, $n^{n-1}$ is the number of rooted trees that can play a role of a perfect elimination tree and $A^n$ is the bound for the number of ways to choose vectors $\textbf{e}_i$ (see Section 2.3). Thus, by Markov’s inequality, we get that whp $X_n/n\leq 1/\alpha +o(1)$ as needed.

We then prove the lower bound. Let us first assume that $1/\alpha =\ell \geq 2$ is an integer. For every $j\in \mathbb{N}$ , consider the following chordal graph $F_j$ on $\{0\}\sqcup [j]$ : the vertex $i\in [j]$ is adjacent to its $\min \{j-1,\ell \}$ predecessors, that is, $F_j$ is the $\ell$ -th power of a path of length $\ell$ . Note that $F_j$ is a strictly 1-balanced graph with 1-density strictly less than $\ell$ and approaching $\ell$ with growing $j$ . By Theorem 4.1, for every $j$ , whp $G_n$ has an almost $F_j$ -tiling, implying that $X_n/n\geq (1/\alpha -o(1))$ whp.

Now, let $1/\alpha \notin \mathbb{Z}$ . Let $\ell$ be the minimum positive integer greater than $1/\alpha$ . Note that $\ell \geq 3$ . Let us consider the (unique) sequence $x_i$ , $i\in \mathbb{N}$ , satisfying the following conditions:

• $(x_1,\ldots,x_{\ell })=(1,2,\ldots,\ell )$ ;

• for every $i\geq \ell +1$ , we define recursively $x_i$ to be the maximum integer in $[2,\ell ]$ such that

  \begin{equation*} \rho _i:=\frac {x_1+\ldots +x_i}{i}\lt \frac {1}{\alpha }. \end{equation*}

Let us consider the sequence $(s_j)_{j\in \mathbb{N}}$ of all $s$ such that

• $\rho _s\gt \ell -1$ ,

• $\rho _s\gt \rho _i$ for all $i\lt s$ .

Since $\rho _i\uparrow 1/\alpha \gt \ell -1$ , there are infinitely many such $s$ . For every $j$ , set $\textbf{x}_j=(x_1,\ldots,x_{s_j})$ . Consider the following graph $F_j$ on $\{0\}\sqcup [s_j]$ : the vertex $i\in [s_j]$ is adjacent to its $x_i$ immediate predecessors. Note that $\rho _{s_j}$ is the 1-density of $F_j$ . Let us prove that $F_j$ is chordal. It is sufficient to show that the natural order of integers is perfect elimination. We first observe that, for every $i\gt \ell$ , we have $x_i\in \{\ell -1,\ell \}$ . Indeed, the inequality $x_1+\ldots +x_{i-1}\lt \frac{1}{\alpha }(i-1)$ that holds for all $i\gt \ell$ , implies $x_1+\ldots +x_{i-1}+\ell -1\lt \frac{1}{\alpha }i$ since $\ell -1\leq \frac{1}{\alpha }$ . Also, the first $\ell +1$ vertices of $F_j$ compose a clique. Proceeding by induction, we get that any set of $\ell$ consecutive vertices in $F_j$ induces a clique. Thus, every $i\geq \ell +1$ is adjacent to at most its $\ell$ predecessors, and these predecessors induce a clique. So the considered order is indeed perfect elimination.

Since the 1-density of $F_j$ approaches $1/\alpha$ as $j$ grows, then, for every $\varepsilon \gt 0$ and large enough $j$ , an almost $F_j$ -tiling has at least $(1/\alpha -\varepsilon )n$ edges. Therefore, we conclude that $X_n/n\geq (1/\alpha -o(1))$ by applying Theorem 4.1 which is possible since all $F_j$ are strictly 1-balanced due to the following claim. This completes the proof of Theorem 2.

Claim 4.3. All graphs $F_j$ are strictly 1-balanced.

Proof. Fix $j$ and assume that $F_j$ is not strictly 1-balanced. Let $\tilde F$ be a proper subgraph of $F_j$ that has 1-density $\rho (\tilde F)\geq \rho _{s_j}$ . First of all, let us note that without loss of generality $\tilde F$ is connected since the 1-density of $\tilde F$ does not exceed 1-densities of all its connected components. Also, we may assume that $\tilde F$ is an induced subgraph.

Let us assume that in $\tilde F$ some intermediate vertices are missing, that is, there exist $i_-,i,i_+\in V(F_j)$ such that $i_-\lt i\lt i_+$ and $i_-,i_+\in V(\tilde F)$ , while $i\notin V(\tilde F)$ . Note that the number of consecutive missing vertices could not be bigger than $\ell -1$ since otherwise $\tilde F$ is not connected. Let $i\geq 1$ be the minimum number such that, for some $\mu \in [\ell -1]$ ,

\begin{align*} i,i+\mu +1\in V(\tilde F),\,\,\textrm{while }\,i+1,\ldots,i+\mu \notin V(\tilde F). \end{align*}

If $i\geq \ell -1$ , then the missing vertices from $[i+1,i+\mu ]$ add at least $\mu \ell \gt \mu/\alpha$ edges to $\tilde F$ . Indeed, every missing vertex sends at least $\ell -1$ edges to its immediate predecessors in $F_j$ and is adjacent to $i+\mu +1$ . Thus, the inequality $\rho (F_j)\leq \rho (\tilde F)$ implies $\rho (F_j)\lt \rho (\tilde F^{\prime})$ , where the graph $\tilde F^{\prime}$ is obtained from $\tilde F$ by adding back the vertices $i+1,\ldots,i+\mu$ . If $i\lt \ell -1$ , then $i+1$ vertices $i^{\prime}\leq i$ contribute at most $(\ell -1)(i+1)$ edges to $E(\tilde F)$ . Indeed, every vertex $i^{\prime}\leq i$ is adjacent to at most $\ell$ and at least $\ell -1$ its immediate successors in $F_j$ . Since the missing vertex $i+1$ is adjacent to all $i^{\prime}\leq i$ in $F_j$ , we get that every $i^{\prime}\leq i$ is adjacent to at most $\ell -1$ its successors in $\tilde F$ . Thus, the deletion of vertices $i^{\prime}\leq i$ from $\tilde F$ leads to the graph $\tilde F^{\prime}$ with $\rho (\tilde F^{\prime})\gt \rho (F_j)$ . We conclude that there is a proper subgraph in $F_j$ with the 1-density at least $\rho (F_j)$ and without missing intermediate vertices. Thus, without loss of generality, we may assume that $\tilde F$ is induced by $[i_-,i_+]$ for certain $0\lt i_-\lt i_+\leq s_j$ . Note that the first inequality is strict since otherwise we get a contradiction with the definition of $F_j$ .

Let $\nu \gt \ell$ be the minimum number such that $x_{\nu }=\ell -1$ . We have that, among the first $\nu -1$ elements of the sequence $\textbf{x}_j$ , there are exactly $\nu -\ell$ numbers equal to $\ell$ . Assume first that $\nu -\ell +1\leq i_-\leq \nu -1$ . Then the missing vertices $0,1,\ldots,i_-1$ add at least $(\ell -1)(i_-(\nu -\ell ))+\ell (\nu -\ell )$ edges to $\tilde F$ . Note that $\frac{(\ell -1)(i_-(\nu -\ell ))+\ell (\nu -\ell )}{i_-}$ is minimised at $i_-=\nu -1$ :

\begin{equation*} \frac {(\ell -1)(i_-(\nu -\ell ))+\ell (\nu -\ell )}{i_-}\geq \frac {(\ell -1)^2+\ell (\nu -\ell )}{\nu -1}. \end{equation*}

We also recall that

\begin{equation*} \frac {|E(F_j[\leq \nu -1])|+\ell }{(|V(F_j[\leq \nu -1])|-1)+1}=\frac {\ell (\ell -1)/2+(\nu -\ell +1)\ell }{\nu }\geq \frac {1}{\alpha }, \end{equation*}

implying that

\begin{align*} (\ell -1)^2+\ell (\nu -\ell ) & =\nu \ell -2\ell +1\geq \frac{\nu }{\alpha }+\frac{\ell ^2-\ell }{2}-2\ell +1\\ &\gt \frac{1}{\alpha }(\nu -1)+(\ell -1)+\frac{\ell ^2-\ell }{2}-2\ell +1\\ &=\frac{\nu -1}{\alpha }+\frac{\ell ^2-3\ell }{2}\geq \frac{\nu -1}{\alpha }, \end{align*}

since $\frac{1}{\alpha }\gt \ell -1$ and $\ell \geq 3$ . So, the “additional density” recovered by the vertices $0,1,\ldots,i_-1$ equals

\begin{equation*} \frac {(\ell -1)(i_-(\nu -\ell ))+\ell (\nu -\ell )}{i_-}\gt \frac {1}{\alpha }. \end{equation*}

If $i_-\leq \nu -\ell$ , then the missing vertices $0,1,\ldots,i_-1$ add at least $i_-\ell$ edges to $\tilde F$ . Thus, in both cases, the addition of vertices $0,1,\ldots,i_-1$ leads to the graph $\tilde F^{\prime}$ satisfying the inequality $\rho (\tilde F^{\prime})\gt \rho (F_j)$ – contradiction with the property of $F_j$ that all $F_j[\leq s]$ , $s\lt s_j$ , have smaller 1-densities.

It remains to consider the case $i_-\geq \nu$ . Clearly, we may assume that $\tilde F$ has at least $\ell +1$ vertices since otherwise $\rho (\tilde F)\leq \frac{\ell }{2}\lt \ell -1\lt \rho _{s_j}$ due to the fact that $\ell \geq 3$ and the choice of $s_j$ . Due to the definition of $\textbf{x}_j$ , we have that, for every $i\geq \nu$ ,

\begin{equation*} \frac {i}{\alpha }-1\leq x_1+\ldots +x_i\lt \frac {i}{\alpha }. \end{equation*}

Let $\delta _i:=\frac{i}{\alpha }-(x_1+\ldots +x_i)$ . We then get

(3) \begin{align} \frac{i_+-i_-}{\alpha }-(x_{i_-+1}+\ldots +x_{i_+}) &= \frac{i_+}{\alpha }-(x_1+\ldots +x_{i_+})- \left (\frac{i_-}{\alpha }-(x_1+\ldots +x_{i_-})\right )\notag \\ &\geq \delta _{i_+}-1. \end{align}

On the other hand, the vertex $x_{i_-+1}$ sends $1\leq (x_{i_-+1}-(\ell -2))$ edge to $x_{i_-}$ in $\tilde F$ , the vertex $x_{i_-+2}$ sends $2\leq (x_{i_-+2}-(\ell -3))$ edges to $\{x_{i_-},x_{i_+}\}$ in $\tilde F$ , etc., implying

\begin{equation*} \rho (\tilde F) \leq \frac {x_{i_-+1}+\ldots +x_{i_+}-(1+\ldots +\ell -2)}{i_+-i_-} \leq \frac {x_{i_-+1}+\ldots +x_{i_+}-1}{i_+-i_-}. \end{equation*}

Therefore, due to (3), we get

\begin{align*} \rho (\tilde F) & \leq \frac{x_{i_-+1}+\ldots +x_{i_+}-1}{i_+-i_-}\\ &\leq \frac{(i_+-i_-)/\alpha -\delta _{i_+}+1-1}{i_+-i_-}\\ &=\frac{1}{\alpha }-\frac{\delta _{i_+}}{i_+-i_-}\lt \frac{1}{\alpha }-\frac{\delta _{i_+}}{i_+}\\ &=\rho (F_j[\{0,1,\ldots,i_+\}])\leq \rho (F_j) \end{align*}

by the definition of $F_j$ – a contradiction.

5. Concluding remarks

In this paper, we study maximum chordal subgraphs in random graphs. We have found asymptotics of maximum sizes of chordal subgraphs in dense and sparse random graphs.

We believe that the concentration interval in Theorem 1 is not optimal, and in particular, there exist $c\in \mathbb{R}$ and $C\gt 0$ such that whp

\begin{equation*} \left |X_n-\gamma n\log _{1/p} n-cn\log _{1/p}\log n\right |\leq Cn. \end{equation*}

Unfortunately, our techniques do not seem sufficient even to achieve the constant factor in the second-order term. Also, we are inclined to believe that $X_n$ is not concentrated in any interval of length $o(n)$ .

Note that whp the maximum size of a chordal subgraph of $G(n,c/n)$ , $c\gt 0$ , is $n-Y_n+o(n)$ , where $Y_n$ is the number of connected components since whp $G(n,c/n)$ has $o(n)$ triangles. Thus $X_n/n\stackrel{\mathbb{P}}\to 1-\gamma (c)\in (0,1)$ , where $\gamma (c)$ is the limit in probability of $Y_n/n$ , which is well known [4, Theorem 6.12]:

\begin{equation*} \gamma (c)=\frac {1}{c}\sum _{i=1}^{\infty }\frac {i^{i-2}}{i!}(c e^{-c})^i. \end{equation*}

In the same way, we believe that, for every $k\in \mathbb{N}$ and $\alpha =\frac{1+k}{1+2k}$ , letting $p=cn^{-\alpha }$ , we would get

(4) \begin{equation} X_n/n\stackrel{\mathbb{P}}\to \gamma _k(c)\in \left (\frac{2k-1}{k},\frac{2k+1}{k+1}\right ), \end{equation}

where $\gamma _k(c)$ increases in $c$ , and $\lim _{c\to 0}\gamma _k(c)=\frac{2k-1}{k}$ , $\lim _{c\to \infty }\gamma _k(c)=\frac{2k+1}{k+1}$ . A possible approach for proving (4) is to analyse the behaviour of inclusion-maximal subgraphs in $G(n,p)$ consisting of blocks of chordal graphs with the outdegree sequence $0,1,2,\ldots,2$ of length $k+3$ .

It would be interesting to study maximum sizes of subgraphs of the random graphs that belong to other families of perfect graphs (interval graphs, strongly chordal graphs, co-graphs, etc.). Note that the maximum size of a perfect graph in $G(n,p=\mathrm{const})$ equals $(1/4+o(1))pn^2$ whp, and the same is true for any hereditary family that contains all bipartite graphs but does not contain at least one 3-colourable graph [2].