Quasi-random graphs and graph limits
From MaRDI portal
Abstract: We use the theory of graph limits to study several quasi-random properties, mainly dealing with various versions of hereditary subgraph counts. The main idea is to transfer the properties of (sequences of) graphs to properties of graphons, and to show that the resulting graphon properties only can be satisfied by constant graphons. These quasi-random properties have been studied before by other authors, but our approach gives proofs that we find cleaner, and which avoid the error terms and epsilons in the traditional arguments using the Szemeredi regularity lemma. On the other hand, other technical problems sometimes arise in analysing the graphon properties; in particular, a measure-theoretic problem on elimination of null sets that arises in this way is treated in an appendix.
Recommendations
- More on quasi-random graphs, subgraph counts and graph limits
- Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs
- Quasi-random graphs
- Quasi-randomness and the distribution of copies of a fixed graph
- Hereditary Extended Properties, Quasi-Random Graphs and Induced Subgraphs
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 3711961 (Why is no real title available?)
- scientific article; zbMATH DE number 747030 (Why is no real title available?)
- scientific article; zbMATH DE number 3329342 (Why is no real title available?)
- A Certain Class of Incidence Matrices
- A measure-theoretic approach to the theory of dense hypergraphs
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Generalized quasirandom graphs
- Graph limits and exchangeable random graphs
- Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs
- Hereditary Extended Properties, Quasi-Random Graphs and Induced Subgraphs
- Limits of dense graph sequences
- Metrics for sparse graphs
- Moments of two-variable functions and the uniqueness of graph limits
- Quasi-random graphs
- 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
- Szemerédi's lemma for the analyst
- Szemerédi's partition and quasirandomness
- The cut metric, random graphs, and branching processes
- Threshold graph limits and random threshold graphs
Cited in
(22)- Quasi-randomness of graph balanced cut properties
- The entropy of random-free graphons and properties
- Characteristic power series of graph limits
- Semantic limits of dense combinatorial objects
- A tail bound for read-k families of functions
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Natural quasirandomness properties
- Quasirandomness in hypergraphs
- Quasi-random words and limits of word sequences
- The poset of hypergraph quasirandomness
- From quasirandom graphs to graph limits and graphlets
- Graph limits of random unlabelled k-trees
- Monotone graph limits and quasimonotone graphs
- Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs
- σ-algebras for quasirandom hypergraphs
- Graph limits and hereditary properties
- Graph limits and exchangeable random graphs
- More on quasi-random graphs, subgraph counts and graph limits
- Concentration estimates for functions of finite high‐dimensional random arrays
- A limit law of almost l-partite graphs
- Correcting continuous hypergraphs
- Random graphons and a weak positivstellensatz for graphs
This page was built for publication: Quasi-random graphs and graph limits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q648965)
