Notation for: the number of triangles $t$ in graph $G = (V,E)$ dominates its number of edges and vertices

Question

Good day to everybody,

I would like to use a nice mathematical notation to represent the following statement:

The number of triangles $t$ in graph $G = (V,E)$ dominates its number of edges and vertices.

I have thought of the following notations:

1. |V| + |E| $\leq$ t
2. $max\{|V|,|E|\}$ $\leq$ t
3. t = $\Omega(|V|+|E|)$
4. t = $\Omega(max\{|V|,|E|\})$
5. $|V|+|E|$ = $O(t)$
6. $max\{|V|,|E|\}$ = $O(t)$

I like options 1 and 4 best, but I am puzzled among all of the options.

To give you a small context, we have an algorithm that accepts a graph along with its triangles, and just goes through all the vertices, all the edges, and all the triangles. As we are interested in triangles, we want to have the assumption that "it is the triangles that matter to us most here and hence we assume that their number dominates everything else, other cases are not important to us".

Which notation do you think (or, even better, know for sure) fits the statement better?

Thank you.

Answer 1

It depends on how do you analyze the algorithm - do you want to express your bounds in terms of $t$ or perhaps $|V|$ and $|E|$? Thus, if you care only about the triangles, then to me it seems that 5 is the best option: when you later analyze your algorithm you can immediately conclude things like $|V| + |E| + t = O(t)$.

Some additional comments:

• 1, 2 are probably too restrictive - if there are more edges than triangles then perhaps that's still fine as long as it's within some constant.
• 2, 4 and 6 have lots of parentheses and braces and look too much complicated for what they express.
• 3, 4 invert the relationship, if you want to express some bounds in terms of $t$, then these will look a bit less natural.

I hope this helps $\ddot\smile$