Kneser Graph

Author

Eric W. Weisstein
February 16, 2024

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

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

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

Special cases

The complete graph on n vertices is the Kneser graph K(n, 1).
The graph K(5, 2) is the Petersen Graph.
The Kneser graph K(2n − 1, n − 1) is known as the odd graph O(n).

RecognizeGraph[KneserGraph@@#]&/@{{2,1},{5,2},{7,1},{7,3}}

Table[{V[KneserGraph[n,k]],Binomial[n,k]},{k,6},{n,2k,6}]

Table[{Degrees[KneserGraph[n,k]][[1]],Binomial[n-k,k]},{k,6},{n,2k,6}]

Empty

Table[RecognizeGraph[KneserGraph[n,n-1]],{n,10}]

LadderRung

V/@Table[KneserGraph[2n,n],{n,6}]/2

FullSimplify[FunctionExpand@FindSequenceFunction[s,n],n∈Integers&&n>0]

Table[Binomial[2n,n],{n,6}]/2

FindGeneratingFunction[s,x]

RecognizeGraph[GraphUnion[#,Graph["P2"]]]&/@{1,3,10}

Table[RecognizeGraph[KneserGraph[2n,n]],{n,3}]

Graphic

kneser=SplitBy[Cases[Sort[{
Lookup[GraphData[#,"NotationRules"],"Kneser"],#}&/@GraphData["Kneser"]],{{_?(LessThan[8]),_},_}],#[[1,1]]&]

g=GraphicsGrid[Map[Show[StyleGraphs@GraphData[#[[2]]],PlotLabel->Column[{Row[{Style["K",Italic],StringReplace[ToString[#[[1]]],{"{"->"(","}"->")"}]}],TextCell[Style[GraphData[#[[2]],"Name"],Italic],TextAlignment->Center,PageWidth->100]},Alignment->Center],LabelStyle->Directive[Black,FontFamily->"Times"]]&,kneser,{2}],ImageSize->400,Alignment->Center,Dividers->All]

Kneser arrays

By Ed Pegg, Jr.
Dec. 8, 2007

Manipulate[With[{g=Subsets[Range[setsize],{choose}]},
Column[{Row[{setsize,"  ",choose,"  ",Length[g]}],ArrayPlot[Table[Length[Intersection[g[[a]],g[[b]]]],{a,Length[g]},{b,1,Length[g]}],PixelConstrained-> True,ImageSize-> Ceiling[200/Length[g]](Length[g]+10)]}]],{{setsize,11},3,13,1},{{choose,3},2,10,1}]

The following graphs are still unsolved.

Tooltip[GraphData[#],{#,GraphData[#,"VertexCount"]}]&/@{{"Kneser",{8,3}},{"Kneser",{9,3}},{"Kneser",{10,3}},{"Odd",5}}

Embeddings

<<MathWorld`Graphs`

GraphData["Kneser*"]

{"Kneser", {7, 2}}

Names

GraphData[{"Kneser",{7,2}},"StandardName"]

GraphData[{"Kneser",{7,2}},"StandardNames"]

Primary

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

All

GraphData[{"Kneser",{7,2}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Kneser",{7,2}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Kneser",{7,2}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Kneser",{7,2}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Kneser",{7,2}},"Graph","Degenerate"]

Perspective

GraphData[{"Kneser",{7,2}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Kneser",{7,2}},"Polyhedron"]

Bilateral

GraphData[{"Kneser",{7,2}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Kneser",{7,2}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Kneser",{7,2}},"Planar"]

GraphData[{"Kneser",{7,2}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Kneser",{7,2}},{"RCN","CN"}]

GraphData[{"Kneser",{7,2}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

(cn=CrossingNumber[GraphData[{"Kneser",{7,2}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Kneser",{7,2}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Kneser",{7,2}}],TimeConstraint->5 3600])//AbsoluteTiming

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Kneser",{7,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[{"Kneser",{7,2}},"Circulant"]

GraphData[{"Kneser",{7,2}},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"Kneser",{7,2}},"ComplementGraph","Name"]

GraphComplement/@GraphData[%,"Graph","All"]

Line graph

GraphData[{"Kneser",{7,2}},"Line"]

LineGraphQ[GraphData[{"Kneser",{7,2}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Kneser",{7,2}}&]

RootGraph[GraphData[{"Kneser",{7,2}}]]

Halin

GraphData[{"Kneser",{7,2}},"Halin"]

GraphData[{"Kneser",{7,2}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Kneser",{7,2}},"Rigid"]

GraphData[{"Kneser",{7,2}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Kneser",{7,2}},"Flexible"]

GraphData[{"Kneser",{7,2}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Kneser",{7,2}},"LCF"]

GraphData[{"Kneser",{7,2}},"HamiltonianCycleCount"]

GraphData[{"Kneser",{7,2}},"LCFSignature"]

GraphData[{"Kneser",{7,2}},"LCFNotations"]

GraphData[{"Kneser",{7,2}},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Kneser",{7,2}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Kneser",{7,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,1])]//Timing

Length[gs]

LCF compute 10^6

Tally[(lcf=LCF[GraphData[{"Kneser",{7,2}}],10^6])[[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]

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"Kneser",{7,2}}],10^7])[[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

LCF compute 5*^7

Tally[(lcf=LCF[GraphData[{"Kneser",{7,2}}],5*^7])[[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

nicelcf={{{{-10,-9,-6,-5,-2,6,8,9},{-9,-5,-3,2,3,5,7,9},{-8,-7,-6,-3,3,5,6,10}},7},{{{-9,-8,-4,-3,2,3,7,9},{-8,-7,-6,-3,3,4,6,8},{-9,-6,-4,-2,4,6,8,9}},7},{{{-10,-9,-8,-7,-4,2,7,9},{-6,-5,-3,2,3,5,8,9},{-9,-8,-5,-4,-2,3,6,9},{-9,-4,-2,3,4,5,9,10},{-9,-7,-5,-3,5,7,9,10},{-9,-7,-6,-3,3,4,7,9},{-10,-9,-5,-3,4,5,6,8}},3},{{{-10,-9,-8,-6,-3,4,5,9},{-7,-4,2,4,5,6,7,9},{-9,-6,-5,-3,2,8,9,10},{-9,-8,-5,-2,3,6,9,10},{-9,-5,-4,-2,3,4,5,10},{-10,-9,-7,-5,-4,5,7,9},{-10,-7,-5,-3,3,5,7,8}},3},{{{-10,-9,-8,-5,-3,4,5,8},{-8,-7,-5,-3,-2,2,7,10},{-10,-6,-5,2,3,5,8,9},{-8,-5,-2,3,5,6,9,10},{-10,-9,-5,-4,-2,3,5,10},{-9,-7,-5,-3,3,5,7,9},{-10,-7,-3,2,5,7,8,10}},3},{{{-10,-9,-8,-5,-2,3,5,6},{-9,-7,-5,-3,3,5,7,9},{-7,-6,-3,2,4,5,7,10},{-9,-6,-5,-3,2,5,6,9},{-7,-5,-3,-2,6,7,9,10},{-10,-9,-5,-2,2,3,5,9},{-9,-6,-5,-4,3,5,8,9}},3},{{{-10,-9,-8,-3,3,4,6,9},{-9,-7,-5,-3,3,5,7,9},{-10,-9,-7,-4,-3,7,8,9},{-9,-8,-6,-5,-3,2,5,8},{-9,-8,-5,-4,-3,3,6,10},{-7,-2,3,4,5,7,8,9},{-8,-6,-5,3,5,8,9,10}},3},{{{-10,-9,-7,-5,-4,-2,7,9},{-10,-7,-6,-4,-2,4,7,9},{-10,-9,-6,-3,5,6,8,9},{-9,-8,-6,-4,4,6,8,9},{-9,-8,-6,-5,4,6,8,10},{-9,-8,-6,-4,2,6,9,10},{-7,2,3,4,5,6,7,10}},3},{{{-10,-9,-7,-5,-3,3,7,8},{-9,-8,-6,-3,2,5,8,9},{-10,-8,-4,3,5,6,9,10},{-9,-7,-6,-4,-3,-2,2,7},{-9,-6,-5,3,6,8,9,10},{-10,-8,-3,-2,3,4,6,9},{-9,-7,-5,4,5,7,9,10}},3},{{{-10,-9,-7,-5,3,5,7,9},{-9,-7,-6,-4,-3,2,4,7},{-10,-9,-6,-3,4,5,6,9},{-7,-5,-3,-2,3,6,7,9},{-9,-6,-5,2,4,8,9,10},{-9,-8,-5,-4,3,5,6,9},{-9,-4,-3,-2,3,5,9,10}},3},{{{-10,-9,-7,-5,3,5,7,9},{-7,-6,-5,-3,4,5,7,10},{-9,-6,-3,2,5,6,8,9},{-8,-5,-4,-3,3,5,6,10},{-10,-9,-7,-2,2,7,8,10},{-8,-6,-5,-4,3,5,8,9},{-10,-8,-5,-3,-2,3,4,6}},3},{{{-10,-9,-6,-2,4,6,8,9},{-10,-8,-6,-4,5,6,8,9},{-9,-8,-6,-4,4,6,8,9},{-9,-8,-6,-5,3,6,9,10},{-9,-7,-4,2,4,6,7,10},{-9,-7,2,4,5,7,9,10},{-10,-7,-6,-5,-4,-3,-2,7}},3},{{{-10,-9,-5,-3,4,5,6,9},{-9,-5,-4,-3,2,3,9,10},{-9,-7,-6,3,4,5,7,9},{-9,-5,-4,-2,3,5,6,9},{-10,-9,-4,-3,3,4,9,10},{-9,-7,-5,-3,3,5,7,9},{-9,-7,-6,-4,-3,4,7,9}},3},{{{-10,-8,-5,-3,3,4,5,6},{-9,-7,-5,-3,5,7,9,10},{-7,-6,-4,-3,2,4,5,7},{-9,-6,-5,-3,5,6,8,9},{-10,-8,-4,-2,3,6,9,10},{-9,-7,-6,-5,3,4,5,7},{-9,-6,-5,-4,3,6,8,9}},3}};

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

gs

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Kneser",{7,2}}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Kneser",{7,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[{"Kneser",{7,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Kneser",{7,2}}],Debug->True]//Timing

GraphData[{"Kneser",{7,2}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Kneser",{7,2}},"Matchstick"]

GraphData[{"Kneser",{7,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Kneser",{7,2}},"Edges"]]

3D All

GraphData[{"Kneser",{7,2}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Kneser",{7,2}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Kneser",{7,2}},"Polyhedral"]

GraphData[{"Kneser",{7,2}},"Graph",{"3D","Polyhedron"}]

{"Kneser", {8, 2}}

Names

GraphData[{"Kneser",{8,2}},"StandardName"]

GraphData[{"Kneser",{8,2}},"StandardNames"]

Primary

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

All

GraphData[{"Kneser",{8,2}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Kneser",{8,2}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Kneser",{8,2}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Kneser",{8,2}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Kneser",{8,2}},"Graph","Degenerate"]

Perspective

GraphData[{"Kneser",{8,2}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Kneser",{8,2}},"Polyhedron"]

Bilateral

GraphData[{"Kneser",{8,2}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Kneser",{8,2}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Kneser",{8,2}},"Planar"]

GraphData[{"Kneser",{8,2}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Kneser",{8,2}},{"RCN","CN"}]

GraphData[{"Kneser",{8,2}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

(cn=CrossingNumber[GraphData[{"Kneser",{8,2}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Kneser",{8,2}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Kneser",{8,2}}],TimeConstraint->5 3600])//AbsoluteTiming

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Kneser",{8,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[{"Kneser",{8,2}},"Circulant"]

GraphData[{"Kneser",{8,2}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Kneser",{8,2}},"ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

GraphComplement/@compl

Line graph

GraphData[{"Kneser",{8,2}},"Line"]

LineGraphQ[GraphData[{"Kneser",{8,2}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Kneser",{8,2}}&]

RootGraph[GraphData[{"Kneser",{8,2}}]]

Halin

GraphData[{"Kneser",{8,2}},"Halin"]

GraphData[{"Kneser",{8,2}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Kneser",{8,2}},"Rigid"]

GraphData[{"Kneser",{8,2}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Kneser",{8,2}},"Flexible"]

GraphData[{"Kneser",{8,2}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Kneser",{8,2}},"LCF"]

GraphData[{"Kneser",{8,2}},"HamiltonianCycleCount"]

GraphData[{"Kneser",{8,2}},"LCFSignature"]

GraphData[{"Kneser",{8,2}},"LCFNotations"]

GraphData[{"Kneser",{8,2}},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Kneser",{8,2}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Kneser",{8,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[{"Kneser",{8,2}}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^7

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 5*^7

Tally[(lcf=LCF[GraphData[{"Kneser",{8,2}}],5*^7])[[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 all

Divisors[GraphData[{"Kneser",{8,2}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Kneser",{8,2}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Kneser",{8,2}}],All])[[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

UnitDistance

GraphData[{"Kneser",{8,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Kneser",{8,2}}],Debug->True]//Timing

GraphData[{"Kneser",{8,2}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Kneser",{8,2}},"Matchstick"]

GraphData[{"Kneser",{8,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Kneser",{8,2}},"Edges"]]

3D All

GraphData[{"Kneser",{8,2}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Kneser",{8,2}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Kneser",{8,2}},"Polyhedral"]

GraphData[{"Kneser",{8,2}},"Graph",{"3D","Polyhedron"}]

{"Kneser", {9, 2}}

Names

GraphData[{"Kneser",{9,2}},"StandardName"]

GraphData[{"Kneser",{9,2}},"StandardNames"]

Primary

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

All

GraphData[{"Kneser",{9,2}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Kneser",{9,2}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Kneser",{9,2}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Kneser",{9,2}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Kneser",{9,2}},"Graph","Degenerate"]

Perspective

GraphData[{"Kneser",{9,2}},"Graph","Perspective"]//StyleGraphs

Perspective construction

PolyhedronGraph[GraphData[{"Kneser",{9,2}},"Polyhedron"]]

Bilateral

GraphData[{"Kneser",{9,2}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Kneser",{9,2}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Kneser",{9,2}},"Planar"]

GraphData[{"Kneser",{9,2}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Kneser",{9,2}},{"RCN","CN"}]

GraphData[{"Kneser",{9,2}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Kneser",{9,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[{"Kneser",{9,2}},"Circulant"]

GraphData[{"Kneser",{9,2}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Kneser",{9,2}},"ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

gs=Delete[%,{2}]

Line graph

GraphData[{"Kneser",{9,2}},"Line"]

LineGraphQ[GraphData[{"Kneser",{9,2}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Kneser",{9,2}}&]

RootGraph[GraphData[{"Kneser",{9,2}}]]

Halin

GraphData[{"Kneser",{9,2}},"Halin"]

GraphData[{"Kneser",{9,2}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Kneser",{9,2}},"Rigid"]

GraphData[{"Kneser",{9,2}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Kneser",{9,2}},"Flexible"]

GraphData[{"Kneser",{9,2}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Kneser",{9,2}},"LCF"]

GraphData[{"Kneser",{9,2}},"HamiltonianCycleCount"]

GraphData[{"Kneser",{9,2}},"LCFSignature"]

GraphData[{"Kneser",{9,2}},"LCFNotations"]

GraphData[{"Kneser",{9,2}},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Kneser",{9,2}}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^6

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^7

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 5*^7

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

LCF compute all

Divisors[GraphData[{"Kneser",{9,2}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Kneser",{9,2}}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Kneser",{9,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[{"Kneser",{9,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Kneser",{9,2}}],Debug->True]//Timing

GraphData[{"Kneser",{9,2}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Kneser",{9,2}},"Matchstick"]

GraphData[{"Kneser",{9,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Kneser",{9,2}},"Edges"]]

3D All

GraphData[{"Kneser",{9,2}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Kneser",{9,2}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Kneser",{9,2}},"Polyhedral"]

GraphData[{"Kneser",{9,2}},"Graph",{"3D","Polyhedron"}]

{"Kneser", {10, 2}}

Names

GraphData[{"Kneser",{10,2}},"StandardName"]

GraphData[{"Kneser",{10,2}},"StandardNames"]

Primary

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

All

GraphData[{"Kneser",{10,2}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Kneser",{10,2}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Kneser",{10,2}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Kneser",{10,2}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Kneser",{10,2}},"Graph","Degenerate"]

Perspective

GraphData[{"Kneser",{10,2}},"Graph","Perspective"]//StyleGraphs

Perspective construction

PolyhedronGraph[GraphData[{"Kneser",{10,2}},"Polyhedron"]]

Bilateral

GraphData[{"Kneser",{10,2}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Kneser",{10,2}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Kneser",{10,2}},"Planar"]

GraphData[{"Kneser",{10,2}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Kneser",{10,2}},{"RCN","CN"}]

GraphData[{"Kneser",{10,2}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Kneser",{10,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[{"Kneser",{10,2}},"Circulant"]

GraphData[{"Kneser",{10,2}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Kneser",{10,2}},"ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Line graph

GraphData[{"Kneser",{10,2}},"Line"]

LineGraphQ[GraphData[{"Kneser",{10,2}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Kneser",{10,2}}&]

RootGraph[GraphData[{"Kneser",{10,2}}]]

Halin

GraphData[{"Kneser",{10,2}},"Halin"]

GraphData[{"Kneser",{10,2}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Kneser",{10,2}},"Rigid"]

GraphData[{"Kneser",{10,2}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Kneser",{10,2}},"Flexible"]

GraphData[{"Kneser",{10,2}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Kneser",{10,2}},"LCF"]

GraphData[{"Kneser",{10,2}},"HamiltonianCycleCount"]

GraphData[{"Kneser",{10,2}},"LCFSignature"]

GraphData[{"Kneser",{10,2}},"LCFNotations"]

GraphData[{"Kneser",{10,2}},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Kneser",{10,2}}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^6

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^7

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 2*^7

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

LCF compute all

Divisors[GraphData[{"Kneser",{10,2}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Kneser",{10,2}}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Kneser",{10,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[{"Kneser",{10,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Kneser",{10,2}}],Debug->True]//Timing

GraphData[{"Kneser",{10,2}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Kneser",{10,2}},"Matchstick"]

GraphData[{"Kneser",{10,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Kneser",{10,2}},"Edges"]]

3D All

GraphData[{"Kneser",{10,2}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Kneser",{10,2}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Kneser",{10,2}},"Polyhedral"]

GraphData[{"Kneser",{10,2}},"Graph",{"3D","Polyhedron"}]

GraphData

GraphDataClassString

GraphDataClassString["Kneser"]

Properties

VertexCount

DeleteCases[{#,GraphData[#,"VertexCount"],Binomial@@Lookup[GraphData[#,"NotationRules"],"Kneser"]}&/@GraphData["Kneser"],{_,x_,x_}]