Gil Kalai’s blog

## From Helly to Cayley IV: Probability

Posted on July 6, 2008 by

I decided to split long part III into two parts. This (truly) last part of this series deals with probabilistic problems and with combinatorial questions regarding higher Laplacians.

### 21. Higher Laplacians and their meanings

Our high dimensional extension to Cayley’s theorem reads:

$\sum |H_{d-1}(K,{\bf Z})|^2 = n^{{n-2} \choose {d}},$

The right hand side of our formula corresponds to the eigenvalues of a higher Laplacian of a complete d-dimensional complex with n vertices. In several general cases there are nice expressions for these eigenvalues - for matroidal complexes, for shifted complexes, for complete skeleta of the cubes and in other cases. There are also nice general high-dimensional matrix-tree theorems.

If $C_k(K)$ is the space of k cycles and we identify it via a certain inner product with the space of k-cocycles, then we can talk about the Laplacian defined by latex $\delta \partial+ (-1)^k \partial \delta$ where $\partial$ is the boundary operator from $C_k$ to $C_{k-1}$ and $\delta$ is the coboundary operator from $C^k$ to $C^{k+1}$.

Spectra of graphs’ Laplacians are very important, for understanding random walks on graphs, for expansion properties and they are also related to many graph parameters like the diameter. The recent series of posts on Luca Trevisan’s blog give a detailed description of these connections (See also this post on James Lee’s blog.) What about higher Laplacians? (Those do not correspond to connectivity but to higher homology groups.)

What is the analog of the random walk interpretation of the spectral gap?

What is the analog of the relation between the spectral gap and expansion properties?

What is the analog of the diameter?

### 22. Probabilistic questions

Consider the class G of all d-dimensional simplicial complexes on n labelled vertices with ${n-1} \choose {d}$ d-faces and a complete (d-1)-skeleton. Is there a substantial probability, for d>1,  that a random complex in G with the property that every (d-1)-face is contained in a d-face (no isolated (d-1)-faces) is Q-acyclic? This is not the case for graphs (d=1). The probability for a graph with n vertices and n-1 edges to be a tree tends to 0 even if it has no isolated vertices. This question has a similar flavour to results regarding singularity of random matrices with 0,1 entries.

Here are other natural probabilistic questions that go back to my old paper.

Inside G consider

A) The class of collapsible complexes

B) The class of contractible complexes

C) The class of Z-acyclic complexes

D(p)) The class of Z/p-acyclic complexes

E) The class of Q-acyclic complexes

For d=1 (graphs) all classes A-E are the same. For d>2 the class C equals the class D.

We can ask if for d >1 as n tends to infinity, a random complex in E is almost surely not in D(p), and a random complex in D(p) is almost surely not in C, and a random complex in C is, for d=2, almost surely not in B, and a random complex in B is almost surely not in A.

Let me also mention that there are several recent results about random simplicial complexes by Linial and Meshulam and by Babson Hoffman and Kahle.

### 23. Russell Lyons problem: Generating random hypertrees

Find a way to generate random Q-acyclic spanning subcomplexes L of a d-dimensional simplicial complex K (with the distribution given by $|H_{d-1}^2 (L)|^2$). One way to do it is to choose a d-face based on the ratio between the weighted number of hypertrees containing and not containing this face. But we want to do something else –  mimicking the beautiful ways of Broder-Aldous and of Wilson to generate a random spanning tree.

This question was raised by Russell Lyons in the context of studying determinental probability measures. (You can read more about determinental processes in this post of Terry Tao,  and this survey paper by J. Ben Hough, Manjunath Krishnapur, Yuval Peres, and Bálint Virág.)

### 24. Diversion: the amazing algorithms of Aldous-Broder and of Wilson to generate random spanning trees.

The Aldous Broder algorithm  goes as follows: Start a random walk on the edges of the graph and add to your tree any edge visited which does not create a cycle, the distribution on the resulting spanning trees is uniform.

The Wilson algorithmgoes as follows: Mark a vertex as a root. (at a later stage the root will be a subtree.) Choose an arbitrary vertex not in the root and make a random walk until hitting the root. Delete all cycles created in this walk and add the remaining path to the root. Returning this process also leads to a uniform random spanning tree.

The paths obtained by Wilson algorithm are called loop erased random walk; we can regard them as a certain random 1-cycle of whose boundary is a presecribed 0-cycle. Something analogous in higher dimension is quite desirable.

### Like this:

This entry was posted in Combinatorics, Probability. Bookmark the permalink.

### 6 Responses to From Helly to Cayley IV: Probability

1. Igor Carron says:

And Jame Lee’s entry would be:
http://tcsmath.wordpress.com/2008/06/15/eigenvalue-multiplicity-and-growth-of-groups/

Igor.

2. Gil says:

Thanks, Igor!

3. Dominic Dotterrer says:

Larry Guth (possibly inspired by M. Gromov and A. Naor) has convinced me that higher expansion constants can be interpreted in the following way:

For a graph, we observe the infimum (over all rectilinear maps to the line) of the maximum (over points in the line) of the number of edges intersecting the preimage of a point in the line.
This is of course, a measure of connectivity closely related to the cheeger/expansion constant.

For a complex, take again infimum (over all rectilinear maps to R^k) of the maximum (over points in the R^k) of the number of of k-faces intersecting the preimage of a point in the affine space.

For the same reason, this constant is a measure of k-connectivity. Thus it should measure “closeness” to a phase-change in the kth cohomology. For this reason, estimates of this constant should be possible using the first positive eigenvalue (i.e. closeness to a phase-change in the dimension of the kernel of the Laplace-Beltrami). But, admittedly, I haven’t yet completed this estimate, though for moral reasons, I am confident it can be done.

Actually writing out higher Laplacians for simplicial complexes shows that \$\delta d\$ acts as a random walk operator on the k-th homology of k-skeleton on the complex. This indicates that a suitable continuous analog could be accomplished by analyzing brownian motion on the loop space of a riemannian manifold (as opposed to getting estimates of the zeroth Laplacian by analyzing brownian motion on the manifold itself).

I am very glad for your post; these things seem to be on my mind quite a bit these days.
Thanks,
Dominic

4. Gil Kalai says:

Thank you, Dominic! I think that a formal theory relating high Laplacians to “hyper” expansion (related to k-connectivity) and to various random walks will be a great progress.

5. Pingback: Plans and Updates « Combinatorics and more

6. Pingback: A Beautiful Garden of Hypertrees « Combinatorics and more

• ### Blogroll

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 11, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8713909387588501, "perplexity_flag": "middle"}