Abstract
We study three mixing properties of a graph: large algebraic connectivity, large Cheeger constant (isoperimetric number) and large spectral gap from 1 for the second largest eigenvalue of the transition probability matrix of the random walk on the graph. We prove equivalence of this properties (in some sense). We give estimates for the probability for a random graph to satisfy these properties. In addition, we present asymptotic formulas for the numbers of Eulerian orientations and Eulerian circuits in an undirected simple graph.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.