Randomly twisted hypercubes: between structure and randomness

DOI10.1002/RSA.21267MaRDI QIDQ7027472zbMATH OpenFDO

Authors Itai Benjamini, Yotam Dikstein, Renan Gross, M. E. Zhukovskii

Publication date 14 February 2025

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1002/RSA.21267

zbMATH Keywords

random graphssemicircle lawshortest pathvertex expansion

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80)

Cites work

• A course in combinatorics.
• A hypercube variant with small diameter
• A new variation on hypercubes with smaller diameter
• A survey of the theory of hypercube graphs
• Almost isoperimetric subsets of the discrete cube
• An isoperimetric inequality for Hamming balls and local expansion in hypercubes
• An isoperimetric inequality on the discrete cube and an elementary proof of the isoperimetric inequality in Gauss space
• Analysis of Boolean Functions
• Automorphisms of random graphs with specified vertices
• Cutoff phenomena for random walks on random regular graphs
• Edge rigidity and universality of random regular graphs of intermediate degree
• Inequalities: theory of majorization and its applications
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• On the chromatic number of random \(d\)-regular graphs
• Randomly twisted hypercubes
• Recurrence of distributional limits of finite planar graphs
• Sparse regular random graphs: spectral density and eigenvectors
• Spectra of graphs
• The complexity of approximating vertex expansion
• The diameter of random regular graphs
• The diameter of randomly twisted hypercubes
• The expected eigenvalue distribution of a large regular graph
• The number of perfect matchings, and the nesting properties, of random regular graphs

Cited in

(2)

• Hypercube minor-universality
• Components, large and small, are as they should be I: supercritical percolation on regular graphs of growing degree

This page was built for publication: Randomly twisted hypercubes: between structure and randomness

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