# Cover all triangles of a graph with n subgraphs as small as possible

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.

• (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? May 21, 2023 at 2:19
• @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. May 22, 2023 at 15:17
• 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. May 31, 2023 at 0:19