Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-09T07:54:39.631Z Has data issue: false hasContentIssue false
  • English
  • Français

Flag algebras

Published online by Cambridge University Press:  12 March 2014

Alexander A. Razborov
Alexander A. Razborov*
Affiliation:
School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540, USA. E-mail: [email protected] Steklov Mathematical Institute, Moscow, Russia. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Asymptotic extremal combinatorics deals with questions that in the language of model theory can be re-stated as follows. For finite models M, N of an universal theory without constants and function symbols (like graphs, digraphs or hypergraphs), let p(M, N) be the probability that a randomly chosen sub-model of N with ∣M∣ elements is isomorphic to M. Which asymptotic relations exist between the quantities p(M1,N),…, p(Mh,N), where M1,…, M1, are fixed “template” models and ∣N∣ grows to infinity?

In this paper we develop a formal calculus that captures many standard arguments in the area, both previously known and apparently new. We give the first application of this formalism by presenting a new simple proof of a result by Fisher about the minimal possible density of triangles in a graph with given edge density.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 72 , Issue 4 , December 2007 , pp. 1239 - 1282
Copyright
Copyright © Association for Symbolic Logic 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[BCR]Bochnak, J., Coste, M., and Roy, M., Real algebraic geometry, Springer-Verlag, 1998.CrossRefGoogle Scholar
[Bol]Bollobás, B., Relations between sets of complete subgraphs, Proceedings of the Fifth British Combinatorial Conference (Nash-Williams, C. St.J. A. and Sheehan, J., editors). Utilitas Mathematica Publishing, 1976, pp. 79–84.Google Scholar
[Bon]Bondy, J. A., Counting subgraphs: A new approach to the Caccetta-Häggkvist conjecture, Discrete Mathematics, vol. 165/166 (1997), pp. 71–80.CrossRefGoogle Scholar
[Bor]Borchers, B., CSDP, a C library for semidefinite programming, Optimization Methods and Software, vol. 11 (1999), no. 1, pp. 613–623.CrossRefGoogle Scholar
[BCL*]Borgs, C., Chayes, J., Lovász, L., Sós, V.T., and Veszteroombi, K., Counting graph homomorphisms, Topics in discrete mathematics (Klazar, M., Kratochvil, J., Loebl, M., Matousek, J., Thomas, R., and Valtr, P., editors), Springer, 2006, pp. 315–371.CrossRefGoogle Scholar
[CaH]Caccetta, L. and Häggkvist, R., On minimal digraphs with given girth, Congressus Numerantium, vol. 21 (1978), pp. 181–187.Google Scholar
[GGW]Chung, F. R. K., Graham, R. L., and Wilson, R. M., Quasi-random graphs, Combinatorica, vol. 9 (1989), pp. 345–362.CrossRefGoogle Scholar
[CaF]Caen, D. De and Füredi, Z., The maximum size of 3-uniform hypergraphs not containing a Fano plane, Journal of Combinatorial Theory, Series B, vol. 78 (2000), pp. 274–276.CrossRefGoogle Scholar
[ErSp]Erdös, P. and Spencer, J., Probabilistic methods in combinatorics, Academic Press, 1974.Google Scholar
[ErSi]Erdös, P. and Simonovits, M., Supersaturated graphs and hypergraphs, Combinatorica, vol. 3 (1983), no. 2, pp. 181–192.CrossRefGoogle Scholar
[Fel]Felix, D., Asymptotic relations in flag algebras, Manuscript, 2005.Google Scholar
[Fish]Fisher, D., Lower bounds on the number of triangles in a graph. Journal of Graph Theory, vol. 13 (1989), no. 4, pp. 505–512.CrossRefGoogle Scholar
[FLS]Freedman, M., Lovász, L., and Schrijver, A., Reflection positivity, rank connectivity, and homomorphism of graphs, Manuscript, 2004.Google Scholar
[Goo]Goodman, A. W., On sets of acquaintances and strangers at any party, American Mathematical Monthly, vol. 66 (1959), no. 9, pp. 778–783.CrossRefGoogle Scholar
[GHP]Grigoriev, D. Yu., Hirsch, E. A., and Pasechnik, D. V., Complexity of semi-algebraic proofs, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, 2002, pp. 419–430.Google Scholar
[LoSi]Lovász, L. and Simonovits, M., On the number of complete subgraphs of a graph, II, Studies in pure mathematics, Birkhäuser, 1983, pp. 459–495.CrossRefGoogle Scholar
[LoSz]Lovász, L. and Szegedy, B., Limits of dense graph sequences, Technical Report TR-2004-79, Microsoft Research, 08 2004.Google Scholar
[Man]Mantel, W., Problem 28, solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W.A. Wythoff, Wiskundige Opgaven, vol. 10 (1907), pp. 60–61.Google Scholar
[Pod]Podolski, V. V., Master's thesis, Moscow State University, Moscow, 2006, (in Russian).Google Scholar
[Tur]Turán, P., Egy gráfelméleti szélsöértékfeladatról, Matematicko Fizicki Lapok, vol. 48 (1941), pp. 436–453.Google Scholar