What is the smallest number $s(n,\Delta)$ such that for any undirected simple graph $G=(V,E)$ with $n$ vertices and $\Delta$ triangles, there exist $n$ subgraphs of $G$ covering all triangles where each subgraph contains $s(n,\Delta)$ edges?

(Definitions) A triangle is a triple $u,v,w\in V$ such that $(u,v),(v,w),(w,u)\in E$. A subgraph is an edge subset $E'\subseteq E$. $n$ subgraphs cover all triangles means for any triangle $u,v,w$, there exists a subgraph $E'$ such that $(u,v),(v,w),(w,u)\in E'$.

(Related Works) It is known that $s(n,\Delta)=O(n^{4/3})$ [Dolev, Lenzen, Peled, DISC'12] in the following way. Divide the vertex set into $n^{1/3}$ subsets $V_1,...,V_{n^{1/3}}$ each with size $n^{2/3}$; for each triple $(i,j,k)\in [n]\times[n]\times[n]$, create a subgraph induced by the vertex set $V_i,V_j,V_k$. There are $n$ subgraphs each with $n^{4/3}$ edges, and each triangle of this graph must be contained in one of them.

The first question to ask is whether $s(n,n^{2.9})=O(n^{4/3-\epsilon})$ for some small constant $\epsilon$, i.e., when graph contains sub-cubic triangles, can we do better? My guess is $s(n,n^{2.9})=\Omega(n^{4/3-o(1)})$, but I did not find a way to prove it.

  • $\begingroup$ (i) Can you prove it for the special case where the graph is a random $n$-vertex graph where each edge is present with probability $p=n^{-0.1}$, so that w.h.p. the number of triangles is $O(n^{2.7})$? (ii) What is known about the tightness of the upper bound you mention in related works? $\endgroup$
    – Neal Young
    May 21, 2023 at 2:19
  • 1
    $\begingroup$ @NealYoung (i) When the graph is a random graph, use idea from the related work, each subgraph induced by $V_i, V_j, V_k$ will contain $O(n^{4/3-0.1})$ edges, which already gives a solution to cover all triangles with $O(n^{4/3-0.1})$ size subgraphs, so "my guess" doesn't work for a random graph. (ii) The related work does not consider any kind of tightness. They are devising an algorithm and the theorem becomes a side product. $\endgroup$
    – walydna
    May 22, 2023 at 15:17
  • $\begingroup$ Not an answer, but I'm pretty sure one can prove that size $\Omega(n^{4/3})$ is necessary for the complete graph. Maybe some ideas of the proof could be useful in attacking the posted question. $\endgroup$
    – Neal Young
    May 31, 2023 at 0:19


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.