0
$\begingroup$

I'm reading this post and I'm getting a little confused. I am trying to find a useful notion of the Mobius function for directed graphs and have had little success in my search. I don't know much about graphs but I have done some enumerative combinatorics. So I guess my questions are:

  1. What graphs do they mean? Directed or undirected? With single edges or with multiple edges?
  2. What is the $M$ in that post? Is it the multiset of prime cycles (What is a prime cycle?)
  3. What is the Mobius function $\mu(M)$? Is it the same as the order theoretic Mobius function for the lattice of subsets of a multiset?
  4. Is there a reference for the Mobius function and Ihara zeta function result that they mention?
$\endgroup$
4
  • 1
    $\begingroup$ It's been many years since I thought about this, so rather than try to write a new answer and risk getting things wrong, I can only recommend reading through the old answer carefully and asking questions in the comments when you get stuck. In particular, you will need to follow the many links in that post to other Math.SE questions, answers, comment threads, and chat threads, as well as resources elsewhere. One thing you should definitely look at is the article by Horton, Stark, and Terras linked from that post. $\endgroup$
    – Will Orrick
    Commented Sep 9, 2023 at 22:44
  • 1
    $\begingroup$ The graphs in the old answer are undirected but can contain loops and multiple edges, if I remember correctly. Your definitions of $M$ and Möbius function are correct. Prime cycle has a somewhat involved, non-intuitive definition, but is given in the Horton, Stark, and Terras article. Some of the examples in my answer and in the links there show its use in practice. $\endgroup$
    – Will Orrick
    Commented Sep 9, 2023 at 22:45
  • 1
    $\begingroup$ Some googling turns up an article by Horton called "Ihara zeta functions of digraphs", which sounds relevant. You might have already seen it. $\endgroup$
    – Will Orrick
    Commented Sep 9, 2023 at 22:51
  • $\begingroup$ Ok I see. I have been looking at the Horton, Stark and Terras article. I will look at the Horton article as well. Thank you!! That was helpful. $\endgroup$
    – joe
    Commented Sep 10, 2023 at 8:20

0

Reset to default

You must log in to answer this question.