Sharp with-high-probability asymptotics of clique coverings of the random graph $G(n,p)$ for constant edge probability

The edge clique cover number $cc(G)$ , also denoted $\theta_1(G)$ , is the minimum number of cliques needed to cover all edges of a graph $G$ ; by a classical theorem of Erdős, Goodman and Pósa it equals the intersection number of $G$ , the minimum ground-set size in a set-intersection representation of $G$ . Bollobás, Erdős, Spencer and West (1993) proved that for the random graph $G(n,1/2)$ this parameter is, with high probability, at least $(1-o(1))\,n^2/(2\lg n)^2$ and at most $O(n^2\ln\ln n/\ln^2 n)$ , and left its sharp behavior open, implicitly conjecturing that the $\ln\ln n$ loss is unnecessary (this is how Frieze and Reed read their result). Frieze and Reed (1995) settled this order-of-magnitude question, proving $\Theta(n^2/\ln^2 n)$ for every constant edge probability $p$ , and Guo, Patton and Warnke (2023) extended the correct order to clique partitions and to local-load parameters (thickness and chromatic index of clique covers), showing moreover that one clique partition achieves all bounds simultaneously up to constants. The sharp leading constants nevertheless remain unknown and are the subject of Guo–Patton–Warnke's Problem 1: determine the with-high-probability asymptotics of $cc(G(n,p))$ , $cp(G(n,p))$ , $cc_\Delta(G(n,p))$ and $cc'(G(n,p))$ for constant $p\in(0,1)$ . The best lower bounds (their Lemma 20) carry a factor $1+\varphi(p)$ over the naive counting bound, where $\varphi(p)=(1-p)\log(1-p)/(p\log p)$ satisfies $\varphi(1/2)=1$ , so at $p=1/2$ the conjectured value is $n^2/(2\lg n)^2$ , matching the 1993 lower bound.

Background

Throughout, $\lg$ denotes $\log_2$ and $\ln$ the natural logarithm. The binomial random graph $G(n,p)$ is the graph on $n$ labeled vertices in which each of the $\binom{n}{2}$ possible edges is present independently with probability $p$ ; a property holds with high probability (whp) if its probability tends to $1$ as $n\to\infty$ . A clique of $G$ is a set of pairwise adjacent vertices. The edge clique cover number (clique cover number) $cc(G)$ , also written $\theta_1(G)$ , is the minimum number of cliques whose union contains every edge of $G$ ; if the cliques are additionally required to be pairwise edge-disjoint, the minimum is the clique partition number $cp(G)\ge cc(G)$ . By a theorem of Erdős, Goodman and Pósa (1966), $cc(G)$ equals the intersection number $\theta(G)$ of $G$ : the minimum size of a ground set $S$ such that each vertex $v$ can be assigned a subset $A_v\subseteq S$ with $A_u\cap A_v\neq\emptyset$ exactly when $uv$ is an edge. Thus $cc(G)$ measures how economically a graph can be represented by set intersections, and for almost all graphs (the typical case $p=1/2$ ) it is a basic representation-theoretic parameter.

Two facts drive the random-graph version of the problem: whp $G(n,p)$ has about $\binom{n}{2}p$ edges, but its largest clique has only about $2\log_{1/p}n$ vertices, so any clique cover must consist of very many cliques of at most logarithmic size, and near-maximal cliques are scarce and hard to organize into a cover. Bollobás, Erdős, Spencer and West (1993) proved for $p=1/2$ that whp $(1-\varepsilon)\,n^2/(2\lg n)^2\le cc(G(n,1/2))\le c\,n^2\ln\ln n/\ln^2 n$ : the lower bound by a counting argument over all intersection representations of graphs with no clique larger than $(2+\varepsilon)\lg n$ , the upper bound by randomly selecting cliques of size $c\lg n$ with $c<2$ . Their motivation included the interval number $i(G)$ , the minimum $t$ such that $G$ is the intersection graph of vertex sets each expressible as a union of at most $t$ closed intervals on the real line, and toward that application they also proved a stronger almost-covering statement in which no vertex belongs to too many of the selected cliques.

Frieze and Reed (1995) removed the $\ln\ln n$ factor up to constants: for every constant $p\in(0,1)$ there are constants $c_1,c_2>0$ such that whp $c_1 n^2/\ln^2 n\le cc(G(n,p))\le c_2 n^2/\ln^2 n$ , proved by a nibble argument (an iterative random selection of cliques of decreasing sizes that eventually covers every edge). They note that their method "does not seem to yield the correct value for $c_2$ ". Two local-load refinements sharpen the question. For a clique cover $\mathcal{C}$ of $G$ , the thickness $\Delta(\mathcal{C})$ is the maximum number of cliques of $\mathcal{C}$ containing a single vertex, and the chromatic index $\chi'(\mathcal{C})$ is the chromatic index of the clique hypergraph (the least number of colors needed to color the cliques so that intersecting cliques get different colors); minimizing these over all clique covers gives $cc_\Delta(G)$ and $cc'(G)$ . Füredi and Kantor (2017), applying the Frieze–Reed theorem to the Kneser rank of $G(n,p)$ (the smallest $k$ such that $G$ is an induced subgraph of a Kneser graph, the graph whose vertices are the $k$ -subsets of a set with disjointness as adjacency), proved $cc_\Delta(G(n,p))=\Theta(n/\log n)$ whp for constant $p$ and conjectured the same for $cc'$ .

