Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

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.

share|improve this answer
    
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) –  Shir Dec 20 '11 at 14:32
    
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. –  Shir May 26 '13 at 7:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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