Largest random component of a k-cube

DOI10.1007/BF02579276MaRDI QIDQ1166544zbMATH OpenOpenAlexWikidataFDO

Authors Miklós Ajtai, János Komlós, Endre Szemerédi

Publication date 1982

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02579276

zbMATH Keywords

random cube

Mathematics Subject Classification ID

Combinatorial probability (60C05) Connectivity (05C40) Graph theory (05C99)

Cites work

• scientific article; zbMATH DE number 3190745 (Why is no real title available?)
• Evolution of the n-cube
• Optimal numberings and isoperimetric problems on graphs
• The longest path in a random graph

Cited in

(47)

• Speeding up random walk mixing by starting from a uniform vertex
• Large components in random induced subgraphs of \(n\)-cubes
• Expansion in supercritical random subgraphs of the hypercube and its consequences
• The \(Q_2\)-free process in the hypercube
• Generic properties of combinatory maps: Neutral networks of RNA secondary structures
• Hypercube percolation
• Supercritical site percolation on the hypercube: small components are small
• Acyclic orientations of random graphs
• The Evolution of Random Subgraphs of the Cube
• Clique percolation
• Random induced subgraphs of generalized \(n\)-cubes
• The component structure of dense random subgraphs of the hypercube
• A branching process with deletions and mergers that matches the threshold for hypercube percolation
• Percolation on finite graphs and isoperimetric inequalities.
• Unlacing hypercube percolation: a survey
• On the critical probability in percolation
• The giant component threshold for random regular graphs with edge faults H. Prodinger
• Extreme values for two-dimensional discrete Gaussian free field
• Existence of a phase transition of the interchange process on the Hamming graph
• The random cluster model on the complete graph via large deviations
• A simplified second-order Gaussian Poincaré inequality in discrete setting with applications
• On the mixing time of Kac's walk and other high-dimensional Gibbs samplers with constraints
• Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
• Phase transition for the interchange and quantum Heisenberg models on the Hamming graph
• Supercritical percolation on finite transitive graphs I: uniqueness of the giant component
• Expansion in supercritical random subgraphs of expanders and its consequences
• Majority Bootstrap Percolation on the Hypercube
• Percolation on irregular high-dimensional product graphs
• Crux and Long Cycles in Graphs
• The evolution of the random reversal graph
• The giant component after percolation of product graphs
• The diameter of a random subgraph of the hypercube
• Uniform multicommodity flows in the hypercube with random edge‐capacities
• Self‐avoiding walk on the hypercube
• Climbing up a random subgraph of the hypercube
• Phase transition phenomena in random discrete structures
• Building a random network with a given expected giant component
• Mean-field conditions for percolation on finite graphs
• scientific article; zbMATH DE number 7650113 (Why is no real title available?)
• Percolation on dense graph sequences
• Bootstrap percolation in high dimensions
• Connectivity properties of random subgraphs of the cube
• Random induced subgraphs of Cayley graphs induced by transpositions
• Connectivity of the k-Out Hypercube
• A phase transition for the metric distortion of percolation on the hypercube
• Random subgraphs of Cayley graphs over p-groups
• Site percolation on pseudo‐random graphs

This page was built for publication: Largest random component of a k-cube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1166544)