Intereting Posts

Do we know if there exist true mathematical statements that can not be proven?
How to find the closed form formula for this recurrence relation
Expressing a root of a polynomial as a rational function of another root
Smallest multiple whose digits are only ones and zeros
Is there a good way to compute Christoffel Symbols
Retracts are Submanifolds
Integration of $\int_0^\infty\frac{1-\cos x}{x^2(x^2+1)}\,dx$ by means of complex analysis
Integration of exponential with square
Is this condition enough to determine a random variable?
Proof of $\int_0^\infty \frac{x^{\alpha}dx}{1+2x\cos\beta +x^{2}}=\frac{\pi\sin (\alpha\beta)}{\sin (\alpha\pi)\sin \beta }$
Difference between dimension and rank of matrix
Compact metrizable space has a countable basis (Munkres Topology)
Show rigorously that Pólya urn describes a martingale
A complete metric space with approximate midpoints is intrinsic
Preparing for Mathematics Olympiad

How many ways can one paint the edges of a Petersen graph black or white?

I know that the symmetrygroup of the Petersen graph is $

[S5][1]$. Furthermore this this seems like a case where I should use Burnside’s lemma. I’m sorry if the following is too verbose or uses non standard notation; I haven’t been acquainted with graph theory.

S5 has 7 conjugacy classes, namely those with cycle types: (1,1,1,1,1),(1,1,1,2),(2,2,1),(2,3),(1,1,1,3),(4,1),(5). S5 has 15 edges so the identity (1,1,1,1,1) would leave $2^{15}$ different colorings fixed. The n-cycle (5) is a rotation of the whole graph and as such would leave $2^3$ colorings fixed. The “outside” could be white or black, the connecting edges and the “inside” edges could both be either white or black. Rotation around one “connecting” edge involves the (2,2,1) cycles. I won’t tire you with the details but I found $2^9$ colorings.

- How does the topology of the graphs' Riemann surface relate to its knot representation?
- Every planar graph has a vertex of degree at most 5.
- Coloring Graph Problem
- Is the empty graph connected?
- Graph Run Time, Nodes and edges.
- Showing ${1\over n}\sum|S_i|=O(\sqrt n)$ for $S_i\subset $, $|S_i\cap S_i|\le 1$ for $i\ne j$

From here I’m stuck however, I can’t find any more symmetries than these. How do I find the colorings left fixed by the other conjugacy classes?

- Show that a matched set of nodes forms a matroid
- abelian finite groups - basic
- G is group of order pq, pq are primes
- Degree sequence of connected graphs
- Finding the order of the automorphism group of the abelian group of order 8.
- Classification of the decomposable primitive permutation groups
- associativity in graph theory
- explicit upper bound of TREE(3)
- About conjugacy in $A_n$
- What is the difference between homomorphism and isomorphism?

I hope I can be of help here even if my approach is not the most sophisticated. I have written a Maple program to compute the action of the automorphism group $G$ of the Petersen graph on its edges (giving the edge permutation group $Q$), using properties that are documented at Wikipedia. My vertices are the number pairs that can be chosen from $\{1, 2, 3, 4, 5\}$. I used a brute force method going through all vertex permutations and checking that they preserve the property that two vertices are adjacent iff the two number pairs are disjoint, i.e. the Kneser graph property of the Petersen graph. That yields the automorphism group $G$ of the vertices. To conclude apply every permutation from $G$ to the edges, thereby obtaining $Q$ and its cycle index. At this point it remains to substitute $x+y$ into the cycle index according to Polya’s theorem to obtain the generating function of the orbits. There are $396$ of them.

This is the cycle index:

$$Z(Q) = {\frac {1}{120}}\,{a_{{1}}}^{15}+{\frac {5}{24}}\,{a_{{2}}}^{6}{a_{{1}}}^

{3}+1/6\,{a_{{3}}}^{5}+1/6\,a_{{3}}{a_{{6}}}^{2}+1/4\,{a_{{4}}}^{3}a_{{2}

}a_{{1}}+1/5\,{a_{{5}}}^{3}.$$

Substituting $x+y$ into $Z(Q)$ yields

$$Z(Q)_{x+y} = {\frac {1}{120}}\, \left( x+y \right) ^{15}+{\frac {5}{24}}\, \left( {x}^

{2}+{y}^{2} \right) ^{6} \left( x+y \right) ^{3}\\ +1/6\, \left( {x}^{3}+{y}

^{3} \right) ^{5}+1/6\, \left( {x}^{3}+{y}^{3} \right) \left( {x}^{6}+{y

}^{6} \right) ^{2} \\ +1/4\, \left( {x}^{4}+{y}^{4} \right) ^{3} \left( {x}^{

2}+{y}^{2} \right) \left( x+y \right) +1/5\, \left( {x}^{5}+{y}^{5}

\right) ^{3}.$$

Expanding we find the generating function that classifies the edge colorings according to the two colors:

$$Z(Q)_{x+y} = {x}^{15}+{x}^{14}y+3\,{x}^{13}{y}^{2}+9\,{x}^{12}{y}^{3}+19\,{x}^{11}{y}^

{4}+37\,{x}^{10}{y}^{5}+58\,{x}^{9}{y}^{6}+70\,{x}^{8}{y}^{7}\\ +70\,{x}^{7}

