uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
More on quasi-random graphs, subgraph counts and graph limits
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
2015 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 46, 134-160 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2015. Vol. 46, 134-160 p.
National Category
URN: urn:nbn:se:uu:diva-248797DOI: 10.1016/j.ejc.2015.01.001ISI: 000350186900012OAI: oai:DiVA.org:uu-248797DiVA: diva2:801876
Available from: 2015-04-10 Created: 2015-04-08 Last updated: 2016-02-17Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Janson, Svante
By organisation
Analysis and Probability Theory
In the same journal
European journal of combinatorics (Print)

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 209 hits
ReferencesLink to record
Permanent link

Direct link