Proves that the giant component in hypercube bond percolation at p = c/d > 1 has diameter Θ(d) and lazy random walk mixing time Θ(d²).
Title resolution pending
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
verdicts
UNVERDICTED 2representative citing papers
For p = d/n the r-th power has maximum degree ~ log n over (r+1)-fold log and chromatic number sandwiched between the maximum degrees of the floor(r/2) and (r-1) powers plus one (equality at r=2); for d = omega(log n) up to n^{1/r-Omega(1)} the chromatic number is Theta(d^r / log d).
citing papers explorer
-
Diameter and mixing time of the giant component in the percolated hypercube
Proves that the giant component in hypercube bond percolation at p = c/d > 1 has diameter Θ(d) and lazy random walk mixing time Θ(d²).
-
Coloring powers of random graphs
For p = d/n the r-th power has maximum degree ~ log n over (r+1)-fold log and chromatic number sandwiched between the maximum degrees of the floor(r/2) and (r-1) powers plus one (equality at r=2); for d = omega(log n) up to n^{1/r-Omega(1)} the chromatic number is Theta(d^r / log d).