Bruhat Graph
Author
Eric W. Weisstein
Title
Bruhat Graph
Description
The (weak) Bruhat graph B_n of order n is the simple graph having have all permutations of {1,2,...,n} as vertices, and with an edge between pairs of permutations that differ by an adjacent transposition. The n-Bruhat graph is the Cayley graph of the symmetric group S_n generated by adjacent transpositions (Hurlburt 2011). The Bruhat graphs of orders 1 to 4 are illustrated above. The permutations and edges corresponding to B_4 are illustrated above. Special cases are summarized in the...
Category
Educational Materials
Keywords
URL
http://www.notebookarchive.org/2019-07-0z3ropl/
DOI
https://notebookarchive.org/2019-07-0z3ropl
Date Added
2019-07-02
Date Last Modified
2019-07-02
File Size
1.66 megabytes
Supplements
Rights
Redistribution rights reserved
Download
Open in Wolfram Cloud
Bruhat Graph
Bruhat Graph
Author
Author
Eric W. Weisstein
July 15, 2018
July 15, 2018
©2018 Wolfram Research, Inc. except for portions noted otherwise
Figure
Figure
Graphs.m
Graphs.m
In[]:=
GraphicsGrid[Partition[Table[Show[BruhatGraph[n]//StyleGraphs[#,VertexSize{"Scaled",.05}]&,PlotLabelStyle[HoldForm[n]n,FontFamily"Times"]],{n,6}],3],ImageSize400,DividersAll]
Out[]=
GraphData "Graph"
GraphData "Graph"
In[]:=
GraphicsGrid[Partition[Table[Show[GraphData[{"Bruhat",n}]//StyleGraphs[#,VertexSizeIf[n1,.01,{"Scaled",.05}]]&,PlotLabelStyle[HoldForm[n]n,FontFamily"Times"]],{n,6}],4],ImageSize400,DividersAll]
Out[]=
Special cases
Special cases
In[]:=
TextGrid[DeleteCases[Table[{n,rg=BruhatGraph[n]//RecognizeGraph},{n,6}],{_,{"Bruhat",_}}],DividersAll]
Out[]=
1 | SingletonGraph |
2 | {Path,2} |
3 | {Cycle,6} |
4 | TruncatedOctahedralGraph |
Source
Source
Construction
Construction
Properties
Properties
Acyclic
Acyclic
AdjacencyMatrixCount
AdjacencyMatrixCount
Anarboricity
Anarboricity
Arboricity
Arboricity
ArcTransitive
ArcTransitive
ArcTransitivity
ArcTransitivity
AutomorphismCount
AutomorphismCount
BalabanIndex
BalabanIndex
Bandwidth
Bandwidth
BridgeCount
BridgeCount
BurningNumber
BurningNumber
CharacteristicPolynomial
CharacteristicPolynomial
ChordCount
ChordCount
Chordless
Chordless
ChordlessCycleCount
ChordlessCycleCount
Chords
Chords
ChromaticInvariant
ChromaticInvariant
In[]:=
seq=Table[GraphData[{"Bruhat",n},"ChromaticInvariant"],{n,6}]
Out[]=
{1,1,1,23425,Missing[NotAvailable],Missing[NotAvailable]}
FindSequenceFunction[DeleteMissing@seq,n]
ChromaticNumber
ChromaticNumber
ChromaticPolynomial
ChromaticPolynomial
Circumference
Circumference
Classes
Classes
CliqueCount
CliqueCount
CliqueCoveringNumber
CliqueCoveringNumber
Probably A001710
In[]:=
seq=Table[GraphData[{"Bruhat",n},"CliqueCoveringNumber"],{n,6}]
Out[]=
{1,1,3,12,60,Missing[NotAvailable]}
In[]:=
Numerator[Range[6]!/2]
Out[]=
{1,1,3,12,60,360}
FullSimplify[FindSequenceFunction[DeleteMissing@seq,n],n>2]
Table[Ceiling[n/2],{n,6}]
CliquePolynomial
CliquePolynomial
CliqueNumber
CliqueNumber
ComplementOddChordlessCycleCount
ComplementOddChordlessCycleCount
ConnectedDominatingSetCount
ConnectedDominatingSetCount
ConnectedDominationNumber
ConnectedDominationNumber
ConnectedDominationPolynomial
ConnectedDominationPolynomial
ConnectedInducedSubgraphCount
ConnectedInducedSubgraphCount
ConnectedInducedSubgraphPolynomial
ConnectedInducedSubgraphPolynomial
CrossingNumber
CrossingNumber
CycleCount
CycleCount
CyclePolynomial
CyclePolynomial
Cyclic
Cyclic
CyclomaticNumber
CyclomaticNumber
DetourIndex
DetourIndex
DetourPolynomial
DetourPolynomial
Diameter
Diameter
DistancePolynomial
DistancePolynomial
DistinguishingNumber
DistinguishingNumber
DomaticNumber
DomaticNumber
DominationNumber
DominationNumber
DominationPolynomial
DominationPolynomial
DominatingSetCount
DominatingSetCount
EdgeChromaticNumber
EdgeChromaticNumber
EdgeConnectivity
EdgeConnectivity
EdgeCount
EdgeCount
EdgeCoverCount
EdgeCoverCount
In[]:=
seq=Table[GraphData[{"Bruhat",n},"EdgeCoverCount"],{n,6}]
Out[]=
{0,1,18,Missing[NotAvailable],Missing[NotAvailable],Missing[NotAvailable]}
In[]:=
FullSimplify[FindSequenceFunction[DeleteMissing@seq,n],n>0&&n∈Integers]
In[]:=
coef=FindLinearRecurrence[DeleteMissing@seq]
In[]:=
Length@coef
In[]:=
Take[seq,6]
In[]:=
LinearRecurrence[{11,-24,-21,33,34,8},{2,34,341,2902,23092,178393},20]
In[]:=
gf=xFindGeneratingFunction[DeleteMissing@seq,x]
In[]:=
FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>0&&n∈Integers]
In[]:=
CoefficientListSeries,{x,0,20},x
-2-12x-15-9-2
2
x
3
x
4
x
-1+11x-24-21+33+34+8
2
x
3
x
4
x
5
x
6
x
EdgeCoverNumber
EdgeCoverNumber
EdgeCoverPolynomial
EdgeCoverPolynomial
EulerianCycleCount
EulerianCycleCount
FaceCount
FaceCount
seq=Table[GraphData[{"Bruhat",n},"FaceCount"],{n,6}]
FindSequenceFunction[seq,n]
FlowPolynomial
FlowPolynomial
FractionalChromaticNumber
FractionalChromaticNumber
FractionalCliqueNumber
FractionalCliqueNumber
FractionalEdgeChromaticNumber
FractionalEdgeChromaticNumber
Girth
Girth
HamiltonDecompositionCount
HamiltonDecompositionCount
Hamiltonian
Hamiltonian
HamiltonianCycleCount
HamiltonianCycleCount
HamiltonianNumber
HamiltonianNumber
HamiltonianPathCount
HamiltonianPathCount
HamiltonianWalkCount
HamiltonianWalkCount
HararyIndex
HararyIndex
HexagonCount
HexagonCount
A317486
In[]:=
seq=Table[GraphData[{"Bruhat",n},"HexagonCount"],{n,6}]
Out[]=
{0,0,1,8,180,4080}
In[]:=
(seq=Table[CycleCount[BruhatGraph[n],6],{n,8}])//Timing
Out[]=
{12.7842,{0,0,1,8,180,4080,74760,1249920}}
In[]:=
(seq=Table[CycleCount[BruhatGraph[n],6],{n,9}])//Timing
(byblis V12.0.0 (2)) In[6]:=
Do[Print[{{"Bruhat",n},CycleCount[BruhatGraph[n],6]//Timing}],{n,10}]
{{Bruhat,1},{0.,0}}
{{Bruhat,2},{0.,0}}
{{Bruhat,3},{0.,1}}
{{Bruhat,4},{0.,8}}
{{Bruhat,5},{0.,180}}
{{Bruhat,6},{0.,4080}}
{{Bruhat,7},{0.,74760}}
{{Bruhat,8},{10.2344,1249920}}
{{Bruhat,9},{233.72,20381760}}
B10 takes 150+ GB
In[]:=
seq={0,0,1,8,180,4080,74760,1249920,20381760};
In[]:=
FindSequenceFunction[Drop[seq,2],n-2]
Out[]=
FindSequenceFunction[{1,8,180,4080,74760,1249920,20381760},-2+n]
In[]:=
FindLinearRecurrence[Drop[seq,2]]
Out[]=
FindLinearRecurrence[{1,8,180,4080,74760,1249920,20381760}]
In[]:=
FindGeneratingFunction[seq,x]
Out[]=
FindGeneratingFunction[{0,0,1,8,180,4080,74760,1249920,20381760},x]
IdiosyncraticPolynomial
IdiosyncraticPolynomial
(poly=Factor@Table[GraphData[{"Bruhat",n},"IdiosyncraticPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x,y])//Column
In[]:=
coef=Factor/@FindLinearRecurrence[poly]
ToPolynomialRecurrence[p,x,n,coef]
FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm
TeXForm[%]
LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]
FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]
gf=Factor[FindGeneratingFunction[poly,z]]
k0
z
FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]
Table[nx(3x+2)-2x^2+1,{n,10}]
FullSimplify[%-poly]
IndependenceNumber
IndependenceNumber
IndependencePolynomial
IndependencePolynomial
(poly=Factor@Table[GraphData[{"Bruhat",n},"IndependencePolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column
Out[]=
1+x |
1+2x |
(1+2x)(1+4x+ 2 x |
1+24x+240 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x |
Missing[NotAvailable] |
Missing[NotAvailable] |
In[]:=
CoefficientList[Take[poly,4],x]
Out[]=
{{1,1},{1,2},{1,6,9,2},{1,24,240,1304,4218,8400,10356,7824,3555,960,168,24,2}}
In[]:=
coef=Factor/@FindLinearRecurrence[poly]
In[]:=
ToPolynomialRecurrence[p,x,n,coef]
In[]:=
FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm
In[]:=
TeXForm[%]
In[]:=
LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]
In[]:=
Simplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]
In[]:=
gf=Factor[FindGeneratingFunction[poly,z]]
k0
z
In[]:=
soln=FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>2]
In[]:=
CoefficientListTable+,{n,10}//Expand,x//Column
-n
2
n
1-
1+4x
n
1+
1+4x
In[]:=
Table+,{n,10}//Expand
-n
2
n
1-
1+4x
n
1+
1+4x
In[]:=
TableLucasLn,1
n/2
x
x
,{n,10}//ExpandSubtract@@@Tablex(x+2)+LucasLn,1
n/2
x
x
,GraphData[{"Bruhat",n},"IndependencePolynomial"][x],{n,3,10}//ExpandIndependenceRatio
IndependenceRatio
seq=Table[GraphData[{"Bruhat",n},"IndependenceRatio"],{n,6}]
In[]:=
FullSimplify[FindSequenceFunction[Rest@seq,n-3],n>3&&n∈Integers]
Table[Floor[2n/3]/(2n),{n,6}]
IndependentEdgeSetCount
IndependentEdgeSetCount
seq=Table[GraphData[{"Bruhat",n},"IndependentEdgeSetCount"],{n,6}]
FindSequenceFunction[seq,n]
In[]:=
gf=FindGeneratingFunction[seq,x]
3
x
In[]:=
FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>2]
IndependentVertexSetCount
IndependentVertexSetCount
seq=Table[GraphData[{"Bruhat",n},"IndependentVertexSetCount"],{n,6}]
FindSequenceFunction[seq,n]//FullSimplify
In[]:=
gf=FindGeneratingFunction[seq,x]
3
x
In[]:=
FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>2]
Table[LucasL[n]+3,{n,6}]
IntersectionNumber
IntersectionNumber
seq=Table[GraphData[{"Bruhat",n},"IntersectionNumber"],{n,6}]
IrredundancePolynomial
IrredundancePolynomial
(poly=Factor@Table[GraphData[{"Bruhat",n},"IrredundancePolynomial"],{n,k0=4,20}]/.f_Functionf[x])//Column
In[]:=
coef=Factor/@FindLinearRecurrence[poly]
In[]:=
ToPolynomialRecurrence[p,x,n,coef]
In[]:=
FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm
In[]:=
TeXForm[%]
In[]:=
LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]
In[]:=
Simplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]
In[]:=
gf=Factor[FindGeneratingFunction[poly,z]]
k0
z
FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]
IrredundantSetCount
IrredundantSetCount
seq=Table[GraphData[{"Bruhat",n},"IrredundantSetCount"],{n,6}]
In[]:=
coef=FindLinearRecurrence[Rest@seq]
In[]:=
Length[coef]
In[]:=
Take[seq,1+{1,8}]
In[]:=
Join[{7},LinearRecurrence[{3,-2,-1,2,-2,0,2,-1},{22,29,39,60,94,151,241,400},20]]
FindSequenceFunction[DeleteMissing@seq,n]
In[]:=
FindSequenceFunction[Drop[seq,2],n-4]
In[]:=
gf=FindGeneratingFunction[DeleteMissing@seq,x]
3
x
CoefficientListSeries(1-x--+),{x,0,20},x
7+x-23+3+9-9+14+2-6
2
x
3
x
4
x
5
x
6
x
7
x
8
x
2
(-1+x)
2
x
4
x
6
x
In[]:=
Refine[SeriesCoefficient[gf,{x,0,n}],n>3]
In[]:=
terms=List@@res;
In[]:=
N[terms/.n0]//Chop
In[]:=
terms[[All,1]]
In[]:=
Expand[1+2(1+n)]
In[]:=
Table[3+2n+RootSum[1---+&,&],{n,40}]
2
#1
4
#1
5
#1
6
#1
n
#
Table[Piecewise[{{7,n3}},3+2n+RootSum[1---+&,&]],{n,6}]
2
#1
4
#1
5
#1
6
#1
n
#
KirchhoffIndex
KirchhoffIndex
seq=Table[GraphData[{"Bruhat",n},"KirchhoffIndex"],{n,6}]
(seq=Table[KirchhoffIndex@BruhatalGraph[n],{n,3,40}])//Timing
FindSequenceFunction[Drop[seq,3],n-5]//Head//Timing
In[]:=
FindLinearRecurrence[Drop[seq,3]]//Head//Timing
In[]:=
FindGeneratingFunction[seq,x]//Head//Timing
KirchhoffSumIndex
KirchhoffSumIndex
seq=Table[GraphData[{"Bruhat",n},"KirchhoffSumIndex"],{n,6}]
(seq=Table[KirchhoffSumIndex@BruhatalGraph[n],{n,3,40}])//Timing
In[]:=
FindSequenceFunction[Drop[seq,3],n-5]//Head//Timing
In[]:=
FindLinearRecurrence[Drop[seq,3]]//Head//Timing
In[]:=
FindGeneratingFunction[seq,x]//Head//Timing
LaplacianPolynomial
LaplacianPolynomial
(poly=Factor@Table[GraphData[{"Bruhat",n},"LaplacianPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column
In[]:=
coef=Factor/@FindLinearRecurrence[poly]
coef=Factor/@FindPolynomialRecurrence[poly,6]
ToPolynomialRecurrence[p,x,n,coef]
FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm
TeXForm[%]
LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]
FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]
gf=Factor[FindGeneratingFunction[poly,z]]
k0
z
FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]
Table[nx(3x+2)-2x^2+1,{n,10}]
FullSimplify[%-poly]
LeafCount
LeafCount
seq=Table[GraphData[{"Bruhat",n},"LeafCount"],{n,6}]
Likelihood
Likelihood
seq=Table[GraphData[{"Bruhat",n},"Likelihood"],{n,6}]
LongestCycleCount
LongestCycleCount
seq=Table[GraphData[{"Bruhat",n},"LongestCycleCount"],{n,6}]
LongestPathLength
LongestPathLength
seq=Table[GraphData[{"Bruhat",n},"LongestPathLength"],{n,6}]
LongestPathCount
LongestPathCount
seq=Table[GraphData[{"Bruhat",n},"LongestPathCount"],{n,6}]
LovaszNumber
LovaszNumber
seq=Table[GraphData[{"Bruhat",n},"LovaszNumber"],{n,6}]
MatchingGeneratingPolynomial
MatchingGeneratingPolynomial
Factor@(poly=Table[GraphData[{"Bruhat",n},"MatchingGeneratingPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column
In[]:=
CoefficientList[Take[poly,5],x]
In[]:=
coef=Factor/@FindLinearRecurrence[poly]
In[]:=
ToPolynomialRecurrence[p,x,n,coef]
In[]:=
FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm
In[]:=
TeXForm[%]
In[]:=
LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]
In[]:=
FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]
In[]:=
gf=Factor[FindGeneratingFunction[poly,z]]
k0
z
Simplify[SeriesCoefficient[gf,{z,0,n}],n>2]
In[]:=
Table-nx(2+7x)-++++,{n,5}//Factor
1
3/2
(1+4x)
-n
2
n
1-
1+4x
n
1+
1+4x
2
n
2
x
1+4x
n
1-
1+4x
n
1+
1+4x
3/2
(1+4x)
n
1-
1+4x
n
1+
1+4x
In[]:=
Table-nx(2+7x)-+++,{n,5}//Factor
1
3/2
(1+4x)
-n
2
n
1-
1+4x
n
1+
1+4x
3/2
(1+4x)
2
n
2
x
1+4x
n
1-
1+4x
n
1+
1+4x
MatchingNumber
MatchingNumber
seq=Table[GraphData[{"Bruhat",n},"MatchingNumber"],{n,6}]
FullSimplify[FindSequenceFunction[seq,n],n∈Integers]
MatchingPolynomial
MatchingPolynomial
(poly=Factor@Table[GraphData[{"Bruhat",n},"MatchingPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column
In[]:=
coef=Factor/@FindLinearRecurrence[poly]
In[]:=
ToPolynomialRecurrence[p,x,n,coef]
In[]:=
FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm
In[]:=
TeXForm[%]
In[]:=
LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]
In[]:=
FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]
In[]:=
gf=Factor[FindGeneratingFunction[poly,z]]
k0
z
SeriesCoefficient[gf,{z,0,n}]
MaximalCliqueCount
MaximalCliqueCount
seq=Table[GraphData[{"Bruhat",n},"MaximalCliqueCount"],{n,6}]
FindSequenceFunction[Rest@seq,n]
MaximalIndependencePolynomial
MaximalIndependencePolynomial
In[]:=
(poly=Table[GraphData[{"Bruhat",n},"MaximalIndependencePolynomial"],{n,6}]/.f_Functionf[x])//Column
Out[]=
x |
2x |
3 2 x 3 x |
117 8 x 9 x 10 x 12 x |
Missing[NotAvailable] |
Missing[NotAvailable] |
MaximalIndependentEdgeSetCount
MaximalIndependentEdgeSetCount
seq=Table[GraphData[{"Bruhat",n},"MaximalIndependentEdgeSetCount"],{n,6}]
(seq=Table[Length@FindAllMaximalIndependentEdgeSets[BruhatalGraph[n]],{n,3,35}])//Timing
In[]:=
coef=FindLinearRecurrence[seq]
In[]:=
Length[coef]
In[]:=
LinearRecurrence[coef,Take[seq,Length@coef],{-1,20}]//Take[#,13]&
In[]:=
seq=LinearRecurrence[{0,5,3,-10,-12,7,18,4,-11,-8,1,3,1},{2,4,12,14,40,56,112,178,306,482,792,1214,1924},40]
In[]:=
FindSequenceFunction[Drop[seq,2],n-4]//Head//Timing
In[]:=
gf=xFindGeneratingFunction[seq,x,ValidationLength5]
In[]:=
CoefficientListSeries-,{x,0,20},x
2(1+2x+-6-6+7+12--9-6+2+)
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
11
x
12
x
2
(-1+)
2
x
3
(-1++)
2
x
3
x
In[]:=
Refine[SeriesCoefficient[gf,{x,0,n}],n>0&&n∈Integers]
MaximalIndependentVertexSetCount
MaximalIndependentVertexSetCount
In[]:=
seq=Table[GraphData[{"Bruhat",n},"MaximalIndependentVertexSetCount"],{n,6}]
Out[]=
{1,2,5,363,Missing[NotAvailable],Missing[NotAvailable]}
FindSequenceFunction[seq,n]//FullSimpify
In[]:=
gf=FindGeneratingFunction[seq,x]
3
x
In[]:=
FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>2]
MaximalIrredundantSetCount
MaximalIrredundantSetCount
In[]:=
seq=Table[GraphData[{"Bruhat",n},"MaximalIrredundantSetCount"],{n,6}]
Out[]=
{1,2,11,16800,Missing[NotAvailable],Missing[NotAvailable]}
In[]:=
FindSequenceFunction[DeleteMissing@Drop[seq,2],n-4]//Head//Timing
In[]:=
FindLinearRecurrence[DeleteMissing@Drop[seq,2]]//Head//Timing
In[]:=
FindGeneratingFunction[seq,x,ValidationLength5]//Head//Timing
MaximumCliqueCount
MaximumCliqueCount
seq=Table[GraphData[{"Bruhat",n},"MaximumCliqueCount"],{n,6}]
FindSequenceFunction[Rest@seq,n]
MaximumIndependentEdgeSetCount
MaximumIndependentEdgeSetCount
seq=Table[GraphData[{"Bruhat",n},"MaximumIndependentEdgeSetCount"],{n,6}]
In[]:=
gf=FindGeneratingFunction[seq,x]
3
x
In[]:=
FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>2]
MaximumIndependentVertexSetCount
MaximumIndependentVertexSetCount
seq=Table[GraphData[{"Bruhat",n},"MaximumIndependentVertexSetCount"],{n,6}]
In[]:=
gf=FindGeneratingFunction[seq,x]
3
x
In[]:=
FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>2]
MaximumIrredundantSetCount
MaximumIrredundantSetCount
seq=Table[GraphData[{"Bruhat",n},"MaximumIrredundantSetCount"],{n,6}]
In[]:=
FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing
FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing
MaximumLeafNumber
MaximumLeafNumber
seq=Table[GraphData[{"Bruhat",n},"MaximumLeafNumber"],{n,6}]
In[]:=
FindSequenceFunction[DeleteMissing@Rest@seq,n-3]
MaximumVertexDegree
MaximumVertexDegree
seq=Table[GraphData[{"Bruhat",n},"MaximumVertexDegree"],{n,6}]
MeanDistance
MeanDistance
seq=Table[GraphData[{"Bruhat",n},"MeanDistance"],{n,6}]
FindSequenceFunction[seq,n]//Factor
MinimalDominatingSetCount
MinimalDominatingSetCount
seq=Table[GraphData[{"Bruhat",n},"MinimalDominatingSetCount"],{n,6}]
In[]:=
FindSequenceFunction[DeleteMissing@Rest@seq,n-3]
In[]:=
gf=FindGeneratingFunction[seq,x]
3
x
In[]:=
Refine[SeriesCoefficient[gf,{x,0,n}],n>3]
MinimalDominatingSetSignature
MinimalDominatingSetSignature
seq=Table[GraphData[{"Bruhat",n},"MinimalDominatingSetSignature"],{n,6}]//Column
FindSequenceFunction[DeleteMissing@seq,n]//Factor
MinimalEdgeCoverCount
MinimalEdgeCoverCount
seq=Table[GraphData[{"Bruhat",n},"MinimalEdgeCoverCount"],{n,6}]
In[]:=
seq={1,6,24,74,180,464,1113,2646,6360,15222,36795,89584,219635,542320,1346881,3361998,8427172,21195416,53455740,135112332,342093443,867325032,2201286622,5591469852,14211796995,36139507614,91934054637,233934039872,595393224041,1515602413390};
In[]:=
seq=Rest@CoefficientList[Series[x*(1+x)*(1+x-2*x^2-14*x^3-39*x^4+63*x^5+69*x^6+55*x^7-39*x^8-85*x^9-118*x^10-102*x^11-63*x^12-27*x^13-7*x^14-x^15)/((1-x^2-x^3)^3*(1-x-x^2-x^3)^2*(1-2*x-x^2-x^3)),{x,0,50}],x]
In[]:=
coef=FindLinearRecurrence[seq]
In[]:=
Length[coef]
In[]:=
Take[seq,18]
In[]:=
LinearRecurrence[{4,1,-12,-15,24,49,6,-73,-76,5,80,72,14,-30,-34,-19,-6,-1},{1,6,24,74,180,464,1113,2646,6360,15222,36795,89584,219635,542320,1346881,3361998,8427172,21195416},30]
FindSequenceFunction[seq,n]
In[]:=
gf=xFactor@FindGeneratingFunction[seq,x,ValidationLength5]
In[]:=
CoefficientListSeries-(-1+2x++),{x,0,20},x
(1+x)(-1-x+2+14+39-63-69-55+39+85+118+102+63+27+7+)
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
10
x
11
x
12
x
13
x
14
x
15
x
3
(-1++)
2
x
3
x
2
(-1+x++)
2
x
3
x
2
x
3
x
In[]:=
Series[gf,{x,0,20}]
In[]:=
res=Refine[SeriesCoefficient[gf,{x,0,n}],n>0&&n∈Integers]
MinimalTotalDominatingSetCount
MinimalTotalDominatingSetCount
seq=Table[GraphData[{"Bruhat",n},"MinimalTotalDominatingSetCount"],{n,6}]
seq={2,4,9,12,15,21,21,20,30,45,44,49,65,77,98,132,153,180,247,329,409,528,690,889,1180,157637,2657,3538,4684,6169,8164,10783,14229,18877,25036,33078,43757,57996,76809,101721,134773,178450,236284,313097,414828,549383};
In[]:=
coef=FindLinearRecurrence[seq]
In[]:=
Length[coef]
In[]:=
Take[seq,Length[coef]]
In[]:=
LinearRecurrence[{2,-1,1,-1,0,0,-1,0,1,1,-1},{2,4,9,12,15,21,21,20,30,45,44},20]
In[]:=
FindSequenceFunction[seq,n]
In[]:=
gf=xFindGeneratingFunction[seq,x,ValidationLength5]
In[]:=
CoefficientListSeries(1----++),{x,0,20},x
2+3-4-2-2-9-2+9+12-9
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
10
x
2
(-1+x)
3
x
4
x
5
x
6
x
8
x
9
x
In[]:=
FullSimplify[SeriesCoefficient[gf,{x,0,n}],n∈Integers&&n>0]
In[]:=
Table2n+RootSum[-1-#1+&,#^n&]+(1+)Root[1-#1+&,2]-+Root[1-#1+&,3]-,{n,20}//RootReduce
3
#1
n
(-1)
3
#1
2+n
2
Root[-1++&,1]
2
#1
3
#1
2+n
2
Root[-1++&,2]
2
#1
3
#1
3
#1
2+n
2
Root[-1++&,1]
2
#1
3
#1
2+n
2
Root[-1++&,3]
2
#1
3
#1
In[]:=
TableRoot[1-#1+&,2]-+Root[1-#1+&,3]-,{n,2,30,2}//RootReduce
3
#1
2+n
2
Root[-1++&,1]
2
#1
3
#1
2+n
2
Root[-1++&,2]
2
#1
3
#1
3
#1
2+n
2
Root[-1++&,1]
2
#1
3
#1
2+n
2
Root[-1++&,3]
2
#1
3
#1
In[]:=
Table[RootSum[-1-#+#^3&,&],{n,20}]
-n
#
In[]:=
Table[2n+RootSum[-1-#1+&,#^n&]+(1+)RootSum[-1-#+#^3&,&],{n,20}]
3
#1
n
(-1)
-n/2
#
MinimumCoveringsByMaximalCliquesCount
MinimumCoveringsByMaximalCliquesCount
seq=Table[GraphData[{"Bruhat",n},"MinimumCoveringsByMaximalCliquesCount"],{n,6}]
In[]:=
seq={1,4,30,12,98,28,270,60,682,124,1638,252,3810,508,8670,1020,19418,2044,42966,4092,94162,8188,204750,16380,442314,32764,950214,65532,2031554,131068,4325310,262140,9174970,524284,19398582,1048572,40894386,2097148,85983150};
In[]:=
Join[{1},Table[If[Mod[n,2]0,2,n](2^Ceiling[n/2]-2),{n,4,20}]]
Table[Piecewise[{{1,n3},{2(2^Ceiling[n/2]-2),Mod[n,2]0},{(2^Ceiling[n/2]-2)n,Mod[n,2]1}}],{n,6}]
In[]:=
FindSequenceFunction[DeleteMissing@Drop[seq,1],n-3]//Head//Timing
In[]:=
coef=FindLinearRecurrence[DeleteMissing@Drop[seq,1]]
In[]:=
Length@coef
In[]:=
Take[seq,1+{1,8}]
In[]:=
Join[{1},LinearRecurrence[{0,6,0,-13,0,12,0,-4},{4,30,12,98,28,270,60,682},20]]
In[]:=
gf=FindGeneratingFunction[seq,x]
3
x
In[]:=
CoefficientListSeries,{x,0,20},x
1+4x+24-12-69+8+60-20
2
x
3
x
4
x
5
x
6
x
8
x
2
(1-3+2)
2
x
4
x
In[]:=
FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>3&&n∈Integers]
MinimumConnectedDominatingSetCount
MinimumConnectedDominatingSetCount
seq=Table[GraphData[{"Bruhat",n},"MinimumConnectedDominatingSetCount"],{n,6}]
In[]:=
FindSequenceFunction[DeleteMissing@Drop[seq,2],n-4]//FullSimplify
MinimumDistinguishingLabelingCount
MinimumDistinguishingLabelingCount
seq=Table[GraphData[{"Bruhat",n},"MinimumDistinguishingLabelingCount"],{n,6}]
FindSequenceFunction[DeleteMissing@seq,n]
FindGeneratingFunction[DeleteCases[seq,_Missing],x]
MinimumDominatingSetCount
MinimumDominatingSetCount
seq=Table[GraphData[{"Bruhat",n},"MinimumDominatingSetCount"],{n,6}]
In[]:=
FindSequenceFunction[DeleteMissing@Drop[seq,4],n-6]//Factor
MinimumEdgeCoverCount
MinimumEdgeCoverCount
seq=Table[GraphData[{"Bruhat",n},"MinimumEdgeCoverCount"],{n,6}]
In[]:=
seq={1,2,21,8,85,18,217,32,441,50,781,72,1261,98,1905,128,2737,162,3781,200,5061,242,6601,288,8425,338,10557,392,13021,450,15841,512,19041,578,22645,648,26677,722,31161,800,36121,882,41581,968,47565,1058,54097,1152};
In[]:=
FullSimplify[FindSequenceFunction[seq,n],n∈Integers]
In[]:=
coef=FindLinearRecurrence[seq]
In[]:=
Length[coef]
In[]:=
Take[seq,8]
In[]:=
LinearRecurrence[{0,4,0,-6,0,4,0,-1},{1,2,21,8,85,18,217,32},20]
In[]:=
Table[Floor[(n+3)/2],{n,20}]
In[]:=
gf=xFindGeneratingFunction[seq,x]
In[]:=
CoefficientListSeries,{x,0,20},x
1+2x+17+7-2-
2
x
4
x
5
x
6
x
4
(-1+)
2
x
In[]:=
Refine[SeriesCoefficient[gf,{x,0,n}],n>0]
In[]:=
Tablen(+3n-1-(+n-1))4,{n,20}
2
n
n
(-1)
2
n
MinimumTotalDominatingSetCount
MinimumTotalDominatingSetCount
seq=Table[GraphData[{"Bruhat",n},"MinimumTotalDominatingSetCount"],{n,6}]
In[]:=
FindSequenceFunction[DeleteMissing@Drop[seq,2],n-4]
MinimumVertexCoverCount
MinimumVertexCoverCount
seq=Table[GraphData[{"Bruhat",n},"MinimumVertexCoverCount"],{n,6}]
MinimumVertexDegree
MinimumVertexDegree
seq=Table[GraphData[{"Bruhat",n},"MinimumVertexDegree"],{n,6}]
MolecularTopologicalIndex
MolecularTopologicalIndex
seq=Table[GraphData[{"Bruhat",n},"MolecularTopologicalIndex"],{n,6}]
FindLinearRecurrence[seq
FindSequenceFunction[seq,n]//Factor
Nonhamiltonian
Nonhamiltonian
Table[GraphData[{"Bruhat",n},"Nonhamiltonian"],{n,6}]
OddChordlessCycleCount
OddChordlessCycleCount
seq=Table[GraphData[{"Bruhat",n},"OddChordlessCycleCount"],{n,6}]
PathCount
PathCount
seq=Table[GraphData[{"Bruhat",n},"PathCount"],{n,6}]
FindSequenceFunction[DeleteMissing@seq,n]//Factor
PathPolynomial
PathPolynomial
(poly=Factor[Table[GraphData[{"Bruhat",n},"PathPolynomial"],{n,k0=1,kmax=6}]/.f_Function:>f[x]])//Column
In[]:=
coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]
In[]:=
ToPolynomialRecurrence[p,x,n,coef]
In[]:=
FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm
In[]:=
TeXForm[%]
In[]:=
LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]
In[]:=
FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]
In[]:=
gf=Factor[FindGeneratingFunction[poly,z]]
k0
z
FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]
poly2=Table[XXX,{n,k0,kmax}]
FullSimplify[poly2-poly]
PentagonCount
PentagonCount
Planar
Planar
ProjectivePlaneCrossingNumber
ProjectivePlaneCrossingNumber
Radius
Radius
seq=Table[GraphData[{"Bruhat",n},"Radius"],{n,6}]
RankPolynomial
RankPolynomial
(poly=Factor@Table[GraphData[{"Bruhat",n},"RankPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x,y])
In[]:=
coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]
In[]:=
ToPolynomialRecurrence[p,x,n,coef]
In[]:=
FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm
In[]:=
TeXForm[%]
In[]:=
LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]
In[]:=
Simplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]
gf=Factor[FindGeneratingFunction[poly,z]]
k0
z
SeriesCoefficient[gf,{z,0,n}]
RectilinearCrossingNumber
RectilinearCrossingNumber
seq=Table[GraphData[{"Bruhat",n},"RectilinearCrossingNumber"],{n,6}]
ReliabilityPolynomial
ReliabilityPolynomial
(poly=Factor@Table[GraphData[{"Bruhat",n},"ReliabilityPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column
In[]:=
coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]
In[]:=
ToPolynomialRecurrence[p,x,n,coef]
In[]:=
FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm
In[]:=
TeXForm[%]
In[]:=
LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]
In[]:=
FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]
gf=Factor[FindGeneratingFunction[poly,z]]
k0
z
FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]
FullSimplify[poly2-poly]
ShannonCapacity
ShannonCapacity
seq=Table[GraphData[{"Bruhat",n},"ShannonCapacity"],{n,6}]
SigmaPolynomial
SigmaPolynomial
(poly=Factor@Table[GraphData[{"Bruhat",n},"SigmaPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column
In[]:=
coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]
ToPolynomialRecurrence[p,x,n,coef]
FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm
TeXForm[%]
LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]
FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]
gf=Factor[FindGeneratingFunction[poly,z]]
k0
z
FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]
Table[nx(3x+2)-2x^2+1,{n,10}]
FullSimplify[%-poly]
Skewness
Skewness
In[]:=
seq=Table[GraphData[{"Bruhat",n},"Skewness"],{n,6}]
Out[]=
{0,0,0,0,Missing[NotAvailable],Missing[NotAvailable]}
SpanningTreeCount
SpanningTreeCount
In[]:=
seq=Table[GraphData[{"Bruhat",n},"SpanningTreeCount"],{n,6}]
Out[]=
{1,1,6,101154816,6187732257761496793412385090375984958331031826464768000000000,661322621260224478395580578853802157067062232148970154277503585961146895143739668354666554145545186620685910518861588701422963711087956658474255192782768385120008789550434872252444278005559966119624304663758766389241298373283197496175027119966896341456806269054506582809609936732561518529850752981301314269634973848884587024447409009012994198155814818300524751367239380759737575625823149582788553237004392857600000000000000000000000000000000000000000000000}
In[]:=
FindSequenceFunction[seq,n]//FullSimplify
Out[]=
FindSequenceFunction[{1,1,6,101154816,6187732257761496793412385090375984958331031826464768000000000,661322621260224478395580578853802157067062232148970154277503585961146895143739668354666554145545186620685910518861588701422963711087956658474255192782768385120008789550434872252444278005559966119624304663758766389241298373283197496175027119966896341456806269054506582809609936732561518529850752981301314269634973848884587024447409009012994198155814818300524751367239380759737575625823149582788553237004392857600000000000000000000000000000000000000000000000},n]
SquareCount
SquareCount
StabilityIndex
StabilityIndex
TopologicalIndex
TopologicalIndex
ToroidalCrossingNumber
ToroidalCrossingNumber
seq=Table[GraphData[{"Bruhat",n},"ToroidalCrossingNumber"],{n,6}]
TotalDominatingSetCount
TotalDominatingSetCount
seq=Table[GraphData[{"Bruhat",n},"TotalDominatingSetCount"],{n,6}]
FullSimplify[FindSequenceFunction[DeleteMissing@seq,n],n∈Integers]
TotalDominationNumber
TotalDominationNumber
seq=Table[GraphData[{"Bruhat",n},"TotalDominationNumber"],{n,6}]
TotalDominationPolynomial
TotalDominationPolynomial
(poly=Factor@Table[GraphData[{"Bruhat",n},"TotalDominationPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column
In[]:=
coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]
In[]:=
ToPolynomialRecurrence[p,x,n,coef]
In[]:=
FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm
In[]:=
TeXForm[%]
In[]:=
LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]
In[]:=
FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]
In[]:=
gf=Factor[FindGeneratingFunction[poly,z]]
k0
z
FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]
Traceable
Traceable
Table[GraphData[{"Bruhat",n},"Traceable"],{n,6}]
Triameter
Triameter
In[]:=
seq=Table[GraphData[{"Bruhat",n},"Triameter"],{n,6}]
Out[]=
{Missing[NotApplicable],Missing[NotApplicable],6,12,20,Missing[NotAvailable]}
FindSequenceFunction[DeleteMissing@seq,n]
TriangleCount
TriangleCount
TuttePolynomial
TuttePolynomial
(poly=Factor@Table[GraphData[{"Bruhat",n},"TuttePolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x,y])//Column
In[]:=
coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]
In[]:=
ToPolynomialRecurrence[p,x,n,coef]
In[]:=
FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm
In[]:=
TeXForm[%]
In[]:=
LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]
In[]:=
Refine[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]
gf=Factor[FindGeneratingFunction[poly,z]]
k0
z
FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]
FullSimplify[poly2-poly]
Untraceable
Untraceable
Table[GraphData[{"Bruhat",n},"Untraceable"],{n,6}]
VertexConnectivity
VertexConnectivity
Table[GraphData[{"Bruhat",n},"VertexConnectivity"],{n,6}]
VertexCoverCount
VertexCoverCount
In[]:=
seq=Table[GraphData[{"Bruhat",n},"VertexCoverCount"],{n,6}]
Out[]=
{2,3,18,37076,Missing[NotAvailable],Missing[NotAvailable]}
FindSequenceFunction[seq,n]
VertexCoverNumber
VertexCoverNumber
seq=Table[GraphData[{"Bruhat",n},"VertexCoverNumber"],{n,6}]
FindSequenceFunction[seq,n]//FullSimplify
In[]:=
gf=FindGeneratingFunction[seq,x]
3
x
In[]:=
FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>3]
VertexCount
VertexCount
VertexCoverPolynomial
VertexCoverPolynomial
(poly=Factor@Table[GraphData[{"Bruhat",n},"VertexCoverPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column
Out[]=
1+x |
x(2+x) |
3 x 2 x |
12 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x |
Missing[NotAvailable] |
Missing[NotAvailable] |
In[]:=
coef=Factor/@FindLinearRecurrence[poly]
In[]:=
ToPolynomialRecurrence[p,x,n,coef]
In[]:=
FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm
In[]:=
TeXForm[%]
In[]:=
LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]
In[]:=
FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]
gf=Factor[FindGeneratingFunction[poly,z]]
k0
z
SeriesCoefficient[gf,{z,0,n}]
poly2=Table[LinearRecurrence[{x^2,2x^3,x^4},{x^2,x^3(4+x),x^4(3+6x+x^2)},{n}][[1]],{n,k0,20}]
FullSimplify[poly2-poly]
VertexDegrees
VertexDegrees
seq=Table[GraphData[{"Bruhat",n},"VertexDegrees"],{n,3,10}]
WienerIndex
WienerIndex
seq=Table[GraphData[{"Bruhat",n},"WienerIndex"],{n,6}]
FindSequenceFunction[seq,n]//Factor
WienerSumIndex
WienerSumIndex
seq=Table[GraphData[{"Bruhat",n},"WienerSumIndex"],{n,6}]
(seq=Table[WienerSumIndex@BruhatalGraph[n],{n,3,40}])//Timing
In[]:=
FindSequenceFunction[Drop[seq,3],n-5]//Head//Timing
In[]:=
FindLinearRecurrence[Drop[seq,3]]//Head//Timing
In[]:=
FindGeneratingFunction[seq,x]//Head//Timing
GraphData
GraphData
Cite this as: Eric W. Weisstein, "Bruhat Graph" from the Notebook Archive (2018), https://notebookarchive.org/2019-07-0z3ropl
Download
