Search for: All records

Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of annvertex graph, and need to output a clique. We show that if the input graph is drawn at random from(and hence is likely to have a clique of size roughly), then for everyδ<2 and constantℓ, there is anα<2 (that may depend onδandℓ) such that no algorithm that makesn^δprobes inℓrounds is likely (over the choice of the random graph) to output a clique of size larger than. 

Abstract We study the volume growth of metric balls as a function of the radius in discrete spaces and focus on the relationship between volume growth and discrete curvature. We improve volume growth bounds under a lower bound on the so-called Ollivier curvature and discuss similar results under other types of discrete Ricci curvature. Following recent work in the continuous setting of Riemannian manifolds (by the 1st author), we then bound the eigenvalues of the Laplacian of a graph under bounds on the volume growth. In particular, $$\lambda _2$$ of the graph can be bounded using a weighted discrete Hardy inequality and the higher eigenvalues of the graph can be bounded by the eigenvalues of a tridiagonal matrix times a multiplicative factor, both of which only depend on the volume growth of the graph. As a direct application, we relate the eigenvalues to the Cheeger isoperimetric constant. Using these methods, we describe classes of graphs for which the Cheeger inequality is tight on the 2nd eigenvalue (i.e. the 1st nonzero eigenvalue). We also describe a method for proving Buser’s Inequality in graphs, particularly under a lower bound assumption on curvature.