Largest random component of a k-cube

DOI10.1007/BF02579276zbMATH Open0489.05053OpenAlexW2026620883WikidataQ29041843 ScholiaQ29041843MaRDI QIDQ1166544FDOQ1166544

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

• Evolution of the \(n\)-cube
• Title not available (Why is that?)
• Optimal numberings and isoperimetric problems on graphs
• The longest path in a random graph

Cited In (47)

• 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
• Supercritical site percolation on the hypercube: small components are small
• Hypercube percolation
• Acyclic orientations of random graphs
• The Evolution of Random Subgraphs of the Cube
• Clique percolation
• The component structure of dense random subgraphs of the hypercube
• Random induced subgraphs of generalized \(n\)-cubes
• 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
• The giant component threshold for random regular graphs with edge faults H. Prodinger
• On the critical probability in percolation
• Extreme values for two-dimensional discrete Gaussian free field
• Existence of a phase transition of the interchange process on the Hamming graph
• A simplified second-order Gaussian Poincaré inequality in discrete setting with applications
• The random cluster model on the complete graph via large deviations
• Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
• Supercritical percolation on finite transitive graphs I: uniqueness of the giant component
• Expansion in supercritical random subgraphs of expanders and its consequences
• Phase transition for the interchange and quantum Heisenberg models on the Hamming graph
• On the mixing time of Kac's walk and other high-dimensional Gibbs samplers with constraints
• Majority Bootstrap Percolation on the Hypercube
• Percolation on irregular high-dimensional product graphs
• Crux and Long Cycles in Graphs
• The giant component after percolation of product graphs
• The evolution of the random reversal graph
• Uniform multicommodity flows in the hypercube with random edge‐capacities
• The diameter of a random subgraph of the hypercube
• Self‐avoiding walk on the hypercube
• Climbing up a random subgraph of the hypercube
• Building a random network with a given expected giant component
• Phase transition phenomena in random discrete structures
• Title not available (Why is that?)
• Mean-field conditions for percolation on finite graphs
• 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
• Site percolation on pseudo‐random graphs
• Random subgraphs of Cayley graphs over \(p\)-groups
• Speeding up random walk mixing by starting from a uniform vertex

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)