More on quasi-random graphs, subgraph counts and graph limits. (May 2015)

• Record Type: Journal Article
• Authors: Janson, Svante; Sós, Vera T.
• Is Part Of: European journal of combinatorics. Volume 46(2015:May)
• Page Start: 134
• Page End: 160
• Publication Date: 2015-05
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2015.01.001
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: We study some properties of graphs (or, rather, graph sequences) defined by demanding that the number of subgraphs of a given type, with vertices in subsets of given sizes, approximatively equals the number expected in a random graph. It has been shown by several authors that several such conditions are quasi-random, but that there are exceptions. In order to understand this better, we investigate some new properties of this type. We show that these properties too are quasi-random, at least in some cases; however, there are also cases that are left as open problems, and we discuss why the proofs fail in these cases. The proofs are based on the theory of graph limits; and on the method and results developed by Janson (2011), this translates the combinatorial problem to an analytic problem, which then is translated to an algebraic problem.