{y}^{8}+58\,{x}^{6}{y}^{9}+37\,{x}^{5}{y}^{10}+19\,{x}^{4}{y}^{11}+9\,{x}

^{3}{y}^{12}+3\,{x}^{2}{y}^{13}+x{y}^{14}+{y}^{15}.$$

Setting $x=1$ and $y=1$ we find that the total count is equal to $$396.$$

The Maple program follows for all group theory enthusiasts who are also programmers! If there are any concrete questions as to what the individual functions do I will be happy to answer them. I can also resend the program if there are problems with the formatting. Enjoy! Comments are welcome.

with(group): with(combinat): pet_verts := convert(choose({seq(k, k=1..5)}, 2), list); pet_edges_set := {}; for v1 in pet_verts do for v2 in pet_verts do if v1 intersect v2 = {} then pet_edges_set := pet_edges_set union {{v1, v2}}; fi; od; od; pet_edges := convert(pet_edges_set, list); pet_is_autom := proc(vperm) local allsubs, e, eperm, el; allsubs := [seq(pet_verts[pos]=vperm[pos], pos=1..nops(vperm))]; eperm := subs(allsubs, pet_edges); for e in eperm do el := convert(e, list); if el[1] intersect el[2] <> {} then return false; fi; od; return true; end; pet_vautom := []; pet_compute_vautom := proc() option remember; global pet_vautom; local perm, vperm, pos, count; count := 0; perm := firstperm(nops(pet_verts)); while type(perm, `list`) do vperm := [seq(pet_verts[perm[q]], q=1..nops(pet_verts))]; if pet_is_autom(vperm) then count := count+1; printf("automorphism %d\n", count); pet_vautom := [op(pet_vautom), vperm]; fi; perm := nextperm(perm); od; pet_vautom; end; pet_compute_vautom(): pet_autom2cycles := proc(src, aut) local numa, numsubs; local marks, pos, cycs, cpos, clen; numsubs := [seq(src[k]=k, k=1..nops(src))]; numa := subs(numsubs, aut); marks := [seq(true, pos=1..nops(aut))]; cycs := []; pos := 1; while pos <= nops(aut) do if marks[pos] then clen := 0; cpos := pos; while marks[cpos] do marks[cpos] := false; cpos := numa[cpos]; clen := clen+1; od; cycs := [op(cycs), clen]; fi; pos := pos+1; od; return mul(a[cycs[k]], k=1..nops(cycs)); end; pet_vperm2eperm := proc(vperm) local allsubs, e, eperm, el; allsubs := [seq(pet_verts[pos]=vperm[pos], pos=1..nops(vperm))]; return subs(allsubs, pet_edges); end; pet_cycleind_petersen_edges := proc() option remember; local vperm, eperm, s; s := 0; for vperm in pet_vautom do eperm := pet_vperm2eperm(vperm); s := s + pet_autom2cycles(pet_edges, eperm); od; s/nops(pet_vautom); end; pet_varinto_cind := proc(poly, ind) local subs1, subs2, polyvars, indvars, v, pot, res; res := ind; polyvars := indets(poly); indvars := indets(ind); for v in indvars do pot := op(1, v); subs1 := [seq(polyvars[k]=polyvars[k]^pot, k=1..nops(polyvars))]; subs2 := [v=subs(subs1, poly)]; res := subs(subs2, res); od; res; end; pet_cycleind_petersen_edges(); latex(%); gf := pet_varinto_cind(x+y, pet_cycleind_petersen_edges()); latex(gf); latex(expand(gf)); subs({x=1, y=1}, gf);

**Addendum Mar 24 2016.** A much improved solution to this problem is at the following MSE link which renders the above obsolete.

Using Burnside’s lemma is the right idea.

Each element of $S_5$ determines a permutation of the 15 edges of the Petersen graph. If this permutation has exactly $r$ cycles on edges, then it fixes exactly $2^r$ 2-colorings of the edge set. If $a$ and $b$ are conjugate elements of $S_5$, then the permutations of the edges they determine have the same cycle structure.

(To proof this, observe that the induced permutations are conjugate in $S_{15}$,

and hence have the same cycle structure.)

So you just have to compute $r$ for one element in each conjugacy class, which is mildly tedious at worst, and then apply Burnside.

- Suppose that $P(x)$ is a polynomial of degree $n$ such that $P(k)=\dfrac{k}{k+1}$ for $k=0,1,\ldots,n$. Find the value of $P(n+1)$
- Why are rotational matrices not commutative?
- Which is greater: $1000^{1000}$ or $1001^{999}$
- Question from Evans' PDE book
- Sentences in first order logic for graphs
- How to solve this Complex inequality system
- “belongs to” versus “contained in”
- Importance of Representation Theory
- How to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$?
- What does the topology on $\operatorname{Spec}(R)$ tells us about $R$?
- Integral of the Von karman equation
- Inclusion $O(2n)/U(n)\to GL(2n,\mathbb{R})/GL(n,\mathbb{C}) $
- Inverse of a symmetric tridiagonal matrix.
- Counting necklaces with a fixed number of each bead
- ELI5: Riemann-integrable vs Lebesgue-integrable