Combinatorial Morse functions and random permutations

Question

This question has its origin in combinatorial topology. In the 90s R. Forman proposed a discrete counterpart of Morse theory. In his case, a Morse function on a triangulated space is a function that assigns a number to each face and satisfying certain conditions.

The theory has found beautiful applications, but it has one limitation: discrete Morse functions are hard to find, unlike the smooth case where smooth Morse functions are a dime a dozen. That made me think that maybe there aren't too many such discrete Morse functions. So naturally one can ask, really, how many Morse functions are out there on a given triangulated space.

The present question deals with the simplest triangulated space, namely a line segment divided into $n$-subintervals. The problem of counting the combinatorial Morse functions on this triangulated space reduces to the following purely combinatorial problem.

Consider the group $S_{2n+1}$ of permutations of the set

$$ V_n:=\lbrace 0,1,\dotsc,2n\rbrace. $$

A point $i\in V_n$ is called an interior point if $i\neq 0,2n$. An interior point $i\in V_n$ is a local minimum of a permutation $\phi\in S_{2n+1}$ if

$$ \phi(i-1)> \phi(i) <\phi(i+1). $$

A local maximum is defined in a similar fashion. Here is now the question.

Denote by $p_n$ the probability that a random permutation of $S_{2n+1}$ has the property that all its interior local minima (if any) are even and all its interior local maxima (if any) are odd. Is it true (as I believe) that $p_n\to 0$ as $n\to\infty$? Can one be more precise about the behavior of $p_n$ as $n\to\infty$?

For example, when $n=1$ the permutations of $\lbrace0,1,2\rbrace$ satisfying the above constraints are

$$ (0,1,2), (2,1,0), (0,2,1), (1,2,0). $$

Hence $p_1=\frac{2}{3}$.

Thanks.

Answer 1

The suggestion of Karl Waugh can be fixed. Let us call a permutation nice if it satisfies the conditions of the problem. Let $a_0 a_1\cdots a_{2n}$ be a permutation of $V_n$. There are six possible orderings of the numbers $a_0, a_1, a_2$, all equally likely. Two of these orderings are incompatible with niceness, so there is a $2/3$ probability of compatibility. Similarly there is a $2/3$ probability, independent from the values of $a_0,a_1,a_2$, that $a_3,a_4,a_5$ are compatible with niceness. Continuing this argument gives an upper bound of $(2/3)^{\lfloor (2n+1)/3\rfloor}\to 0$ on the probability for a permutation of $0,1,\dots,2n$ to be nice.

A further thought. Alternating permutations are nice. The number $E_n$ of alternating permutations of $1,2,\dots,n$ (an Euler number) satisfies $E_n\sim C(2/\pi)^nn!$. If $f(2n+1)$ denotes the number of nice permutations of $V_n$, then this suggests that the limit $$ L=\lim_{n\to \infty} \left( \frac{f(2n+1)}{(2n+1)!}\right)^{1/(2n+1)} $$ exists. The observations above show that then $$ \frac{2}{\pi}=0.6366\cdots \leq L\leq\left(\frac 23\right)^{1/3}= 0.8735\cdots. $$ It would be interesting to determine this limit. The upper bound can be made arbitrary close to $L$ by looking at blocks of length $k$ (rather than of length three) as $k\to\infty$. Doing it for $k=10$ yields (modulo computational error) an upper bound of $L\leq (405581/10!)^{1/5} = 0.64515\cdots$.

Answer 2

This is a sketch of a solution by my student Yan Zhuang and me. A paper with all the details (and further results) can be found in Counting permutations by alternating descents, Electronic J. Combin. 21 (4) (2014), Paper #P4.23.

We find the exact exponential generating function for counting these permutations and derive the asymptotics from it.

First, there is no reason from the enumerative point of view to consider only permutations of odd length. So let $u_n$ be the number of permutations of $\{1,2,\dots, n\}$ in which every peak is even and every valley is odd, where a peak of $\pi\in S_n$ is an $i$, with $1<i<n$, such that $\pi(i-1)<\pi(i)>\pi(i+1)$, and valleys are defined similarly. The first few values of $u_n$ are $u_0=1$, $u_1=1$, $u_2=2$,$u_3=4$, $u_4=13$, $u_5=50$, $u_6=229$. Let \begin{equation} U(x) = \sum_{n=0}^\infty u_n \frac{x^n}{n!}.\end{equation} The nicest formula for $U(x)$ is \begin{equation} U(x) = \left( 1-E_1x +E_3 \frac{x^3}{3!}-E_4\frac{x^4}{4!}+E_6\frac{x^6}{6!}-E_7\frac{x^7}{7!} +\cdots\right)^{-1}, \tag{1}\end{equation} where $$\sum_{n=0}^\infty E_n \frac{x^n}{n!} = \sec x + \tan x.$$ A formula equivalent to (1) which is more useful for asymptotics is \begin{equation}U(x) = \frac{3\sin\frac x 2 + 3\cosh \frac {\sqrt3}{2} x} {3\cos \frac x 2 -\sqrt 3\sinh \frac{\sqrt3}{2} x}. \tag{2}\end{equation}

Since $U(x)$ is meromorphic with a single simple pole on its circle of convergence, at $x=\alpha:=1.299828316\cdots$, we find by standard techniques that $u_n/n!$ is asymptotic to $2\beta^{n+1}$, where $\beta:=\alpha^{-1}=.7693323708\cdots$.

Formula (2) can be proved by finding a recurrence for $u_n$, converting it to a differential equation, and solving it. (We need to use an auxiliary sequence, and consider even and odd $n$ separately, so we actually get a system of four differential equations.)

We can give a more conceptual proof of (1). We first note that the similar-looking exponential generating function \begin{equation}\left( 1-x + \frac{x^3}{3!}-\frac{x^4}{4!}+\frac{x^6}{6!}-\frac{x^7}{7!} +\cdots\right)^{-1}\tag{3}\end{equation} (OEIS sequence A049774) counts permutations with no increasing run of length greater than 2.

We may define an alternating run of a permutation $\pi$ to be a maximal subsequence of the form $\pi(2i)<\pi(2i+1)>\pi(2i+2)<\cdots\mathrel{<\atop >}\pi(j)$ or $\pi(2i+1)>\pi(2i+2)<\pi(2i+3)>\cdots \mathrel{<\atop >}\pi(j)$. Then the permutations counted by $u_n$ are permutations with no alternating run of length greater than 2, and (1) can be proved in a way that is analogous to the proof of (3).

Formulas involving the numbers $E_n$ and “alternating descents”, using the same basic idea, have been proved by Denis Chebikin, Variations on descents and inversions in permutations, Electronic J. Combin. 15 (2008), Research Paper R132.

Answer 3

Originally I thought that the answer to your question could be deduced from results in a recent paper written by Sara Billey, Chris Burdzy, and myself, arXiv:1209.0693. Theorem 1.1 in that paper gives an enumeration result for the number of permutations in S_n which have a given set of peaks (what you are calling interior local maxima). Unfortunately, the theorem only applies if the number of elements in the peak set is constant with respect to n, which is not true in this case. It would be very interesting to find an analogue of this theorem where the size of the peak set varies with n.

Cheers, Bruce Sagan

PS Thanks to Richard Stanley for pointing out this post to us.

Answer 4

Attempting to answer the final question, I think the following should do it but I'm not 100% certain.

By hand we can see that if n=1, that exactly 2 out of the 6 permutations satisfy the condition, making 1 a maxima. If we move to n=2, then we have to make sure 1 and 3 are both maxima, 2 being a minima will follow from these.

If we look at just the movement of numbesr 0, 1 and 2, and 'restrict' the permutations to these - aka if they go to 0, 4, 3 then we can treat that as 0, 2, 1 by lowering values until they're in the range - then it isn't hard to see that thus 1/3rd of permutations make 1 a maxima, and that a 1/3rd will make 3 a maxima. Thus $p_2 \le 1/9$.

A similar arguement should be able to show that $p_n \le (1/3)^n$ which will satisfy your claim.

Answer 5

Please allow me to answer an amended question. It seems better to me to count discrete gradient flows instead of discrete Morse functions (of course this is a matter of opinion). In the case of the subdivision of the segment into n subintervals, the number of discrete gradient flows is the number of matchings on a path with 2n edges. This is the Fibonacci number $F_{2n+1}$ (if $F_0=F_1=1$).

(Here I consider the Hasse diagram on the poset of nonempty faces of a regular cell complex. One directs every edge in this diagram downwards, and a discrete gradient flow is obtained by reversing some set of edges so that each vertex is contained in at most one reversed edge and the resulting directed graph has no directed cycles. Each discrete Morse function f gives rise to a discrete gradient flow, by directing an edge from the face getting the larger value under f to the face getting the smaller value.)

Answer 6

While the original question regarding permutations is interesting, it is not true that combinatorial Morse functions are hard to construct algorithmically on regular CW complexes. Much work has gone into this: see for instance the work of Lewiner. It doesn't take much: here is a simple algorithm based on Mrozek's coreduction approach from this paper.

Given regular CW complex $X$ we construct the discrete Morse function $\mu:X \to \mathbb{R}$.

1. Pick either a minimum dimensional cell $a \in X$ with no $\mu$ value assigned, or a cell pair $(k,q) \in X^2$ with $q$ being the only element in the boundary of $k$ with no $\mu$ value assigned.

2. In case you picked the single cell $a$, assign it a value strictly larger than the maximum $\mu$-value encountered among cells in the boundary of $a$. This will be a critical cell of $\mu$.

3. In case you picked the pair $(k,q)$, assign both $k$ and $q$ the same $\mu$-value which must be higher than the maximum $\mu$-value encountered among non-$q$ cells in the boundary of $k$. This corresponds to setting $V(q) = \pm k$ where $V$ is the discrete gradient vector field for $\mu$.

Repeat until the complex $X$ is exhausted.