[seqfan] Re: Enumerating DFS on multigraphs

Antti Karttunen antti.karttunen at gmail.com
Thu Mar 2 17:51:27 CET 2017


On Thu, Mar 2, 2017 at 3:54 PM, Li-yao Xia <lysxia at gmail.com> wrote:

> Hello Antti,
>
> Thank you very much for your feedback, and the bijection! Indeed, this
> is the behavior I had in mind. Some illustrations would be a good
> idea, attached are crude ones in ASCII for n=1 to 3, where (tree- and
> back-) edges around some vertices are explicitly numbered, indicating
> the presence of back edges and to disambiguate the two subtle cases.
>

I guess you mean this same pair that I also meant:

 o
 |
1|
 o
 |\2
 |/
 *

 o
 |
2|
 o
 |\1
 |/
 *


But I wonder, shouldn't those edges be labeled instead like this:

 o
 |
 |
 o
1|\2
 |/
 *

 o
 |
 |
 o
2|\1
 |/
 *


?

Or am I missing some subtle point?


I'll make nicer pictures later if I have the time. As you mention,
> there are a couple of parameters to tweak and it would be interesting
> to see what other sequences arise out of that.
>

In graph-wise context, I guess forgetting the relative position (or "side",
in relation to "uplinks") at which of the back-links come back (towards the
root) might make sense? In that case, the above two cases would collapse to
just one, and the enumerating sequence would start as  1, 1, 3, 11, ...
In wonder if that sequence is already in OEIS?
http://oeis.org/search?q=1%2C+1%2C+3%2C+11&sort=&language=&go=Search


> de Bruijn indices offer a mechanical way to encode back edges which
> is convenient for implementation.


Does the condition "*every vertex is a binder" *specify an interesting
subset of all lambda-forms? What about the lambda-forms where not every
vertex is a binder?
Would that subset be e.g. closed regarding the application of its elements
(lambda-forms) to each other? (Maybe I should re-read
http://dkeenan.com/Lambda/ )

Now, I wonder if there is a "natural" isomorphism between natural numbers
and these kinds of lambda-forms? (which are enumerated by
http://oeis.org/A258173 1, 1, 3, 12, 58, 321,)
like there are several between N and the denizens of Catalania proper?
(CC to Jon Awbrey, if this rings any bell for him...)



Best regards,

Antti


I think it's useful to help the
> intuition of people in my circle of acquaintances who are familiar with
> this concept, but otherwise there's not much to read in there from a
> purely combinatorial perspective.
>
> Cheers,
> Li-yao
>
>
> On 03/02/2017 06:40 AM, Antti Karttunen wrote:
>
>> I mean, even though your graph-theoretical interpretation would result a
>> different sequence, I wonder that your "This is just like de Bruijn
>> indices
>> in lambda terms, and here every vertex is a binder" might still be useful
>> interpretation for A258173 ? Or?
>>
>> Best,
>>
>> Antti
>>
>>
>>
>> On Thu, Mar 2, 2017 at 1:01 PM, Antti Karttunen <
>> antti.karttunen at gmail.com>
>> wrote:
>>
>>
>>> On Thu, Mar 2, 2017 at 11:23 AM, Antti Karttunen <
>>> antti.karttunen at gmail.com> wrote:
>>>
>>> Could you prepare an illustration for cases n=1 .. 3 edges (or at least
>>>> for the 12 instances with 3 edges)? That could be a very helpful
>>>> attachment
>>>> to A258173, after it has been proved that it enumerates also your trees.
>>>>
>>>> Best regards,
>>>>
>>>> Antti
>>>>
>>>>
>>>> On Thu, Mar 2, 2017 at 10:56 AM, Antti Karttunen <
>>>> antti.karttunen at gmail.com> wrote:
>>>>
>>>> Dear Li-Yao,
>>>>>
>>>>> Your problem ( http://list.seqfan.eu/pipermai
>>>>> l/seqfan/2017-March/017312.html ) is very interesting.
>>>>>
>>>>> Just now, I'm wondering whether I have got all the parameters
>>>>> correctly.
>>>>> Clearly, the A000108(n) rooted general trees give always a subset of
>>>>> solutions, namely, those DFS-"scans" with no backlinks,
>>>>> e.g. for graphs of three edges, those trees no 4-8 I have illustrated
>>>>> with grude ASCII graphics in https://oeis.org/A179752
>>>>> (The orientation of up-links is important also in your case, isn't it?)
>>>>>
>>>>> But for DFS's with at least one back-link, I only manage to find these
>>>>> ones:
>>>>>
>>>>> E.g., if we indicate a pair of vertices with an immediate back-loop
>>>>> from
>>>>> the upper vertex to the lower as (), then we
>>>>> can add that on the top of a single edge, or below it, or at the left
>>>>> side, or the right side of a single edge, as
>>>>> \() or ()/, and that makes four in total. Then we can have two vertices
>>>>> with one edge going up and two back-edges coming down, and also we can
>>>>> have
>>>>> three vertices stacked on the top of each other as:
>>>>> o
>>>>> |
>>>>> o
>>>>> |
>>>>> o
>>>>>
>>>>> with a single back-edge coming from the top-vertex to the bottom-vertex
>>>>> (root).
>>>>> And that makes six more in total, altogether 5+6 = 11, so I'm still
>>>>> missing one example from your count of 12.
>>>>> Which one it is?
>>>>> (The orientation of back-links in relation to up-links is not
>>>>> important,
>>>>> I guess? Or?)
>>>>>
>>>>>
>>>>> Best regards,
>>>>>
>>>>> Antti
>>>>>
>>>>>
>>>>> I think I see it now:
>>>
>>> Because of this definition:
>>>
>>> data EdgeB = TreeB TreeB | BackB Integer
>>>
>>> your program counts this depth-first-traversal with backlinks twice:
>>>
>>> |
>>> ()
>>>
>>> (root at the bottom)
>>>
>>> that is, it considers either the left hand edge ( or the right hand edge
>>> )
>>> to be the back-link (and the other one respectively the "uplink"). Is
>>> this
>>> the intended behaviour?
>>>
>>> Now, if this is intended (although I'm not sure how it can be justified
>>> "graphically"), then I guess the following simple bijection with the
>>> original interpretation of https://oeis.org/A258173 works:
>>>
>>> For any leaf at height n (with root at 0) in the general rooted oriented
>>> trees (that is, a peak in Dyck path interpretation), one can either leave
>>> that branch intact, or delete that leaf-vertex and draw from its
>>> immediate
>>> ancestor vertex (at height n-1, i.e. one immediately below if the root is
>>> drawn at the bottom) a back-link to any of the n-1 ancestor vertices (at
>>> levels n-2 .. 0). So there is n choices what to do for each leaf at level
>>> n, and this can be done independently of any other leaf-branches, thus
>>> the
>>> multiplication in formula of A258173.
>>>
>>> On the other hand, if this was a mistake in your Haskell-definition, then
>>> it is very interesting mistake.
>>>
>>>
>>> Best regards,
>>>
>>> Antti
>>>
>>>
>>>
>



More information about the SeqFan mailing list