More on quasi-random graphs, subgraph counts and graph limits

DOI10.1016/J.EJC.2015.01.001zbMATH Open1307.05204arXiv1405.6808OpenAlexW2963444279MaRDI QIDQ2255808FDOQ2255808

Authors: Svante Janson, Vera T. Sós 

Publication date: 18 February 2015

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1405.6808

Recommendations

• Quasi-random graphs and graph limits
• Quasi-randomness and the distribution of copies of a fixed graph
• Hereditary Extended Properties, Quasi-Random Graphs and Induced Subgraphs
• Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs
• On the graph limit question of Vera T. Sós

zbMATH Keywords

graph sequencesnumber of subgraphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Cites Work

• Limits of dense graph sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Szemerédi's partition and quasirandomness
• Quasi-random graphs
• Title not available (Why is that?)
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Quasi-randomness and the distribution of copies of a fixed graph
• Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs
• A characterization of functions with vanishing averages over products of disjoint sets
• The effect of induced subgraphs on quasi-randomness
• Title not available (Why is that?)
• Szemerédi's lemma for the analyst
• The quasi-randomness of hypergraph cut properties
• Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets
• Hereditary Extended Properties, Quasi-Random Graphs and Induced Subgraphs
• Quasi-random graphs and graph limits
• Quasi-randomness of graph balanced cut properties

Cited In (5)

• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• A characterization of functions with vanishing averages over products of disjoint sets
• FORCING QUASIRANDOMNESS WITH TRIANGLES
• Limits of random trees. II
• Quasirandom multitype graphs

This page was built for publication: More on quasi-random graphs, subgraph counts and graph limits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2255808)