Quasi-random graphs and graph limits
From MaRDI portal
Publication:648965
DOI10.1016/J.EJC.2011.03.011zbMATH Open1230.05262arXiv0905.3241OpenAlexW2021064202MaRDI QIDQ648965FDOQ648965
Publication date: 29 November 2011
Published in: European Journal of Combinatorics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0905.3241
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
hereditary subgraph counts[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Szemer%EF%BF%BD%EF%BF%BDdi+regularity+lemma&go=Go Szemer��di regularity lemma]
Cites Work
- Limits of dense graph sequences
- Graph limits and exchangeable random graphs
- Title not available (Why is that?)
- Moments of two-variable functions and the uniqueness of graph limits
- Generalized quasirandom graphs
- Title not available (Why is that?)
- Szemerédi's partition and quasirandomness
- Quasi-random graphs
- Title not available (Why is that?)
- A measure-theoretic approach to the theory of dense hypergraphs
- 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
- The effect of induced subgraphs on quasi-randomness
- Title not available (Why is that?)
- Title not available (Why is that?)
- Szemerédi's lemma for the analyst
- A Certain Class of Incidence Matrices
- Threshold Graph Limits and Random Threshold Graphs
- Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets
- Metrics for sparse graphs
- Hereditary Extended Properties, Quasi-Random Graphs and Induced Subgraphs
- The cut metric, random graphs, and branching processes
Cited In (15)
- Semantic limits of dense combinatorial objects
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Natural quasirandomness properties
- Quasirandomness in hypergraphs
- The poset of hypergraph quasirandomness
- Graph limits of random unlabelled k-trees
- A tail bound for read-kfamilies of functions
- σ-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
- Correcting continuous hypergraphs
- A limit law of almost \(l\)-partite graphs
- Quasi-randomness of graph balanced cut properties
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)
