Flag algebras
Top Cited Papers
- 1 December 2007
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 72 (4) , 1239-1282
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.Keywords
This publication has 11 references indexed in Scilit:
- The Maximum Size of 3-Uniform Hypergraphs Not Containing a Fano PlaneJournal of Combinatorial Theory, Series B, 2000
- CSDP, A C library for semidefinite programmingOptimization Methods and Software, 1999
- Real Algebraic Geometry1998
- Counting subgraphs a new approach to the Caccetta-Häggkvist conjectureDiscrete Mathematics, 1997
- Quasi-random graphsCombinatorica, 1989
- Lower bounds on the number of triangles in a graphJournal of Graph Theory, 1989
- Supersaturated graphs and hypergraphsCombinatorica, 1983
- On the number of complete subgraphs of a graph II1983
- On Sets of Acquaintances and Strangers at any PartyThe American Mathematical Monthly, 1959
- On Sets of Acquaintances and Strangers at any PartyThe American Mathematical Monthly, 1959