5
$\begingroup$

Let $\Omega_n$ denote the symmetric/permutation group on $n$ objects. Let $T_n \subseteq \Omega_n$ denote the set of transpositions. Drop the $n$-subscripts.

Define the Cayley graph $G = (\Omega, E)$ by saying that $\sigma, \sigma' \in \Omega$ are adjacent if $\sigma^{-1} \sigma \in T$, ie they differ by a transposition. One can use the Aldous spectral gap conjecture to show that the spectral gap of (the simple random walk on) this graph is $1/n$. A standard result by multiple authors (Jerrum and Sinclair, to name two) then says that $1/n^2 \lesssim \Phi_* \lesssim 1/n$ where $\Phi_*$ is the isoperimetric constant: $$ \Phi(S) := \frac{|\partial S|}{|S|} \quad\text{and}\quad \Phi_* := \min_{|S| \le |\Omega|/2} \Phi(S),$$ where $\partial S$ is the edge boundary of the set $S$. This is a worst-case bound.

I am interested in a better understanding of the isoperimetric profile $\Phi(S)$, not just for the worst-case $S$. References and the like would be appreciated.

Consider this example. Define $S$ by including every permutation independently with probability $\tfrac12$. (I just mean site $\tfrac12$-percolation by this.) Fix any transposition $\tau \in T$. Define $$ \partial_\tau S := \{ \sigma \tau \mid \sigma \in S \text{ and } \sigma \tau \notin S \}. $$ One can pair up all the permutations: $(\sigma, \sigma \tau)$ where $\sigma$ ranges over a set of size $\tfrac12 |\Omega|$. This outlook shows that $$ |\partial_\tau S| \sim \textrm{Bin}(|\Omega|, \tfrac14). $$ Indeed, for every point in $S$ there is a $\tfrac12$ chance that its pair is not in $S$. Also, $|S| \sim \textrm{Bin}(|\Omega|, \tfrac12)$. Thus $ \Phi(S) \approx \tfrac12. $ So if $S$ is drawn in this sense then typically it has isoperimetric expansion roughly $\tfrac12$. This is much better than the worst-case, which is at least as bad as $1/n$.

Ideally I would like to determine some characterisation of the set of 'expanding' sets, ie ones with $\Phi(S) \asymp 1$. More formally, define $\mathcal P_c := \{ S \subseteq \Omega \mid \Phi(S) \ge c \}$ for $c \ge 0$. Then $\mathcal P_0$ is just the power set of $\Omega$. I am after some characterisation of $\mathcal P_c$, or some large subset of it, for $c > 0$ fixed and $n \to \infty$.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Just a remark: from where I stand (a differential geometer with interest in isoperimetric inequalities), I would say that the isoperimetric profile is about the best case: having a large boundary is easy, one only needs to add wrinkles or holes every now and then. What is dificult is to have small perimeter. So, I would fear that your question could have no good answer: most sets should have large perimeter, as well shown from your probabilistic argument. Maybe you should explain what type of characterization you seek? $\endgroup$
    – Benoît Kloeckner
    Commented Jan 22, 2021 at 12:35
  • $\begingroup$ Interesting, @BenoîtKloeckner! Always nice to get other viewpoints. I'm looking to show a spread of a growing set (evolving sets to be precise). It grows/shrinks proportionally to its boundary. Namely, either the entire external boundary is added or the entire internal boundary is deleted; it is slightly more likely to add than remove so overall grows. I want to show that it grows quickly and thus want a large boundary. "Small boundary" is thus bad for me. The "characterisation" is very informal. I just want this process to satisfy $\Phi(S_t) \asymp 1$ for lots of $t$ $\endgroup$
    – Sam OT
    Commented Jan 22, 2021 at 14:02
  • $\begingroup$ Hum, if we see this from a differential geometry point of view, such a growth process could end up creating relatively round balls, close to isoperimetric (and thus with small perimeter). The analogy is far-fetched, but I am not confident in what you expect. $\endgroup$
    – Benoît Kloeckner
    Commented Jan 22, 2021 at 19:17
  • $\begingroup$ Yes, this is strongly related to what I was thinking. However, other results tell me that if I draw the transposition uniformly at each step then it takes time order n log n to absorb at its maximal size. This is just the mixing time of the Random Transposition shuffle. So it surely must be the case that $\Phi(S_t)$ is typically order 1, since $|\Omega|$ goes somewhat like $e^{n \log n}$ $\endgroup$
    – Sam OT
    Commented Jan 22, 2021 at 23:04
  • 1
    $\begingroup$ So, I was being pretty rough so as to not overload with not-so-relevant details, but I may have gone too far the other way. Suppose one pre-specifies a specific transposition $\tau$ to use, ie chooses the "direction", and does a lazy step in this "direction". Define the external boundary $\partial_\tau^+ S$ of a set $S \subseteq \Omega$ to be $\{ x \tau \mid x \in S, \: x \tau \notin S \}$ and similarly for internal $\partial_\tau^- S$. Then the set process either adds all of $\partial_\tau^+ S_t$ or removes all of $\partial_\tau^- S_t$. I fear this is going away from the original topic... $\endgroup$
    – Sam OT
    Commented Jan 24, 2021 at 22:11

