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:
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 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 where is the boundary operator from to and is the coboundary operator from to .
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 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.
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 ). 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.