scientific article

Publication date: 5 June 2008

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

random graph probabilistic methods giant component graph property testing deviation probabilities Erdoes Renyi phase transition half liar game

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

The vertex size-Ramsey number, Bounds on the maximum number of minimum dominating sets, A-priori upper bounds for the set covering problem, A problem of Erdős and Sós on 3-graphs, An approximate version of the tree packing conjecture, Perfect packings in quasirandom hypergraphs. I., Packing minor-closed families of graphs into complete graphs, On the typical values of the cross-correlation measure, Creating cycles in walker-breaker games, Secret-sharing schemes for very dense graphs, On the minimum degree of minimal Ramsey graphs for multiple colours, $(1, j)$-set problem in graphs, Subexponential size hitting sets for bounded depth multilinear formulas, On the number of matroids, Adjacency matrices of random digraphs: singularity and anti-concentration, Asymptotic results for a class of triangular arrays of multivariate random variables with Bernoulli distributed components, Unsplittable coverings in the plane, Upper bounds for the total rainbow connection of graphs, The time of bootstrap percolation in two dimensions, Additive properties of sequences of pseudo $s$-th powers, Counting and packing Hamilton cycles in dense graphs and oriented graphs, On the Ramsey-Turán number with small $s$-independence number, Moderate deviations via cumulants, Perturbing the hexagonal circle packing: a percolation perspective, Can extra updates delay mixing?, Tightened exponential bounds for discrete-time conditionally symmetric martingales with bounded jumps, Gumbel fluctuations for cover times in the discrete torus, A probabilistic technique for finding almost-periods of convolutions, Random walks on quasirandom graphs, On the dynamic coloring of graphs, Discrepancy inequalities for directed graphs, Infeasibility of instance compression and succinct PCPs for NP, Long paths and cycles in random subgraphs of $\mathcal{H}$-free graphs, Perfect matchings in 3-partite 3-uniform hypergraphs, Energy fluctuations shape free energy of nonspecific biomolecular interactions, Approximate multipartite version of the Hajnal-Szemerédi theorem, On extremal hypergraphs for Hamiltonian cycles, Improved bounds on coloring of graphs, Colorful triangle counting and a \textsc{MapReduce} implementation, The size Ramsey number of a directed path, Spectra of uniform hypergraphs, Biased orientation games, New bounds for contagious sets, Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels, Random geometric complexes, Local correction of juntas, Scaling limits for continuous opinion dynamics systems, Small components in $k$-nearest neighbour graphs, Kakeya-type sets in finite vector spaces, The existence of $k$-radius sequences, Randomly colouring graphs (a combinatorial view), Equitable two-colorings of uniform hypergraphs, The cone percolation on $\mathbb{T}_{d}$, On generalized Ramsey numbers of Erdős and Rogers, An entropy argument for counting matroids, Book review of: D. P. Dubhashi and A. Panconesi, Concentration of measure for the analysis of randomized algorithms., The cook-book approach to the differential equation method, Noise sensitivity in continuum percolation, A $q$-analogue of the FKG inequality and some applications, Phase transition for finite-speed detection among moving particles, On the computation of edit distance functions, On the KŁR conjecture in random graphs, Bounds for generalized Sidon sets, Extremal results for odd cycles in sparse pseudorandom graphs, A non-linear lower bound for planar epsilon-nets, Random Latin squares and 2-dimensional expanders, The game chromatic number of dense random graphs, Comparable pairs in families of sets, Spectral clustering in the dynamic stochastic block model, Approximating sparse binary matrices in the cut-norm, On sets of integers with restrictions on their products, Independent sets in graphs, Notes on use of generalized entropies in counting, Hölder-type inequalities and their applications to concentration and correlation bounds, A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming, Enumerating matroids of fixed rank, Partitioning random graphs into monochromatic components, Chromatic roots and limits of dense graphs, The typical structure of graphs with no large cliques, A Lyapunov function for Glauber dynamics on lattice triangulations, On pseudorandomness of families of binary sequences, Set families with a forbidden pattern, The critical window for the classical Ramsey-Turán problem, A polynomial Turing-kernel for weighted independent set in bull-free graphs, Sequences of radius $k$ for complete bipartite graphs, Words in linear groups, random walks, automata and P-recursiveness, New results on $k$-independence of graphs, Phase transitions for modified Erdős--Rényi processes, Spectra of lifted Ramanujan graphs, Dynamic chromatic number of regular graphs, Block sensitivity of minterm-transitive functions, Partial covering arrays: algorithms and asymptotics, Two proofs for shallow packings, Distinct distances on regular varieties over finite fields, Onk-tuple domination of random graphs, Sets of integers with no large sum-free subset, Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas, A problem of Erdős on the minimum number of $k$-cliques, Bandwidth theorem for random graphs, Algorithms and almost tight results for 3-colorability of small diameter graphs, A Short Note on the Average Maximal Number of Balls in a Bin, On tripartite common graphs, A Stability Result on Matchings in 3-Uniform Hypergraphs, Super Solutions of Random Instances of Satisfiability, Large Rainbow Cliques in Randomly Perturbed Dense Graphs, Random Subgraphs in Sparse Graphs, Spanning Structures in Walker–Breaker Games, ADDITIVE ENERGY AND THE METRIC POISSONIAN PROPERTY, Small violations of Bell inequalities for multipartite pure random states, Small subgraphs and their extensions in a random distance graph, The Range of a Rotor Walk, Around the log-rank conjecture, Co-degree threshold for rainbow perfect matchings in uniform hypergraphs, Rainbow spanning structures in graph and hypergraph systems, A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees, Induced Subgraphs With Many Distinct Degrees, Randomized Rumour Spreading: The Effect of the Network Topology, The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups, Easily Testable Graph Properties, Orientability Thresholds for Random Hypergraphs, Decomposing Random Graphs into Few Cycles and Edges, On the Length of a Random Minimum Spanning Tree, On Active and Passive Testing, First Order Probabilities for Galton–Watson Trees, Universality of Graphs with Few Triangles and Anti-Triangles, Tuza's Conjecture is Asymptotically Tight for Dense Graphs, Large Unavoidable Subtournaments, The Threshold Probability for Long Cycles, On Regularity Lemmas and their Algorithmic Applications, Bridge-Addability, Edge-Expansion and Connectivity, On Hamilton cycles in Erdős‐Rényi subgraphs of large graphs, Optimal induced universal graphs for bounded-degree graphs, Mod-ϕ Convergence, II: Estimates on the Speed of Convergence, On the size of the set AA+A, LONELY RUNNERS IN FUNCTION FIELDS, Rainbow structures in locally bounded colorings of graphs, Spectral expansion of random sum complexes, Ordered Ramsey numbers, Packing and counting arbitrary Hamilton cycles in random digraphs, Most edge‐orderings of K_n have maximal altitude, Colorings of hypergraphs with large number of colors, On the cycle space of a random graph, A Note on Large H-Intersecting Families, Semantic limits of dense combinatorial objects, Foster, Turán, and Neighbors, Robust Tverberg and Colourful Carathéodory Results via Random Choice, Compressing Interactive Communication Under Product Distributions, Error estimates and convergence rates for the stochastic homogenization of Hamilton-Jacobi equations, Colourings of Uniform Hypergraphs with Large Girth and Applications, Coalescence on the real line, Balancing sums of random vectors, Spatially independent martingales, intersections, and applications, Packing, counting and covering Hamilton cycles in random directed graphs, Harmonious and achromatic colorings of fragmentable hypergraphs, Counting configuration-free sets in groups, Partial domination - the isolation number of a graph, Statistical inference on random dot product graphs: a survey, Robust Hamiltonicity of Dirac graphs, Lipschitz functions on the infinite-dimensional torus, Topics of Stochastic Algebraic Topology, Unnamed Item, Unnamed Item, Minimum rainbow $H$-decompositions of graphs, A new kind of selectors and their applications to conflict resolution in wireless multichannels networks, Strong noise sensitivity and random graphs, Tight bounds for sliding Bloom filters, Extractors in Paley graphs: a random model, Disjoint edges in complete topological graphs, A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem], Robust Auctions for Revenue via Enhanced Competition, Separation Choosability and Dense Bipartite Induced Subgraphs, On Erdős–Ko–Rado for random hypergraphs I, Approximation in (Poly-) Logarithmic Space, A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols, An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions, The Lovász Local Lemma and Satisfiability, Some Properties of Random Apollonian Networks, Shearer's point process, the hard-sphere model, and a continuum Lovász local lemma, Weak limits for the largest subpopulations in Yule processes with high mutation probabilities, Finding independent transversals efficiently, Superlogarithmic Cliques in Dense Inhomogeneous Random Graphs, Concentration and Moment Inequalities for Polynomials of Independent Random Variables, Nearly Perfect Matchings in Uniform Hypergraphs, Random Popular Matchings with Incomplete Preference Lists, On the subgraph query problem, Balanced Hashing, Color Coding and Approximate Counting, On the Concentration of the Domination Number of the Random Graph, Further results on generalized conditional entropies, Independent sets in hypergraphs, The Phase Transition in Multitype Binomial Random Graphs, Unnamed Item, Unnamed Item, Minimum Congestion Mapping in a Cloud, Unnamed Item, Faster 3-Coloring of Small-Diameter Graphs, Pseudorandom Functions: Three Decades Later, The number of partial Steiner systems and d-partitions, Upper Bounds on the Size of Covering Arrays, On Treewidth and Related Parameters of Random Geometric Graphs, Randomly coloring simple hypergraphs with fewer colors, Waiter-client and client-waiter colourability and $k$-SAT games, Partition expanders, Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs, Elegantly Colored Paths and Cycles in Edge Colored Random Graphs, On reverse hypercontractivity, Uniformly Discrete Forests with Poor Visibility, Connections in Randomly Oriented Graphs, An Upper Bound for the Hales--Jewett Number $\mathrm{HJ}(4,2)$, Exact learning from an honest teacher that answers membership queries, Contraction of areas vs. topology of mappings, Ramsey-type results for semi-algebraic relations, Remarks on a Ramsey theory for trees, Secret-sharing for NP, Expanders with superquadratic growth, The total acquisition number of random geometric graphs, Deviation estimates for Eulerian edit numbers of random graphs, Strongly separable matrices for nonadaptive combinatorial group testing, Constrained minimum passage time in random geometric graphs, Efficient random graph matching via degree profiles, Probabilistic constructions in generalized quadrangles, Kantorovich duality for general transport costs and applications, An average degree condition for independent transversals, Spectra of first-order formulas with a low quantifier depth and a small number of quantifier alternations, On Failure of 0-1 Laws, Erdős-Hajnal conjecture for graphs with bounded VC-dimension, Block avoiding point sequencings of partial Steiner systems, Local bounds for the optimal information ratio of secret sharing schemes, A new coding-based algorithm for finding closest pair of vectors, The removal lemma for tournaments, Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives, On the distribution of the sum of digits of sums $a+b$, A better bound on the size of rainbow matchings, Small Dense Subgraphs of a Graph, On nowhere dense graphs, A Power-of-Two-Choices Unbalanced Allocation Process, Tilted Sperner families, FINITELY DEPENDENT COLORING, On balanced colorings of sparse hypergraphs, On a conjecture of Erdős and Simonovits: even cycles, Competitive router scheduling with structured data, More fires and more fighters, Irreversible conversion processes with deadlines, On the power of conditional samples in distribution testing, Forbidding a set difference of size 1, Extremal statistics on non-crossing configurations, Sharp vanishing thresholds for cohomology of random flag complexes, Online Ramsey Numbers and the Subgraph Query Problem, Rainbow Matchings: existence and counting, The limiting shape for drifted internal diffusion limited aggregation is a true heat ball, The frequent paucity of trivial strings, Pseudorandom generators hard for $k$-DNF resolution and polynomial calculus resolution, Counting matroids in minor-closed classes, The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled Chi-square, Traveling salesman problem across well-connected cities and with location-dependent edge lengths, The typical structure of sparse $K_{r+1}$-free graphs, Optimal packings of bounded degree trees, Conditional expanding bounds for two-variable functions over prime fields, The range of thresholds for diameter 2 in random Cayley graphs, A Danzer set for axis parallel boxes, On the existence of accessible paths in various models of fitness landscapes, On the relation of separability, bandwidth and embedding, Extremal paths in inhomogenous random graphs, Colorings of partial Steiner systems and their applications, On obstacle numbers, Clustering coefficients of large networks, Multicolor Ramsey numbers via pseudorandom graphs, Consistent structure estimation of exponential-family random graph models with block structure, A power law of order 1/4 for critical mean-field Swendsen-Wang dynamics, Graphs with Many Strong Orientations, On “stability” in the Erdös--Ko--Rado Theorem, Improved Bounds on Induced Acyclic Subgraphs in Random Digraphs, Small Subgraphs in Random Distance Graphs, A constructive proof of a concentration bound for real-valued random variables, Zero-one laws for $k$-variable first-order logic of sparse random graphs, The correlation measures of finite sequences: limiting distributions and minimum values, Applying a generalized allocation scheme to analyzing a class of sequences generated by a shift register, Expanding phenomena over matrix rings, Computing a small agreeable set of indivisible items, A note on the warmth of random graphs with given expected degrees, Embedding Graphs Having Ore-Degree at Most Five, New selectors and locally thin families with applications to multi-access channels supporting simultaneous transmissions, Average stretch factor: how low does it go?, How to play Thue games, Multiscale analysis for ergodic Schrödinger operators and positivity of Lyapunov exponents, Lengths of monotone subsequences in a Mallows permutation, Locating-dominating sets and identifying codes in graphs of girth at least 5, Extensions of results on rainbow Hamilton cycles in uniform hypergraphs, The 2-tuple dominating independent number of a random graph, Local correction with constant error rate, An asymptotic existence result on compressed sensing matrices, Bipartite decomposition of random graphs, Forbidding intersection patterns between layers of the cube, Poset-free families and Lubell-boundedness, Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry, Disjoint induced subgraphs of the same order and size, A generalization of the Hajnal-Szemerédi theorem for uniform hypergraphs, Synchronization of coupled chaotic maps, On the bipartite graph packing problem, Waiter-client and client-waiter Hamiltonicity games on random graphs, Multicolor list Ramsey numbers grow exponentially, Value‐based distance between information structures, On some graph densities in locally dense graphs, Independence number of hypergraphs under degree conditions, Improved bound on vertex degree version of Erdős matching conjecture, ℓ $\ell $‐Connectivity and ℓ $\ell $‐edge‐connectivity of random graphs, Detecting arrays for effects of single factors, Linear arboricity of degenerate graphs, Spanning trees in graphs of high minimum degree with a universal vertex II: A tight result, The planted matching problem: sharp threshold and infinite-order phase transition, A decomposition method on solving the linear arboricity conjecture, Low communication complexity protocols, collision resistant hash functions and secret key-agreement protocols, The largest crossing number of tanglegrams, Cut distance identifying graphon parameters over weak* limits, On a combinatorial framework for fault characterization, Topology of random geometric complexes: a survey, Nominal correlation of inhomogeneous random sequences, Phase transitions in discrete structures, Phylogenetic information complexity: is testing a tree easier than finding it?, Achieving positive rates with predetermined dictionaries, On the feedback number of 3-uniform linear extremal hypergraphs, Book review of: L. Guth, Polynomial methods in combinatorics, Spectral gap of random hyperbolic graphs and related parameters, Around the Danzer problem and the construction of dense forests, On $n$-saturated closed graphs, Chromatic index of dense quasirandom graphs, $k$-planar crossing number of random graphs and random regular graphs, Localization in random geometric graphs with too many edges, Upper tails for arithmetic progressions in random subsets, Revolutionaries and spies: spy-good and spy-bad graphs, Cops and Robber game with a fast robber on expander graphs and random graphs, On the game domination number of graphs with given minimum degree, A remark on the tournament game, Random-player maker-breaker games, The maximal length of a gap between $r$-graph Turán densities, More on the colorful monochromatic connectivity, Information gathering in ad-hoc radio networks with tree topology, Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution, Long directed rainbow cycles and rainbow spanning trees, Extremal problems in uniformly dense hypergraphs, A stability result for the cube edge isoperimetric inequality, A transition of limiting distributions of large matchings in random graphs, Stability of twisted states in the Kuramoto model on Cayley and random graphs, Size and degree anti-Ramsey numbers, A note on interference in random networks, Hoeffding's inequality for sums of dependent random variables, Local and global colorability of graphs, Three ways to cover a graph, Every countable infinite group admits a long range percolation with a phase transition, Smooth movement and Manhattan path based random waypoint mobility, New bounds on the maximum number of edges in $k$-quasi-planar graphs, The phase transition in site percolation on pseudo-random graphs, Large convex holes in random point sets, Stochastic coalescence in logarithmic time, Threshold functions and Poisson convergence for systems of equations in random sets, Adaptive estimation of convex polytopes and convex sets from noisy data, On the stretch factor of randomly embedded random graphs, Mobile geometric graphs: detection, coverage and percolation, On a conjecture of Erdős on locally sparse Steiner triple systems, Number of 1-factorizations of regular high-degree graphs, Discrepancy and numerical integration on metric measure spaces, Upper bounds on positional Paris-Harrington games, On the distribution of the maximum $k$-degrees of the binomial random graph, Realization of aperiodic subshifts and uniform densities in groups, Egalitarian Steiner triple systems for data popularity, Asymptotic and constructive methods for covering perfect hash families and covering arrays, The hardest halfspace, Minimum spanning trees of random geometric graphs with location dependent weights, Phase transition in inhomogenous Erdős-Rényi random graphs via tree counting, On the metric dimension of incidence graphs, Abstract polymer gas: a simple inductive proof of the Fernández-Procacci criterion, First-passage percolation on Cartesian power graphs, On $k$-uniform random hypergraphs without generalized fans, Random walks on the random graph, Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count, Weighted dependency graphs, Bounded size biased couplings, log concave distributions and concentration of measure for occupancy models, On vertex-disjoint paths in regular graphs, Subgraphs with large minimum $\ell$-degree in hypergraphs where almost all $\ell$-degrees are large, Improved bounds in stochastic matching and optimization, De-anonymization of heterogeneous random graphs in quasilinear time, Sidon set systems, Using TPA to count linear extensions, Geometric properties of infinite graphs and the Hardy-Littlewood maximal operator, Some remarks on the geodetic number of a graph, The discrepancy of the lex-least de Bruijn sequence, On $k$-partite hypergraphs with the induced $\epsilon $-density property, An algebraic perspective on integer sparse recovery, On loops intersecting at most once, Parametric monotone function maximization with matroid constraints, Reliable communication over highly connected noisy networks, Burning graphs: a probabilistic perspective, Cutoff phenomena for random walks on random regular graphs, Choice-memory tradeoff in allocations, Set systems with distinct sumsets, Approximation in (Poly-) logarithmic space, Strong identification codes for graphs, Recent progress in combinatorial random matrix theory, Connector-breaker games on random boards, Roots of random polynomials with coefficients of polynomial growth, Rainbow monochromatic $k$-edge-connection colorings of graphs, The unit acquisition number of binomial random graphs, Further results on the rainbow vertex-disconnection of graphs, Strong and weighted matchings in inhomogenous random graphs, On probabilistic generalizations of the Nyman-Beurling criterion for the zeta Function, Best response dynamics on random graphs, The distribution of the maximum number of common neighbors in the random graph, The cone percolation model on Galton-Watson and on spherically symmetric trees, Triangle packing and covering in dense random graphs, Rainbow and monochromatic vertex-connection of random graphs, Counting embeddings of rooted trees into families of rooted trees, Approximate counting of standard set-valued tableaux, No-dimensional Tverberg theorems and algorithms