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

DOI10.1016/J.EJC.2015.01.001MaRDI QIDQ2255808zbMATH OpenOpenAlexFDO

Authors Svante Janson, Vera T. Sós

Publication date 18 February 2015

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

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

zbMATH Keywords

graph sequencesnumber of subgraphs

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(9)

• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Quasi-random words and limits of word sequences
• A characterization of functions with vanishing averages over products of disjoint sets
• From quasirandom graphs to graph limits and graphlets
• Limits of random trees. II
• Random homomorphisms into the orthogonality graph
• Quasi-random graphs and graph limits
• Forcing quasirandomness with triangles
• 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)