Mixing time of the lazy and simple random walk on a randomly twisted hypercube
En palabras de los autores
We consider a randomly twisted hypercube on vertices and study a simple or lazy random walk on this graph. We show that for both walks the mixing time is of order , and the model does not exhibit cutoff. We also establish that both walks have cover time of order , and we show that the chromatic number of the graph diverges.
Resultado principalEl resumen no menciona limitaciones.
Apareció: viernes, 16 de octubre. arXiv. Preprint, todavía sin revisión por pares.