Isomorphic Factorization

Author

Ed Pegg Jr
June 7, 2005

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/IsomorphicFactorization.nb

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/IsomorphicFactorization.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Initialization

edgeClebsch1 = {{{1,2}},{{1,5}},{{1,7}},{{1,8}},{{1,9}},{{2,3}},{{2,11}},{{2,14}},{{2,15}},{{3,4}},{{3,6}},{{3,9}},{{3,12}},{{4,7}},{{4,8}},{{4,10}},{{4,15}},{{5,6}},{{5,10}},{{5,12}},{{5,15}},{{6,7}},{{6,13}},{{6,14}},{{7,11}},{{7,16}},{{8,12}},{{8,13}},{{8,14}},{{9,10}},{{9,13}},{{9,16}},{{10,11}},{{10,14}},{{11,12}},{{11,13}},{{12,16}},{{13,15}},{{14,16}},{{15,16}}};
edgeClebsch2 = {{{1,11}},{{1,12}},{{1,13}},{{1,15}},{{1,16}},{{2,5}},{{2,6}},{{2,7}},{{2,12}},{{2,16}},{{3,7}},{{3,10}},{{3,11}},{{3,14}},{{3,16}},{{4,6}},{{4,9}},{{4,13}},{{4,14}},{{4,16}},{{5,8}},{{5,11}},{{5,13}},{{5,14}},{{6,10}},{{6,11}},{{6,15}},{{7,9}},{{7,13}},{{7,15}},{{8,9}},{{8,10}},{{8,15}},{{8,16}},{{9,11}},{{9,12}},{{10,12}},{{10,13}},{{12,14}},{{14,15}}};
edgeClebsch3 = {{{1,3}},{{1,4}},{{1,6}},{{1,10}},{{1,14}},{{2,4}},{{2,8}},{{2,9}},{{2,10}},{{2,13}},{{3,5}},{{3,8}},{{3,13}},{{3,15}},{{4,5}},{{4,11}},{{4,12}},{{5,7}},{{5,9}},{{5,16}},{{6,8}},{{6,9}},{{6,12}},{{6,16}},{{7,8}},{{7,10}},{{7,12}},{{7,14}},{{8,11}},{{9,14}},{{9,15}},{{10,15}},{{10,16}},{{11,14}},{{11,15}},{{11,16}},{{12,13}},{{12,15}},{{13,14}},{{13,16}}};

nodeClebsch = {{{204,-7720.0}},{{1104,-9538.25`}},{{2266,-14098.3`}},{{3792,-9734.25`}},{{4169,-5207.25`}},{{4273,-13795.3`}},{{4814,-7826.25`}},{{5289,-11297.3`}},{{5615,-9484.25`}},{{5615,-3781.25`}},{{6943,-8209.25`}},{{7237,-10354.3`}},{{8964,-14098.3`}},{{9232,-6786.25`}},{{9296,-12094.3`}},{{11034,-7720.0}}};

clebsch1= Graph[edgeClebsch1 ,nodeClebsch];
clebsch2= Graph[edgeClebsch2 ,nodeClebsch];
clebsch3= Graph[edgeClebsch3 ,nodeClebsch];

Definition

Isomorphic factorization entails dividing a given graph into n identical subgraphs. For instance, (Subscript[K, 16]) has the Clebsch graph as a factor.  This provides a
proof that Ramsey number R(3,3,3)>16.  That is, the complete graph on 16 points can be three-colored so that no triangle of a single color appears.

Testing

A check that all edges are covered, and various checks that all three are Clebsch graphs.

Sort[Flatten[{edgeClebsch1,edgeClebsch2,edgeClebsch3},2]] == Flatten[Table[{m,n},{m,1,15},{n,m+1,16}],1]

Through[{V,M}[clebsch1]]

StronglyRegularQ[clebsch1]

Flatten[RegularParameters[clebsch1]]

Spectrum[clebsch1]//SpectrumForm//TraditionalForm

MyIsomorphicQ[clebsch1,ClebschGraph]
MyIsomorphicQ[clebsch2,ClebschGraph]
MyIsomorphicQ[clebsch3,ClebschGraph]

Graphic

ShowGraphArray[{clebsch1,clebsch2,clebsch3},
VertexStyle->Disk[.025],AspectRatio->Automatic];