Зарегистрироваться
Восстановить пароль
FAQ по входу

Lovász L. Large networks and graph limits

  • Файл формата pdf
  • размером 3,37 МБ
Lovász L. Large networks and graph limits
Budapest: Eotvos Lorand University, 2012. — 487 p.
Contents:
Preface
Large graphs: an informal introduction
Very large networks
Huge networks everywhere
What to ask about them?
How to obtain information about them?
How to model them?
How to approximate them?
How to run algorithms on them?
Bounded degree graphs
Large graphs in mathematics and physics
Extremal graph theory
Statistical physics
The algebra of graph homomorphisms
Notation and terminology
Basic notation
Graph theory
Operations on graphs
Graph parameters and connection matrices
Graph parameters and graph properties
Connection matrices
Finite connection rank
Graph homomorphisms
Existence of homomorphisms
Homomorphism numbers
What hom functions can express
Homomorphism and isomorphism
Independence of homomorphism functions
Characterizing homomorphism numbers
The structure of the homomorphism set
Graph algebras and homomorphism functions
Algebras of quantum graphs
Reflection positivity
Contractors and connectors
Algebras for homomorphism functions
Computing parameters with finite connection rank
The polynomial method
Limits of dense graph sequences
Kernels and graphons
Kernels, graphons and stepfunctions
Generalizing homomorphisms
Weak isomorphism I
Sums and products
Kernel operators
The cut distance
The cut distance of graphs
Cut norm and cut distance of kernels
Weak and L-topologies
Szemer´edi itions
Regularity Lemma for graphs
Regularity Lemma for kernels
Compactness of the graphon space
Fractional and integral overlays
Uniqueness of regularity itions
Sampling
W-random graphs
Sample concentration
Estimating the distance by sampling
The distance of a sample from the original
Counting Lemma
Inverse Counting Lemma
Weak isomorphism II
Convergence of dense graph sequences
Sampling, homomorphism densities and cut distance
Random graphs as limit objects
The limit graphon
Proving convergence
Many disguises of graph limits
Convergence of spectra
Convergence in norm
First applications
Convergence from the right
Homomorphisms to the right and multicuts
The overlay functional
Right-convergent graphon sequences
Right-convergent graph sequences
On the structure of graphons
The general form of a graphon
Weak isomorphism III
Pure kernels
The topology of a graphon
Symmetries of graphons
The space of graphons
Norms defined by graphs
Other norms on the kernel space
Closures of graph properties
Graphon varieties
Random graphons
Exponential random graph models
Algorithms for large graphs and graphons
Parameter estimation
Distinguishing graph properties
Property testing
Computable structures
Extremal theory of dense graphs
Nonnegativity of quantum graphs and reflection positivity
Variational calculus of graphons
Densities of complete graphs
The classical theory of extremal graphs
Local vs global optima
Deciding inequalities between subgraph densities
Which graphs are extremal?
Multigraphs and decorated graphs
Compact decorated graphs
Multigraphs with unbounded edge multiplicities
Limits of bounded degree graphs
Graphings
Borel graphs
Measure preserving graphs
Random rooted graphs
Subgraph densities in graphings
Local equivalence
Graphings and groups
Convergence of bounded degree graphs
Local convergence and limit
Local-global convergence
Right convergence of bounded degree graphs
Random homomorphisms to the right
Convergence from the right
On the structure of graphings
Hyperfiniteness
Homogeneous decomposition
Algorithms for bounded degree graphs
Estimable parameters
Testable properties
Computable structures
Extensions: a brief survey
Other combinatorial structures
Sparse (but not very sparse) graphs
Edge-coloring models
Hypergraphs
Categories
And more
Mobius functions
The Tutte polynomial
Some background in probability and measure theory
Moments and the moment problem
Ultraproduct and ultralimit
Vapnik–Chervonenkis dimension
Nonnegative polynomials
Categories
Bibliography
Author Index
Subject Index
Notation Index
  • Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт используя форму сверху.
  • Регистрация