3
$\begingroup$

Let $G=(V,E)$ be a graph. Let $t$ denote the number of triangles in the graph, and $x$ denote the number of pairs of distinct triangles that share an edge.
(For example in $K_4$ we have $t=4$ and $x=6$)
Define $\Delta_{e}= {\text {no. of triangles that use e}}$
Define $\Delta_{max}=\max_{e\in E} \Delta_{e}$

We have been able to show that $\frac {2x} {3t} \leq \Delta_{max}$ and one can see that this is tight ($\pm 1$) when $G$ is a complete graph.

The proof we have is fairly simple: view this as an optimization problem. We aim to maximize the $L_2$ norm of the vector $(\Delta_{e_1},\Delta_{e_2}, ... , \Delta_{|E|})$ subject to the constraints that the overall number of triangles is still $t$ and that for all $e\in E$ we have $0\leq \Delta_e \leq \Delta_{max}$.

My problem is that I'm convinced that there's a simpler straightforward proof. I feel in my bones that there's some simple counting argument hiding here, as the 2 in the numerator and 3 in the denominator of the bound must stem from the fact that we are discussing edges and triangles. They do so in our proof, but in a sort of roundabout way. Can anyone come up with a two-sentence proof for this bound?

Thanks

$\endgroup$

1 Answer 1

9
$\begingroup$

Let $N~$ be the number of figures consisting of two triangles sharing an edge, with one of the vertices not on the common edge marked.

Clearly $N=2x$. Alternatively, start with one triangle, mark a vertex, add a second triangle to the opposite side. So $N\le 3t(\Delta_e-1)$. Which is now exact for complete graphs and sharpens your inequality.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks, nice observation. (Our original proof did give a sharp bound, but we neglect the -1 during the calculation since we are interested in asymptotics anyway) $\endgroup$
    – Shir
    Dec 20, 2011 at 14:32
  • 1
    $\begingroup$ Here's a published paper (DISC 2012) where we used this proof (Lemma 5.9). link.springer.com/chapter/10.1007%2F978-3-642-33651-5_14 Thanks again, Prof. McKay. $\endgroup$
    – Shir
    May 26, 2013 at 7:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.