<p>What is the smallest number <span class="math-container">$s(n,\Delta)$</span> such that for any undirected simple graph <span class="math-container">$G=(V,E)$</span> with <span class="math-container">$n$</span> vertices and <span class="math-container">$\Delta$</span> triangles, there exist <span class="math-container">$n$</span> subgraphs of <span class="math-container">$G$</span> covering all triangles where each subgraph contains <span class="math-container">$s(n,\Delta)$</span> edges?</p>
<p>(Definitions) A triangle is a triple <span class="math-container">$u,v,w\in V$</span> such that <span class="math-container">$(u,v),(v,w),(w,u)\in E$</span>. A subgraph is an edge subset <span class="math-container">$E'\subseteq E$</span>. <span class="math-container">$n$</span> subgraphs cover all triangles means for any triangle <span class="math-container">$u,v,w$</span>, there exists a subgraph <span class="math-container">$E'$</span> such that <span class="math-container">$(u,v),(v,w),(w,u)\in E'$</span>.</p>
<p>(Related Works) It is known that <span class="math-container">$s(n,\Delta)=O(n^{4/3})$</span> [Dolev, Lenzen, Peled, DISC'12] in the following way. Divide the vertex set into <span class="math-container">$n^{1/3}$</span> subsets <span class="math-container">$V_1,...,V_{n^{1/3}}$</span> each with size <span class="math-container">$n^{2/3}$</span>; for each triple <span class="math-container">$(i,j,k)\in [n]\times[n]\times[n]$</span>, create a subgraph induced by the vertex set <span class="math-container">$V_i,V_j,V_k$</span>. There are <span class="math-container">$n$</span> subgraphs each with <span class="math-container">$n^{4/3}$</span> edges, and each triangle of this graph must be contained in one of them.</p>
<p>The first question to ask is whether <span class="math-container">$s(n,n^{2.9})=O(n^{4/3-\epsilon})$</span> for some small constant <span class="math-container">$\epsilon$</span>, i.e., when graph contains sub-cubic triangles, can we do better? My guess is <span class="math-container">$s(n,n^{2.9})=\Omega(n^{4/3-o(1)})$</span>, but I did not find a way to prove it.</p>

CC BY-SA 4.0
2023-05-21T02:19:48.730Z
(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?
Neal Young
CC BY-SA 4.0
2023-05-22T15:17:17.473Z
@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.
walydna
CC BY-SA 4.0
2023-05-31T00:19:18.503Z
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.
Neal Young
<graph-theory><graph-algorithms><co.combinatorics>
Cover all triangles of a graph with n subgraphs as small as possible
walydna
# Cover all triangles of a graph with n subgraphs as small as possible

(Asked by: username_0 on 2023-05-18)

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.

**Tags:** graph-theory, graph-algorithms, co.combinatorics
> **Comments:**
> **username_1**: (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?  
> **username_0**: @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.  
> **username_1**: 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.  

---

## 0 answers

