Arrangement Graph

Author

Eric W. Weisstein
November 14, 2023

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

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

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

Figure

gs=SortBy[{("Arrangement"/.GraphData[#,"NotationRules"]),#}&/@GraphData["Arrangement"],First]

nicegs=Select[gs,GraphData[#[[2]],"Embeddings"]=!={}&]

GraphicsGrid[Partition[GraphPlot[Graph[#[[2]]],Method->None,BaseStyle->Italic,PlotLabel->TextCell[Column[{Subscript["A",Style[Row[Riffle[#[[1]],","]],Plain]],GraphData[#[[2]],"Name"]},Alignment->Center]]]&/@nicegs,3,3,{1,1},{}],ImageSize->450]

Special cases

GetGraphData["TriangleGraph","File","8.1"]

(rec=Flatten[Table[{{n,k},RecognizeGraph[ArrangementGraph[n,k]]},{n,6},{k,n-1}],1])//Timing

Grid[DeleteCases[rec,{_,{}}],Dividers->All,Alignment->Left]

Cases[rec,{_,{}}][[All,1]]

n!/(n-k)! nodes

Flatten[Table[{{n,k},V[ArrangementGraph[n,k]],n!/(n-k)!},{n,6},{k,n-1}],1]//Column

Regular of Degree k(n-k)

Flatten[Table[{{n,k},Union[Degrees[ArrangementGraph[n,k]]],k(n-k)},{n,5},{k,n-1}],1]//Column

Diameter Floor[3k/2]

Flatten[Table[{{n,k},Diameter[ArrangementGraph[n,k]],Floor[3k/2]},{n,5},{k,n-1}],1]//Column

k(n-k)-Connected

Flatten[Table[{{n,k},VertexConnectivity[ArrangementGraph[n,k]],k(n-k)},{n,4},{k,n-1}],1]//Column

ET

Flatten[Table[{{n,k},EdgeTransitiveQ[ArrangementGraph[n,k]]},{n,5},{k,n-1}],1]

VT

Flatten[Table[{{n,k},VertexTransitiveQ[ArrangementGraph[n,k]]},{n,5},{k,n-1}],1]

Properties

IndependenceNumber

From Stan Wagon, Aug 8, 2018

Table 1.  Known results for the independence number of (Subscript[A, n+k,n]). Perfect strategies exist in all cases shown except the red entries, and perhaps the bold one.

Wagon: The 209 was a big surprise as that kills the conjecture that in all cases these are 1/3 of the vertex count.

TextGrid[
Sort[{
GraphData[#,"NotationRules","Arrangement"],
GraphData[#,"V"],
#,
GraphData[#,"α"]}&/@GraphData["Arrangement"]],Alignment->{{{Left},Decimal}},Dividers->All]

RootGraph

TextGrid[Sort@DeleteCases[{GraphData[#,"NotationRules","Arrangement"],#,GraphData[#,"RootGraph","Name"]}&/@GraphData["Arrangement"],_Missing],Dividers->All]

TextGrid[Table[{n,RecognizeGraph[RootGraph[ArrangementGraph[n,2]]]},{n,3,7}],Dividers->All]

Properties

VertexCount

DeleteCases[{#,GraphData[#,"V"],FactorialPower@@GraphData[#,"NotationRules","Arrangement"]}&/@GraphData["Arrangement"],{_,x_,x_}]

Embeddings

<<MathWorld`Graphs`

{"Arrangement", {5, 2}}

Names

GraphData[{"Arrangement",{5,2}},"StandardName"]

GraphData[{"Arrangement",{5,2}},"StandardNames"]

Primary

GraphData[{"Arrangement",{5,2}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Arrangement",{5,2}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Arrangement",{5,2}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Arrangement",{5,2}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Arrangement",{5,2}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Arrangement",{5,2}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Arrangement",{5,2}},"Graph","Degenerate"]

Perspective

GraphData[{"Arrangement",{5,2}},"Graph","Perspective"]//StyleGraphs

Perspective construction

PolyhedronGraph[GraphData[{"Arrangement",{5,2}},"Polyhedron"]]

Bilateral

GraphData[{"Arrangement",{5,2}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Arrangement",{5,2}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Arrangement",{5,2}},"Planar"]

GraphData[{"Arrangement",{5,2}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Arrangement",{5,2}},{"RCN","CN"}]

GraphData[{"Arrangement",{5,2}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Arrangement",{5,2}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Arrangement",{5,2}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Arrangement",{5,2}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

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

Table[MinimalCrossingGraph[GraphData[{"Arrangement",{5,2}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Arrangement",{5,2}},"Circulant"]

GraphData[{"Arrangement",{5,2}},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"Arrangement",{5,2}},"ComplementGraph","Name"]

Line graph

GraphData[{"Arrangement",{5,2}},"Line"]

LineGraphQ[GraphData[{"Arrangement",{5,2}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Arrangement",{5,2}}&]

RootGraph[GraphData[{"Arrangement",{5,2}}]]

LabelGraph@%

LineGraph/@GraphData[{"Crown",5},"Graph","All"]

RecognizeGraph/@%

gs={,,,,};

Halin

GraphData[{"Arrangement",{5,2}},"Halin"]

GraphData[{"Arrangement",{5,2}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Arrangement",{5,2}},"Rigid"]

GraphData[{"Arrangement",{5,2}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Arrangement",{5,2}},"Flexible"]

GraphData[{"Arrangement",{5,2}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Arrangement",{5,2}},"LCF"]

GraphData[{"Arrangement",{5,2}},"HamiltonianCycleCount"]

GraphData[{"Arrangement",{5,2}},"LCFSignature"]

GraphData[{"Arrangement",{5,2}},"LCFNotations"]

GraphData[{"Arrangement",{5,2}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute all

Divisors[GraphData[{"Arrangement",{5,2}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Arrangement",{5,2}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Arrangement",{5,2}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Arrangement",{5,2}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1|2}]

LCFGraph@@@DeleteCases[lcf,{_,1|2}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,3])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Arrangement",{5,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Arrangement",{5,2}}],Debug->True]//Timing

GraphData[{"Arrangement",{5,2}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Arrangement",{5,2}},"VertexList"],GraphData[{"Arrangement",{5,2}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Arrangement",{5,2}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

gs={RotateGraph[,{10,11}],RotateGraph[,{13,18}],RotateGraph[,{20,12}],RotateGraph[,{12,3}],RotateGraph[,{15,11}]}

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Arrangement",{5,2}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Arrangement",{5,2}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Arrangement",{5,2}},"Matchstick"]

GraphData[{"Arrangement",{5,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Arrangement",{5,2}},"Edges"]]

3D All

GraphData[{"Arrangement",{5,2}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Arrangement",{5,2}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Arrangement",{5,2}},"Polyhedral"]

GraphData[{"Arrangement",{5,2}},"Graph",{"3D","Polyhedron"}]

{"Arrangement", {6, 2}}

Names

GraphData[{"Arrangement",{6,2}},"StandardName"]

GraphData[{"Arrangement",{6,2}},"StandardNames"]

Primary

GraphData[{"Arrangement",{6,2}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Arrangement",{6,2}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Arrangement",{6,2}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Arrangement",{6,2}},"EdgeList"]]

Default embedding

g=Graph@GraphData[{"Arrangement",{6,2}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Arrangement",{6,2}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Arrangement",{6,2}},"Graph","Degenerate"]

Perspective

GraphData[{"Arrangement",{6,2}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Arrangement",{6,2}},"Polyhedron"]

Bilateral

GraphData[{"Arrangement",{6,2}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Arrangement",{6,2}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Arrangement",{6,2}},"Planar"]

GraphData[{"Arrangement",{6,2}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Arrangement",{6,2}},{"RCN","CN"}]

GraphData[{"Arrangement",{6,2}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Arrangement",{6,2}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Arrangement",{6,2}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Arrangement",{6,2}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

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

Table[MinimalCrossingGraph[GraphData[{"Arrangement",{6,2}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Arrangement",{6,2}},"Circulant"]

GraphData[{"Arrangement",{6,2}},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"Arrangement",{6,2}},"ComplementGraph","Name"]

Line graph

GraphData[{"Arrangement",{6,2}},"Line"]

LineGraphQ[GraphData[{"Arrangement",{6,2}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Arrangement",{6,2}}&]

RootGraph[GraphData[{"Arrangement",{6,2}}]]

LineGraph/@GraphData[{"Crown",6},"Graph","All"]

gs={,,,};

Halin

GraphData[{"Arrangement",{6,2}},"Halin"]

GraphData[{"Arrangement",{6,2}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Arrangement",{6,2}},"Rigid"]

GraphData[{"Arrangement",{6,2}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Arrangement",{6,2}},"Flexible"]

GraphData[{"Arrangement",{6,2}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Arrangement",{6,2}},"LCF"]

GraphData[{"Arrangement",{6,2}},"HamiltonianCycleCount"]

GraphData[{"Arrangement",{6,2}},"LCFSignature"]

GraphData[{"Arrangement",{6,2}},"LCFNotations"]

GraphData[{"Arrangement",{6,2}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Arrangement",{6,2}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Arrangement",{6,2}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 10^6

Tally[(lcf=LCF[GraphData[{"Arrangement",{6,2}}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,3,2])]//Timing

Length[gs]

gs

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"Arrangement",{6,2}}],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,3,2])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 5*^7

Tally[(lcf=LCF[GraphData[{"Arrangement",{6,2}}],5*^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,3,2])]//Timing

LCF compute all

Divisors[GraphData[{"Arrangement",{6,2}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Arrangement",{6,2}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Arrangement",{6,2}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Arrangement",{6,2}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

UnitDistance

GraphData[{"Arrangement",{6,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Arrangement",{6,2}}],Debug->True]//Timing

GraphData[{"Arrangement",{6,2}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Arrangement",{6,2}},"VertexList"],GraphData[{"Arrangement",{6,2}},"EdgeList"]],MaxIterations->500]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Arrangement",{6,2}},"Graph",#]&/@{"All","UnitDistance"})

gs={RotateGraph[,{19,28}],RotateGraph[,{26,5}]}

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Arrangement",{6,2}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Arrangement",{6,2}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Arrangement",{6,2}},"Matchstick"]

GraphData[{"Arrangement",{6,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Arrangement",{6,2}},"Edges"]]

3D All

GraphData[{"Arrangement",{6,2}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Arrangement",{6,2}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Arrangement",{6,2}},"Polyhedral"]

GraphData[{"Arrangement",{6,2}},"Graph",{"3D","Polyhedron"}]

GraphData

GraphDataClassString

GraphDataClassString["Arrangement"]

GraphDataString

file=OpenWrite["~/arrangement.m"]

Function[{n,k},WriteString[file,
GraphDataString[ArrangementGraph[n,k],
"StandardName"->{"Arrangement",{n,k}},
"Name"->"("<>ToString[n]<>","<>ToString[k]<>")-arrangement graph",
"Vertices"->None,
"Information"->"ArrangementGraph",
"Classes"->{"Arrangement"},
"NotationRules"->{"Arrangement"->{n,k}},
TimeConstraint->10,
Debug->True]]]@@@{{5,2},{5,3},{6,2},{6,3},{6,4}}

Close[file]