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 (only showing first 100 items - show all)

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

This page was built for publication: