29
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ What did you mean to write when you wrote $p_n\to\infty$? $\endgroup$ Jan 20, 2012 at 10:52
  • $\begingroup$ Ooops! Thanks for point out the error. I meant $p_n\to 0$. I have corrected the typo. $\endgroup$ Jan 20, 2012 at 12:06
  • 6
    $\begingroup$ Actually, discrete Morse theory was invented in the mid-80s by Ken Brown. He calls the notion a collapsing scheme on his paper on rewriting systems and monoid cohomplogy but it is equivalent to the acyclic matching formulation of Forman's theory. $\endgroup$ Jan 20, 2012 at 15:15
  • 2
    $\begingroup$ @Liviu, okay so it's easy to find morse functions theoretically, but maybe not so easy to compute their critical points unless the space is very symmetric or the functions are well chosen. $\endgroup$ Jan 20, 2012 at 15:39
  • 1
    $\begingroup$ @Liviu: I like your question and have been meaning to think about it for some time now, but never seem to have the time. Meanwhile, I hope you don't mind that I added an enumerative-combinatorics tag to it, in case that might draw some additional other people's attention to your question. It seemed to me at least like an interesting relaxation of counting alternating permutations. $\endgroup$ Nov 19, 2012 at 20:35

6 Answers 6

12
$\begingroup$

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$.

$\endgroup$
3
  • 1
    $\begingroup$ Very nice and so simple! $\endgroup$ Nov 20, 2012 at 19:01
  • $\begingroup$ Here are some related asymptotics front.math.ucdavis.edu/1202.2724 $\endgroup$ Nov 20, 2012 at 21:47
  • $\begingroup$ I believe that the upper bound should be $L\leq (405581/10!)^{1/10} = 0.80321\cdots$, which may be compared to the actual value $L=0.7693323708\cdots$. $\endgroup$
    – Ira Gessel
    Jul 8, 2014 at 16:27
15
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ A most satifying answer. Beautiful. $\endgroup$ Jul 9, 2014 at 16:59
10
$\begingroup$

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.

$\endgroup$
1
  • 5
    $\begingroup$ Hi Bruce, welcome to MathOverflow! You might consider registering your account (if you might participate more -- I've been finding this a great place to learn interesting math). $\endgroup$ Nov 20, 2012 at 3:40
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ For $n=1$ the permutations satisfying the desired conditions are (2,1,0), (0,1,2) (0,2,1), (1,2,0). The condition on the permutation involves only interior local maxima and minima. $\endgroup$ Jan 20, 2012 at 16:53
  • 1
    $\begingroup$ I see. My answer was to the similar question of "all even values being minima and all odd values maxima" rather than all minima being even. I still believe you could adjust the idea, considering the probability of each even point being either a minima or a 'through point' $\endgroup$
    – Karl Waugh
    Jan 20, 2012 at 22:13
4
$\begingroup$

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.)

$\endgroup$
1
  • $\begingroup$ You are correct: the discrete gradient flows are the important objects for a topologist. I dealt with them in a relatively recent paper of mine, Combinatorial Morse flows are hard to find front.math.ucdavis.edu/1202.2724 $\endgroup$ Nov 20, 2012 at 21:41
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The function that associates to each cell its dimension is a combinatorial Morse function. Granted, it is not the most efficient computationally. $\endgroup$ Jan 21, 2012 at 10:21
  • 1
    $\begingroup$ Benedetti and Lutz have done some experimental work with algorithmically generating discrete Morse collapsing schemes. An announcement of this work can be found at math.kth.se/~brunoben/OWR2012_Benedetti.pdf although as far as I can tell the full paper hasn't yet made it to the arXiv. $\endgroup$ Nov 21, 2012 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.