### Decomposition of Triangle-dense Graphs

- Series
- Graph Theory Seminar
- Time
- Wednesday, April 20, 2016 - 15:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- He Guo – Math, GT

A special feature possessed by the graphs of social networks
is triangle-dense. R. Gupta, T. Roughgarden and C. Seshadhri give a
polynomial time graph algorithm to decompose a triangle-dense graph into
some clusters preserving high edge density and high triangle density in
each cluster with respect to the original graph and each cluster has
radius 2. And high proportion of triangles of the original graph are
preserved in these clusters. Furthermore, if high proportion of edges in
the original graph is "locally triangle-dense", then additionally, high proportion of
edges of the original graph are preserved in these clusters.
In this talk, I will present most part of the paper "Decomposition of Triangle-dense Graphs"
in SIAM J. COMPUT. Vol. 45, No. 2, pp. 197–215, 2016, by R. Gupta, T. Roughgarden and C. Seshadhri.