Truncated Witt Graph

Author

Eric W. Weisstein
October 25, 2022

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

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

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

Embeddings

GraphData["TruncatedWittGraph","StandardName"]

Primary

GraphData["TruncatedWittGraph"]//StyleGraphs[#,ImageSize->Small]&

All

GraphData["TruncatedWittGraph","Graph","All"]//StyleGraphs

Default embedding

GraphPlot@GraphData["TruncatedWittGraph","Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Embedding types

GraphDataEmbeddings[GraphData["TruncatedWittGraph","EdgeList"]]

Degenerate

GraphData["TruncatedWittGraph","Graph","Degenerate"]//StyleGraphs

Circular

GraphData["TruncatedWittGraph","Graph","Circular"]//StyleGraphs

Planar

GraphData["TruncatedWittGraph","Planar"]

GraphData["TruncatedWittGraph","Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData["TruncatedWittGraph",{"RCN","CN"}]

GraphData["TruncatedWittGraph","Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData["TruncatedWittGraph"],TimeConstraint->10])//AbsoluteTiming

CrossingNumber[GraphData["TruncatedWittGraph"],TimeConstraint->60]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData["TruncatedWittGraph"],"CrossingNumber"->cn]]

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData["TruncatedWittGraph"],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData["TruncatedWittGraph","V"]&]]//Timing

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["TruncatedWittGraph","Circulant"]

GraphData["TruncatedWittGraph","Graph","Circulant"]//StyleGraphs

Halin

GraphData["TruncatedWittGraph","Halin"]

GraphData["TruncatedWittGraph","Graph","Halin"]//StyleGraphs

LCF

GraphData["TruncatedWittGraph","LCF"]

GraphData["TruncatedWittGraph","LCFSignature"]

GraphData["TruncatedWittGraph","Graph","LCF"]//StyleGraphs

LCF compute

Length[FindHamiltonianCycle[GraphData["TruncatedWittGraph"],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData["TruncatedWittGraph"],All])[[All,2]]]

gs=LCFGraph@@@DeleteCases[lcf,{_,1|2}]

UnitDistance

GraphData["TruncatedWittGraph","UnitDistance"]

UnitDistanceGraphQ[GraphData["TruncatedWittGraph"],Debug->True]//Timing

GraphData["TruncatedWittGraph","Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement

UnitDistanceEmbeddingRefine/@GraphData["TruncatedWittGraph","Graph","All"]//Timing

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistanceEmbeddingRefine/@Complement@@(GraphData["TruncatedWittGraph","Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData["TruncatedWittGraph"],MaxIterations->1000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData["TruncatedWittGraph"],MaxIterations->1000,"ReturnWithMessage"->False]//Quiet//Timing

FindUnitDistanceEmbedding[GraphData["TruncatedWittGraph"],MaxIterations->50000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{"TruncatedWittGraph",l=FindSubgraphUnitDistanceEmbedding[GraphData["TruncatedWittGraph"],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData["TruncatedWittGraph","Matchstick"]

GraphData["TruncatedWittGraph","Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData["TruncatedWittGraph","Edges"]]

3D All

GraphData["TruncatedWittGraph","Graph",{"3D","All"}]

3D UnitDistance

GraphData["TruncatedWittGraph","Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData["TruncatedWittGraph","Polyhedral"]

GraphData["TruncatedWittGraph","Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData["TruncatedWittGraph","Polyhedron"]}]

Construction

Witt Design

Brouwer et al., p. 367

The truncated Witt graph on 506 points is constructed by removing all vectors of the large Witt design containing an arbitrarily chosen symbol. This produces a \href{distance-regular graph} with intersection array {15, 14, 12; 1, 1, 9}.

Should have |M23| = 10200960

Tally[Length/@WittDesign]

Length[t=Select[WittDesign,Length[#]==15&]]

Flatten[Outer[Length[Intersection[#1,#2]]&,t,t,1]]//Union

7

g1=MakeGraph[t,(!UnsameQ[Length[Intersection[#1,#2]],7]&),Type->Undirected]

RecognizeGraph[g1]

Tally[Flatten[GraphDistanceMatrix[g1]]]

FastAutomorphismCount[g1]

c1=Tally[spec=Round[Eigenvalues[N[ToAdjacencyMatrix[g1]]]]]

char=Evaluate[Times@@((x-#[[1]])^#[[2]]&/@c1)/.x->#]&

spec//SpectrumForm//TraditionalForm

That's the one!

9

g2=MakeGraph[t,(!UnsameQ[Length[Intersection[#1,#2]],9]&),Type->Undirected]

Tally[Round[Eigenvalues[N[ToAdjacencyMatrix[g2]]]]]

FastAutomorphismCount[g2]

11

g3=MakeGraph[t,(!UnsameQ[Length[Intersection[#1,#2]],11]&),Type->Undirected]

Tally[Round[Eigenvalues[N[ToAdjacencyMatrix[g3]]]]]

FastAutomorphismCount[g3]

Extended Golay Code

Golay Code

Andries E. Brouwer
Mon, 8 Jun 2009 13:18:58 +0200

The large Witt graph has as vertices the 759 words of weight 8 in extended binary Golay. Call the octads, and view them as sets of size 8.  Pick one coordinate position. 253 octads have a 1 there, 506 octads have a 0 there.  I conjecture that your IofinovaIvanovGraph506 is the same as what I describe in [BCN] 11.4.2 - it is the induced subgraph on 506 vertices from the 759.

Length[w8=Select[ExtendedBinaryGolayCode,Total[#]==8&]]

(z=Flatten[Position[w8[[All,1]],0]])//Length

(LargeWitt=MakeGraph[w8,#1.#2==0&,Type->Undirected])

InduceSubgraph[LargeWitt,z]

RecognizeGraph[%]

GraphData["TruncatedWittGraph","Degrees"]//Union

distanceregular.org

g=DistanceRegularGraph["http://www.distanceregular.org/graphdata/truncwitt.am"]

RecognizeGraph[g]

VertexCount[g]

GraphDiameter[g]//Timing

RegularParameters[g]//Timing

DistanceRegularGraphQ[g]//Timing

IntersectionArray[g]//Timing

IntegerSpectrum[g]//SpectrumForm

GroupOrder[GraphAutomorphismGroup[g]]

HamiltonianGraphQ[g]

GraphData

GraphClassString

GraphClassString["TruncatedWittGraph"]

GraphDataString

file=OpenWrite["truncwitt.m"]

WriteString[file,GraphDataString[g1,
"StandardName"->"TruncatedWittGraph",
"AlternateStandardName"->"truncated Witt graph",
"CharacteristicPolynomial"->char,
"Information"->"TruncatedWittGraph",
"Classes"->{"DeterminedBySpectrum"},
Debug->True,
TimeConstraint->60
]]