1 Answer 1

Reset to default
4
$\begingroup$

This reply is a bit too long for a comment, but it responds mainly to the comment from the OP who wrote that "it surely must be the case that $\Phi(S_t)$ is typically of order 1". The mixing time bound using evolving sets need not be sharp, and there are results (see [2]) that support Benoît Kloeckner's intuition that the evolving sets are typically "round", i.e., provide sparse cuts.

The full spectrum (not just the spectral gap) of random transpositions has been known long before the Aldous conjecture, see [3].

[1] Morris, Ben, and Yuval Peres. "Evolving sets, mixing and heat kernel bounds." Probability Theory and Related Fields 133, no. 2 (2005): 245-266.

[2] Andersen, Reid, and Yuval Peres. "Finding sparse cuts locally using evolving sets." In Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 235-244. 2009.

[3] Diaconis, Persi, and Mehrdad Shahshahani. "Generating a random permutation with random transpositions." Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 57, no. 2 (1981): 159-179.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks, Yuval, for your comments. I wasn't aware of [2]. I shall certainly look at it! Also, I realise [3] gives the references, but personally I find it rather more difficult to understand why from [3] than from the Aldous spectral gap conjecture. Hence why I gave the latter as the reference. || Onto $\Phi(\cdot)$... Italicising "must" was perhaps a little presumptuous. I realise that the evolving sets need not be tight, however I feel that intuitively in a transitive graph like this one one would expect it to be tight up to constants. Would you agree? Why do I think this? [cont...] $\endgroup$
    – Sam OT
    Commented Jan 23, 2021 at 9:23
  • $\begingroup$ The walk $X_t$ is uniform on the Doob transform $\tilde S_t$. If $|\tilde S_t| = o(|\Omega|)$, then the walk is uniform on a set of size $o(|\Omega|)$. Of course, if $\tilde S_t$ is a singleton, but which singleton uniformly distributed, then the walk is mixed. The "roundness" suggests to me that it grows, not moving around the state space. Rather one can define a set $A_t$ with $|A_t| = o(|\Omega|)$ such that $X_t \in \tilde S_t \subseteq A_t$ whp. At the very least $\tau = \inf\{t:\tilde S_t=V\}$ will not be much large than $n \log n$---certainly $\Phi_*^{-1} n \log n$ seems implausible...? $\endgroup$
    – Sam OT
    Commented Jan 23, 2021 at 9:25
  • $\begingroup$ Does this not seem like a fairly reasonable heuristic to you? Or do you feel the evolving sets behave in a different way? :-) $\endgroup$
    – Sam OT
    Commented Jan 28, 2021 at 9:18
  • $\begingroup$ This heuristic seems reasonable. But comparing the isoperimetry of the evolving set to a uniformly chosen random set seems less reasonable. e.g. consider an $n$ by $n$ torus where the mixing time $n^2$ means that usually the evolving set has a small boundary $\endgroup$
    – Yuval Peres
    Commented Jan 28, 2021 at 16:04
  • $\begingroup$ Oh, yes, certainly. Note that the OP doesn't mention evolving sets at all. I was merely showing that "typical" sets in a certain sense are nothing like the worst. Apologies for not making that clear! Certainly it seems to me that evolving sets should be fairly round. My hope was that a reference regarding "typical" sets in any sense would help in my quest to understand typical evolving sets :-) $\endgroup$
    – Sam OT
    Commented Jan 28, 2021 at 20:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .