Fourier analysis on finite groups is well known to be useful for probability theory and combinatorics — consider for example the Fourier analysis on $(\mathbb Z/2\mathbb Z)^n$ which can be used to get interesting results about sharp thresholds and noise stability and so on. It is, fortunately, concrete and easy enough that you don't need to be much of an algebraist to do something interesting.

Now, unfortunately, sometimes objects can't be easily coded by a sequence of independent bits, even if the bits are allowed to take more values. For a simple example, consider the set of graphs with n vertices and m edges. We can no longer consider a “small perturbation” of this to be rerandomizing some bits.

What we can do instead is this: Pick a pair of vertices between which there is an edge, and a pair which do not have an edge between them. Move the edge from the first pair to the second, getting a new graph with the same amount of vertices and edges, which is very similar.

I just noticed that this actually naturally creates a groupoid: Consider the category of graphs with $n$ vertices and $m$ edges, with morphisms being these switchings and compositions thereof. The same construction of course gives a groupoid for other classes of objects and switchings between them as well.

So since Fourier analysis is useful for studying perturbations in other contexts, I was wondering if there is some such thing here as well. Google tells me that abstractly there is, but is it possible to work out what it concretely is for a concretely given finite groupoid like this?

  • 1
    $\begingroup$ When you refer to Fourier analysis on finite groups, these might not be commutative. In that case, would the matrix-valued Fourier transform be the kind of "concrete" Fourier analysis you are after? $\endgroup$
    – Yemon Choi
    Oct 1 '20 at 18:02
  • 1
    $\begingroup$ (Just trying to get an idea of what is desired for the group case before we hit the groupoid case) $\endgroup$
    – Yemon Choi
    Oct 1 '20 at 18:03
  • 1
    $\begingroup$ The one application that immediately comes to mind where the group is not abelian is the stuff with representations of the symmetric group being used to analyse mixing times of card shuffles. So that's the sort of concrete I wish for -- not just "there exists", but the ability to actually write down the result of the transform on specific functions, for example. $\endgroup$ Oct 1 '20 at 19:06
  • $\begingroup$ Thanks. Another request for clarification: are these labelled or unlabelled graphs? Can I think of adjacency matrices or do I have to think of equivalence classes of adjacency matrices $\endgroup$
    – Yemon Choi
    Oct 1 '20 at 20:10
  • $\begingroup$ I think seeing it as labelled graphs is actually better for generalizing the ideas to other models which may not be homogeneous, in addition to being perhaps easier. $\endgroup$ Oct 1 '20 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.