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
Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт используя форму сверху.