Introduction to Random Graphs

DOI10.1017/CBO9781316339831zbMath1328.05002MaRDI QIDQ2949990

Publication date: 5 October 2015

combinatorics networks random graph applied probability

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random graphs (graph-theoretic aspects) (05C80) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics (05-01)

Related Items

On connectivity and robustness of random graphs with inhomogeneity, Parameter Estimators of Sparse Random Intersection Graphs with Thinned Communities, The Early Evolution of the Random Graph Process in Planar Graphs and Related Classes, Large complete minors in random subgraphs, Short proofs for long induced paths, Random recursive hypergraphs, A note on long cycles in sparse random graphs, The Phase Transition of Discrepancy in Random Hypergraphs, Matrix-scaled resilient consensus of discrete-time and continuous-time networks, Random plane increasing trees: Asymptotic enumeration of vertices by distance from leaves, Random cliques in random graphs and sharp thresholds for F$$ F $$‐factors, Independent sets in hypergraphs omitting an intersection, Phase transition in count approximation by count-min sketch with conservative updates, Which networks permit stable allocations? A theory of network‐based comparisons, The global resilience of Hamiltonicity in $G(n, p)$, Cycle lengths in randomly perturbed graphs, Dynamic concentration of the triangle‐free process, On Bollobás‐Riordan random pairing model of preferential attachment graph, Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models, Color‐biased Hamilton cycles in random graphs, Longest and shortest cycles in random planar graphs, Limiting probabilities of first order properties of random sparse graphs and hypergraphs, Counting extensions revisited, Clustering and percolation on superpositions of Bernoulli random graphs, Site percolation on pseudo‐random graphs, Color-avoiding percolation of random graphs: between the subcritical and the intermediate regime, Rainbow connectivity and rainbow index of inhomogeneous random graphs, The planted matching problem: sharp threshold and infinite-order phase transition, $\boldsymbol{H}$-Games Played on Vertex Sets of Random Graphs, On the time to identify the nodes in a random graph, Testing correlation of unlabeled random graphs, Characterization of expansion-related properties of modular graphs, On the chromatic number in the stochastic block model, Random amenable C^*-algebras, Power of $k$ choices in the semi-random graph process, Two-Point Concentration of the Independence Number of the Random Graph, The birth of the strong components, One‐sided sharp thresholds for homology of random flag complexes, Sharp Thresholds in Random Simple Temporal Graphs, On some Multicolor Ramsey Properties of Random Graphs, Practical-time related-key attack on GOST with secret S-boxes, On the Gamma-Vector of Symmetric Edge Polytopes, Heavy and light paths and Hamilton cycles, Long paths in heterogeneous random subgraphs of graphs with large minimum degree, Edge and pair queries-random graphs and complexity, Estrada index of dynamic random graphs, Largest component of subcritical random graphs with given degree sequence, Exploring Endless Space, Unnamed Item, Turán‐type problems for long cycles in random and pseudo‐random graphs, Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics, Parking on Cayley trees and frozen Erdős-Rényi, Matching recovery threshold for correlated random graphs, Edge ideals of Erdős-Rényi random graphs: linear resolution, unmixedness and regularity, On the Concentration of the Maximum Degree in the Duplication-Divergence Models, A critical probability for biclique partition of $G_{n,p}$, Zero forcing with random sets, Trees grown under young-age preferential attachment, Continuously increasing subsequences of random multiset permutations, Random Graphs with a Fixed Maximum Degree, A counterexample to the DeMarco‐Kahn upper tail conjecture, Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs, Minimizing the number of 5-cycles in graphs with given edge-density, On the dense preferential attachment graph models and their graphon induced counterpart, Rank of the Vertex-Edge Incidence Matrix of r-Out Hypergraphs, Probabilistic intuition holds for a class of small subgraph games, Local boxicity, Insertion depth in power-weight trees, Optimal approximations made easy, Networks beyond pairwise interactions: structure and dynamics, On Stable Systems with Random Structure, Assortativity and Bidegree Distributions on Bernoulli Random Graph Superpositions, A Note on the Conductance of the Binomial Random Intersection Graph, A note on the vertex degree distribution of random intersection graphs, Assortativity and bidegree distributions on Bernoulli random graph superpositions, Harary polynomials, Packing Hamilton Cycles Online, Characteristic Dependence of Syzygies of Random Monomial Ideals, The containment profile of hyper-recursive trees, Complete Minors in Graphs Without Sparse Cuts, Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity, The (minimum) rank of typical fooling-set matrices, Planarity and Genus of Sparse Random Bipartite Graphs, Note on the multicolour size-Ramsey number for paths, Giant descendant trees, matchings, and independent sets in age-biased attachment graphs, Triangle resilience of the square of a Hamilton cycle in random graphs, 2-universality in randomly perturbed graphs, Discrepancies of spanning trees and Hamilton cycles, The giant component of the directed configuration model revisited, Spanning Trees at the Connectivity Threshold, Profile of random exponential recursive trees, Connectivity of the k-Out Hypercube, On Two Limit Values of the Chromatic Number of a Random Hypergraph, A gentle introduction to the differential equation method and dynamic concentration, Spanning structures and universality in sparse hypergraphs, Two lower bounds for $p$-centered colorings, Constraints for generating graphs with imposed and forbidden patterns: an application to molecular graphs, Compression of dynamic graphs generated by a duplication model, Phase transition of degeneracy in minor-closed families, Concentration of rainbow $k$-connectivity of a multiplex random graph, Star saturation number of random graphs, The average distance and the diameter of dense random regular graphs, On offset Hamilton cycles in random hypergraphs, Longest distance of a non-uniform dispersion process on the infinite line, Unnamed Item, Chip-Firing Games and Critical Groups, Barabási-Albert random graph with multiple type edges and perturbation, The concentration of the maximum degree in the duplication-divergence models, Asymptotics for Shamir's problem, Continuously increasing subsequences of random multiset permutations, Phase transitions for detecting latent geometry in random graphs, The threshold for the full perfect matching color profile in a random coloring of random graphs, Exponential-family models of random graphs: inference in finite, super and infinite population scenarios, Probabilistic zero forcing on random graphs, Blowup Ramsey numbers, Survival and extinction of epidemics on random graphs with general degree, On generalized choice and coloring numbers, Extremal Graphs with Local Covering Conditions, On the number of alternating paths in random graphs, Independent sets in graphs, Preferential attachment without vertex growth: emergence of the giant component, $q$-random walks on $\mathbb Z^d$, $d = 1, 2, 3$, Partitioning random graphs into monochromatic components, An exponential-type upper bound for Folkman numbers, Random flag complexes and asymptotic syzygies, Long cycles, heavy cycles and cycle decompositions in digraphs, Dense induced bipartite subgraphs in triangle-free graphs, Spectral gap bounds for the simplicial Laplacian and an application to random complexes, Maximum likelihood estimation for discrete exponential families and random graphs, Cutoff for random walk on dynamical Erdős-Rényi graph, Random perturbation of sparse graphs, Effectiveness analysis of a mixed rumor-quelling strategy, A note on the majority dynamics in inhomogeneous random graphs, Consistent structure estimation of exponential-family random graph models with block structure, On $K_{2, t}$-bootstrap percolation, Random-cluster dynamics on random regular graphs in tree uniqueness, Dold's theorem from viewpoint of strong compatibility graphs, Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process, The Kőnig graph process, A mathematical model of p62-ubiquitin aggregates in autophagy, Tight bounds on probabilistic zero forcing on hypercubes and grids, The set of ratios of derangements to permutations in digraphs is dense in $[0,1/2$], New lower bounds on the size-Ramsey number of a path, The Effect of Adding Randomly Weighted Edges, The threshold for the square of a Hamilton cycle, An approximate version of Jackson’s conjecture, Hamiltonian Berge cycles in random hypergraphs, Zero-one laws for random $k$-partite graphs, On testing for parameters in Ising models, Topological price of anarchy bounds for clustering games on networks, Vanishing of cohomology groups of random simplicial complexes, Limits of multiplicative inhomogeneous random graphs and Lévy trees: the continuum graphs, On the performance of the depth first search algorithm in supercritical random graphs, Geometric dominating sets -- a minimum version of the no-three-in-line problem, Pattern Colored Hamilton Cycles in Random Graphs, Isoperimetric numbers of randomly perturbed intersection graphs, Hamiltonicity of Random Graphs in the Stochastic Block Model, Large deviations for the largest eigenvalue of Gaussian networks with constant average degree, Grouped spatial autoregressive model, On the tree-depth and tree-width in heterogeneous random graphs, Expansion in supercritical random subgraphs of the hypercube and its consequences, Almost unimodal and real-rooted graph polynomials, Hitting times for Shamir’s problem, Typical values of extremal-weight combinatorial structures with independent symmetric weights, Compressive Sensing for Cut Improvement and Local Clustering, Waiter-client and client-waiter Hamiltonicity games on random graphs