Asymptotic structure of graphs with the minimum number of triangles\ud

Article English OPEN
Pikhurko, Oleg ; Razborov, Alexander (2016)
  • Publisher: Cambridge University Press
  • Related identifiers: doi: 10.1017/S0963548316000110
  • Subject: QA
    acm: MathematicsofComputing_DISCRETEMATHEMATICS

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.
  • References (39)
    39 references, page 1 of 4

    [1] Aristoff, D. and Radin, C. (2013) Emergent structures in large networks. J. Appl. Probab. 50 883-888.

    [2] Bollob a´s, B. (1976) On complete subgraphs of different orders. Math. Proc. Camb. Phil. Soc. 79 19-24.

    [3] Borgs, C., Chayes, J., Lov a´sz, L., So´ s, V. T. and Vesztergombi, K. (2008) Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Adv. Math. 219 1801-1851.

    [4] Chatterjee, S. and Dembo, A. (2014) Nonlinear large deviations. arXiv:1401.3495

    [5] Chatterjee, S. and Dey, P. S. (2010) Applications of Stein's method for concentration inequalities. Ann. Probab. 38 2443-2485.

    [6] Chatterjee, S. and Diaconis, P. (2013) Estimating and understanding exponential random graph models. Ann. Statist. 41 2428-2461.

    [7] Chatterjee, S. and Varadhan, S. R. S. (2011) The large deviation principle for the Erdo˝s-Re´nyi random graph. Europ. J. Combin. 32 1000-1017.

    [8] Cummings, J., Kr a´l', D., Pfender, F., Sperfeld, K., Treglown, A. and Young, M. (2013) Monochromatic triangles in three-coloured graphs. J. Combin. Theory Ser. B 103 489-503.

    [9] Das, S., Huang, H., Ma, J., Naves, H. and Sudakov, B. (2013) A problem of Erdo˝s on the minimum number of k-cliques. J. Combin. Theory Ser. B 103 344-373.

    [10] Erdo˝s, P. (1955) Some theorems on graphs. Riveon Lematematika 9 13-17.

  • Metrics
    views in OpenAIRE
    views in local repository
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    Warwick Research Archives Portal Repository - IRUS-UK 0 18
Share - Bookmark