Results 1 to 5 of 5

Math Help - Cauchy-Frobenius-Burnside Theorem

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    Italy
    Posts
    7

    Cauchy-Frobenius-Burnside Theorem

    Use the Cauchy-Frobenius-Burnside Theorem to determine the number of graphs of order 5. Can someone please assist with this question.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: Cauchy-Frobenius-Burnside Theorem

    The setup seems like it must be this:

    Let V = \{v_1, v_2, v_3, v_4, v_5\}, G = Sym(V), X = \{ (x_1, x_2) \in V \times V | x_1 \ne x_2 \}

    Then G induces an action on the power set of X, \mathcal{P}(X). Each subset of X corresponds to some graph with verticies V. Each permutation of the verticies (obviously G \simeq S_5) represents a graph isomophism, and visa-versa, so that the orbit under G of a subset A of X (i.e. of a graph) is the set of graphs isomorphic to A.

    There's a complication to consider in that (v_1, v_2) and (v_2, v_1) represent the same edge, so we could make them equivalent, and so consider only X/~, and let G act on \mathcal{P}(X/\sim). That does seem like a sensible way to proceed, as otherwise we'll be wrongly treating A_1 and A_2 as different graphs, where A_1 = \{ (v_1, v_2) \}, A_2= \{ (v_1, v_2), (v_2, v_1) \}. I haven't thought it out, but that seems like how it should be handled. Without the equivalence classes, we'd be considering digraphs, not graphs.

    That sets it up to apply the CFB Lemma. So the problem becomes computing \mathcal{P}(X/\sim)^g when g \in G. I haven't thought about that, but this maybe will get you started.
    Last edited by johnsomeone; October 8th 2012 at 06:14 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2012
    From
    Italy
    Posts
    7

    Re: Cauchy-Frobenius-Burnside Theorem

    Thanks for your response! Can I ask another question, if we let the set of all automorphisms of G under the operation of function composition be the automorphism group of G, which we denote T(G), or simply T. How would you prove:

    A graph G has fixing number 1 if and only if G contains an orbit of cardinality |T|. Help with either implication would be great if you can.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: Cauchy-Frobenius-Burnside Theorem

    I don't recall a definition for "fixing number". I found this online: "The fixing number of a graph G is the smallest cardinality of a set of vertices S such that only the trivial automorphism of G fixes every vertex in S." It makes the statement work, so I'll assume that's the meaning you intend.

    For my own benefit, I'm going to reason through what "fixing number" "means", especially for fixing number 1:
    1) If S is the set whose cardinality makes the fixing number, then any non-identity automorphism of G moves at least one vertex of S.
    2) If fixing number is 1, then S= {v}, so any non-identity automorphism of G moves v.
    2') Thus fixing number 1 means there exists v in V(G) such that every non-identity automorphism of g of G satisifies g(v) not= v.
    2'') And so fixing number 1 means there exists v in V(G) such that: if g is an automorphism of G, then g(v) = v iff g is the identity.
    2''') And so fixing number 1 means there exists v in V(G) such that the stabilizer of x in the automorphism group of G is trivial.
    3) Special case: what if G has no non-identity automorphisms? Then every orbit has cardinality 1, and fixing number is 1.

    With that in mind, I'll do one direction, and leave the other to you. They're very similar.

    Suppose orbit \mathcal{O} has cardinality |T|.

    Let v \in \mathcal{O}, \text{ and so have } \mathcal{O} = Tv = \{ g(v) | g \in T \}.

    Since |T| = |\mathcal{O}| = |\{ g(v) | g \in T \}|, must have that images of T's action on v are all distinct.

    Thus, since id(v) = v, no other element of T can fix v. Thus S = {v} satisfies the definition for fixing number, and so the fixing number is 1.
    Last edited by johnsomeone; October 9th 2012 at 11:27 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2012
    From
    Italy
    Posts
    7

    Re: Cauchy-Frobenius-Burnside Theorem

    That's awesome thanks! For the reverse implication would the following be the idea:

    Assume the fixing number is 1, so the fixing set is S = {v} for some vertex v of G. Then the only automorphism that keeps v fixed is id(v) = v and for any other automorphism g we know that g(v) does not equal v. Also if we take any automorphisms g_1 and g_2 from T which are not the identity automorphisms then assume g_1(v) = g_2(v), it follows that g_1g_2(v) = v but since S = {v} satisfies the definition for fixing number it follows that g_1(v) does not equal g_2(v) and the results follows easily from that.

    If there is only one automorphism g other that the identity then we still have that g(v) cannot equal v and the results follows.

    As you said if G has no non-identity automorphisms then every orbit has cardinality 1, and fixing number is 1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cauchy's residue theorem - help
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: August 16th 2010, 05:17 AM
  2. cauchy's integral theorem
    Posted in the Calculus Forum
    Replies: 2
    Last Post: April 10th 2010, 03:54 AM
  3. Cauchy's Integral theorem
    Posted in the Calculus Forum
    Replies: 1
    Last Post: March 18th 2010, 07:01 AM
  4. Burnside's Lemma problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 6th 2010, 03:20 PM
  5. cauchy theorem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 4th 2009, 09:31 PM

Search Tags


/mathhelpforum @mathhelpforum