3
$\begingroup$

Recall that the Cheeger constant (AKA isoperimetric constant) of a graph $G$ is the infimum of $\frac{\partial S}{vol S}$ over all subsets $S$ of $G$ with volume no larger than $vol(G)/2$. I would like to know about the statistics (average, variance) of the Cheeger constant of a random graph with $n$ vertices. The random process that I have in mind for generating such a graph is to determine whether or not each pair of vertices should be joined by an edge by flipping a coin. However, if the question is easier to answer for other notions of random graph, I would be happy to see the answer.

Note that according to the Cheeger inequality the Cheeger constant can be estimated in terms of the smallest nonzero eigenvalue of the graph's Laplacian matrix. It may be possible to answer this question using results about the statistics of eigenvalues of random matrices, though clearly not every positive definite symmetric integer matrix is the Laplacian of a graph.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.