Asymptotic Structure of Graphs with the Minimum Number of Triangles

作者:Pikhurko Oleg*; Razborov Alexander
来源:Combinatorics Probability & Computing, 2017, 26(1): 138-160.
DOI:10.1017/S0963548316000110

摘要

We consider the problem of minimizing the number of triangles in a graph of given order and size, and describe the asymptotic structure of extremal graphs. This is achieved by characterizing the set of flag algebra homomorphisms that minimize the triangle density.

  • 出版日期2017-1