Guo, Patton and Warnke (2023) settled those conjectures and determined the correct order of all four parameters for essentially all densities: for $n^{-2}\ll p\le 1-\gamma$ (with constant $\gamma\in(0,1)$ ) whp $cc(G(n,p))$ and $cp(G(n,p))$ are both $\Theta(n^2p/\log_{1/p}^2 n)$ , and for $n^{-1}\log n\ll p\le 1-\gamma$ whp $cc_\Delta(G(n,p))$ and $cc'(G(n,p))$ are both $\Theta(np/\log_{1/p} n)$ ; moreover, by their Theorem 7, whp $G(n,p)$ has a single clique partition simultaneously achieving the size and load bounds up to constants, which resolves the 1993 almost-covering formulation up to constants. However, for constant $p$ the sharp leading constants are unknown, and Guo–Patton–Warnke state that "our understanding of the asymptotics remains unsatisfactory, even on a heuristic level". Their Lemma 20 improves the counting lower bound to $(1-\varepsilon)(1+\varphi(p))\,\binom{n}{2}p/\binom{s}{2}$ for $cc$ and $(1-\varepsilon)(1+\varphi(p))\,np/(s-1)$ for $cc_\Delta$ , where $s=\lceil 2\log_{1/p}n\rceil$ and $\varphi(p)=(1-p)\log(1-p)/(p\log p)$ is increasing with $\varphi(1/2)=1$ ; at $p=1/2$ this is $n^2/(2\lg n)^2$ , matching the 1993 lower bound, and it refutes the natural guess $cc\sim\binom{n}{2}p/\binom{s}{2}$ for constant $p$ . In certain sparse regimes $p\to 0$ the sharp asymptotics are known and do equal the natural guess, so the constant-density case is genuinely different. Basu, Rödl and Sales (2024) extended the topic to $k$ -representation numbers (minimum size of a family of vertex subsets in which every edge is covered at least $k$ times and every non-edge at most $k-1$ times), whose $k=1$ case is the clique cover number; their results concern $k>1$ and cite the $k=1$ case as known up to constants. The interval number of random graphs, the original 1993 motivation, received separate attention (Scheinerman 1990; Balogh and Pluhár 2002), and the $\Theta(n/\log n)$ order for local clique-cover load underlies clique-cover-based representation parameters of almost all graphs, such as the Prague dimension of $G$ (the minimum number of complete graphs whose direct product contains $G$ as an induced subgraph, a parameter that differs from the clique-covering chromatic index $cc'(G)$ by at most an additive constant), determined as $\Theta(n/\log n)$ whp for constant $p$ by Guo–Patton–Warnke.

Problem Statement

Determine the sharp with-high-probability asymptotics of clique coverings of the random graph $G(n,p)$ for constant edge probabilities $p\in(0,1)$ — posed as Problem 1 by Guo, Patton and Warnke (2023), sharpening the question left open by Bollobás, Erdős, Spencer and West (1993). Concretely, for each constant $p\in(0,1)$ : (i) determine the whp asymptotics of the clique cover number $cc(G(n,p))$ and the clique partition number $cp(G(n,p))$ , conjecturally $(1+\varphi(p))\,\binom{n}{2}p/\binom{s}{2}$ with $s=\lceil 2\log_{1/p}n\rceil$ and $\varphi(p)=(1-p)\log(1-p)/(p\log p)$ ; and (ii) determine the whp asymptotics of the thickness $cc_\Delta(G(n,p))$ and the clique covering chromatic index $cc'(G(n,p))$ , conjecturally $(1+\varphi(p))\,np/(s-1)$ . The central special case is $p=1/2$ , descending directly from the 1993 paper, where the conjecture reads $cc(G(n,1/2))\sim n^2/(2\lg n)^2$ whp, matching the 1993 lower bound.

References

Paul Erdős, A. W. Goodman, Louis Pósa, The Representation of a Graph by Set Intersections, Canadian Journal of Mathematics 18 (1966), 106–112. DOI 10.4153/cjm-1966-014-3, https://doi.org/10.4153/cjm-1966-014-3.
Béla Bollobás, Paul Erdős, Joel Spencer, Douglas B. West, Clique coverings of the edges of a random graph, Combinatorica 13 (1993), 1–5. DOI 10.1007/BF01202786, https://doi.org/10.1007/BF01202786.
Alan Frieze, Bruce Reed, Covering the edges of a random graph by cliques, Combinatorica 15 (1995), 489–497. DOI 10.1007/BF01192522, https://doi.org/10.1007/BF01192522; full text at arXiv:1103.4870, https://arxiv.org/abs/1103.4870.
He Guo, Kalen Patton, Lutz Warnke, Prague Dimension of Random Graphs, Combinatorica 43 (2023), 853–884. DOI 10.1007/s00493-023-00016-9, https://doi.org/10.1007/s00493-023-00016-9; full text at arXiv:2011.09459, https://arxiv.org/abs/2011.09459.
Ayush Basu, Vojtěch Rödl, Marcelo Sales, The k-representation number of the random graph, preprint (2024), arXiv:2403.01563, https://arxiv.org/abs/2403.01563.
Zoltán Füredi, Ida Kantor, Kneser ranks of random graphs and minimum difference representations, arXiv:1701.08292 (2017), https://arxiv.org/abs/1701.08292; published as SIAM Journal on Discrete Mathematics 32 (2018), 1016–1028, DOI 10.1137/17M1114703, https://doi.org/10.1137/17M1114703.
Edward R. Scheinerman, On the interval number of random graphs, Discrete Mathematics 82 (1990), 105–109. DOI 10.1016/0012-365X(90)90050-R, https://doi.org/10.1016/0012-365X(90)90050-R.
József Balogh, András Pluhár, The interval number of dense graphs, Discrete Mathematics 256 (2002), 423–429. DOI 10.1016/S0012-365X(01)00215-1, https://doi.org/10.1016/S0012-365X(01)00215-1.