I am looking for some reasoning in Chatterjee's paper here (page 3) (also picture below) of the bound on the number of triangles in the random graph $G(n,p)$ of n verticies and each edge is present with probability p. It somewhat seems like an inclusion exclusion application, but with two conditions (good/bad edges AND verticies) I'm not able to see it. I am also not understanding the significance of $\epsilon l n p$ for number of triangles in good edges, since the expectation of good edges is $(n-2)p^2$. Simply helping to understand how this inequality exists would be very helpful.

enter image description here


migrated from mathoverflow.net Feb 6 at 17:23

This question came from our site for professional mathematicians.

  • 3
    $\begingroup$ It's just a grouping, not a partition or classification, to provide an upper bound. A partition would be for example, triangles with all good edges and triangles with ( not all good edges). The important thing here is to find a triangle of G that does not fall into one of the classes. If you do, you have a basis for complaint. I am not finding a use of inclusion exclusion yet. Gerhard "Not Finding Complaint Basis Either" Paseman, 2019.01.27. $\endgroup$ – Gerhard Paseman Jan 28 at 5:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.