Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

It is well-known that for each planar graph, the number of paths from each source to each sink will give rise to a totally non-negative matrix. However, did anyone ever come up with a planar network whose paths give a matrix whose entries are Eulerian numbers?

share|improve this question
    
Do you need a nondegenerate example? There is one with all the sinks coinciding. –  Gjergji Zaimi Apr 19 '12 at 10:23
    
I was hoping to get a nondegenerate example. But sure, I would love to see even a degenerated one thanks!!! –  Percy Apr 19 '12 at 14:19
add comment

1 Answer

up vote 1 down vote accepted

There is a Bratelli diagram which satisfies this. Consider $\mathbb N^2$ as a graph where the edges are given by k parallel directed edges from $(n,k)$ to $(n+1,k)$, and $n-k+1$ parallel directed edges from $(n,k)$ to $(n+1,k+1)$. Here the number of paths from $(1,1)$ (the unique source) to any vertex $(n,k)$ is the Eulerian number $A(n,k)$, the number of permutations in $S_n$ with exactly $k$ ascents. For a picture see fig.1 in "Random permutations and unique fully supported ergodicity for the Euler adic transformation" by Frick and Petersen. This can be proven quickly using the recurrence $$A(n, k) = (k+1) A(n-1, k) + (n-k+1) A(n-1, k-1).$$

Somewhat similarly one can give a directed graph where the number of paths from the source to any vertex in the graph is equal to an Euler number $E(n,k)$, which counts the number of alternating permutations of $S_n$ which start with $k$. For a picture of how this looks like look at fig.5 in "Generating alternating permutations lexicographically" by Bauslaugh and Ruskey.

share|improve this answer
    
I talked with my adviser today and he was pretty sure that no one has come up with a nondegenerate example. Your answer is pretty enlightening though. Thanks!!! –  Percy Apr 20 '12 at 3:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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