Kanat Tangwongsan
Science Division, Mahidol University International College, Thailand

A dense undirected graph with $n$ nodes (e.g., $K_n$) has up to $O(n^3)$ connected triplets of nodes, often known as triangles. An algorithm to find them all is straightforward and takes at most $O(n^3)$ steps. The story becomes more interesting when the graph is sparse:

Given an undirected graph with m edges, how many distinct triangles can there be?

The answer, which we'll discuss in the talk, is $O(m^{3/2})$—and quite surprisingly, there is a simple algorithm requiring no more than $O(m^{3/2})$ steps that finds all these triangles. In this talk, I will tell a story of some remarkable connections between graph motifs (triangles being the smallest nontrivial example) and geometric bounds recently studied by Atserias, Grohe, and Marx; and Bollobas and Thomason, with roots tracing back to the famous Loomis-Whitney inequality.

• Note

Additional reading: Probabilistic Method by Alon and Spencer, section 14.6 Entropy