Lovász Number

Author

Eric W. Weisstein
March 20, 2023

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

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

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

GraphDataCountTable

GraphDataCountTable["LovaszNumber",{"AlternatingGroupGraph"->001715,"Antelope"->286069,"Bruhat"->001710,"FibonacciCube"->173173,{"Grid",2}->000982,{"Grid",3}->036486,"Hanoi"->000244,"King"->008794,"Knight"->030978,"MengerSponge"->307691,"SierpinskiCarpet"->013731,"SierpinskiGasket"->067771,"SierpinskiTetrahedron"->283070,"Spoke"->031940,"StackedBook"->128223,"TriangularHoneycombAcuteKnight"->287195}]

Parametrized families

<<MathWorld`Graphs`

Alkane

seq=Table[GraphData[{"Alkane",n},"LovaszNumber"],{n,10}]

FindSequenceFunction[seq,n]

AlternatingGroupGraph

A001715

seq=Table[GraphData[{"AlternatingGroupGraph",n},"LovaszNumber"],{n,2,6}]

FindSequenceFunction[seq,n-1]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"LovaszNumber"],{n,10}]

Do[Print[{gn=GraphData[{"Andrasfai",n}, "#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,10}]

Antelope n×n

A286069

== IndependenceNumber

seq=Table[GraphData[{"Antelope",{n,n}},"LovaszNumber"],{n,15}]

Antiprism

Entity["Graph",{"Antiprism",n}]["LovaszNumber"]

(seq=Table[GraphData[{"Antiprism",n},"LovaszNumber"],{n,3,25}])//Column

Do[Print[{gn=GraphData[{"Antiprism",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,3,25}]

Do[Print[{gn=GraphData[{"Antiprism",n},"#"],InputForm@LovaszNumber[GraphData[gn],Tolerance->1.*^-15]//AbsoluteTiming}],{n,3,25}]

InputForm@LovaszNumber[GraphData[{"Antiprism",7}],Tolerance->1.*^-15]

r=ToAlgebraicRoot[SetPrecision[x=4.505530797860137,13],"MaxDegree"->3]

Abs[r-x]

r=ToAlgebraicRoot[SetPrecision[x=4.505530797860137,15],"MaxDegree"->3]

Abs[r-x]

Apollonian

A000244

seq=Table[GraphData[{"Apollonian",n},"LovaszNumber"],{n,5}]

FindSequenceFunction[seq,n]

Barbell

seq=Table[GraphData[{"Barbell",n},"LovaszNumber"],{n,3,20}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"LovaszNumber"],{n,10}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"LovaszNumber"],{n,10}]

Book

seq=Table[GraphData[{"Book",n},"LovaszNumber"],{n,20}]

FindSequenceFunction[seq,n]

Bruhat

A001710

seq=Table[GraphData[{"Bruhat",n},"LovaszNumber"],{n,6}]

FindSequenceFunction[seq,n]

Camel n×n

== IndependenceNumber

seq=Table[GraphData[{"Camel",{n,n}},"LovaszNumber"],{n,10}]

Table[GraphData[{"Camel",{n,n}},"IndependenceNumber"],{n,10}]

Centipede

seq=Table[GraphData[{"Centipede",n},"LovaszNumber"],{n,10}]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"LovaszNumber"],{n,20}]

Complete

Entity["Graph",{"Complete",n}]["LovaszNumber"]

seq=Table[GraphData[{"Complete",n},"LovaszNumber"],{n,30}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["LovaszNumber"]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["LovaszNumber"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"LovaszNumber"],{n,20}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["LovaszNumber"]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["LovaszNumber"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"LovaszNumber"],{n,10}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"LovaszNumber"],{n,2,10}]

FindSequenceFunction[seq,n-1]//Factor

Crown

seq=Table[GraphData[{"Crown",n},"LovaszNumber"],{n,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["LovaszNumber"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"LovaszNumber"],{n,3,8}]

Do[Print[{gn=GraphData[{"CubeConnectedCycle",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,3,8}]

Table[(4^n)n,{n,5}]

Table[RootApproximant[SetPrecision[424.6614`,n]],{n,5,10}]

N[%-424.6614`,10]

Cycle

Entity["Graph",{"Cycle",n}]["LovaszNumber"]

seq=Table[GraphData[{"Cycle",n},"LovaszNumber"],{n,3,30}]

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"LovaszNumber"],{n,3,20}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"LovaszNumber"],{n,3,14}]

Do[Print[{gn=GraphData[{"DiagonalIntersection",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"LovaszNumber"],{n,3,20}]

Do[Print[{gn=GraphData[{"Dipyramid",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,3,20}]

Do[Print[{gn=GraphData[{"Dipyramid",n},"#"],InputForm@LovaszNumber[GraphData[gn],Tolerance->1.*^-15]//AbsoluteTiming}],{n,3,20}]

r=ToAlgebraicRoot[SetPrecision[x=4.360089581434064,12],"MaxDegree"->3]

Abs[x-r]

r=ToAlgebraicRoot[SetPrecision[x=5.386302911967423,12],"MaxDegree"->5]

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"LovaszNumber"],{n,3,20}]

Do[Print[{gn=GraphData[{"DoubleCone",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,3,20}]

Table[RootApproximant@SetPrecision[4.4721359`,n],{n,5,10}]

Abs[%-4.4721359`]

Table[RootApproximant@SetPrecision[6.6353344`,n],{n,5,10}]

Empty

Entity["Graph",{"Empty",n}]["LovaszNumber"]

seq=Table[GraphData[{"Empty",n},"LovaszNumber"],{n,30}]

FibonacciCube

A173173

seq=Table[GraphData[{"FibonacciCube",n},"LovaszNumber"],{n,15}]

Table[Ceiling[Fibonacci[n+2]/2],{n,15}]

Do[Print[{gn=GraphData[{"FibonacciCube",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,15}]

Flower

seq=Table[GraphData[{"Flower",n},"LovaszNumber"],{n,5,20}]

Do[Print[{gn=GraphData[{"Flower",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"LovaszNumber"],{n,2,10}]

Do[Print[{gn=GraphData[{"FoldedCube",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,2,10}]

26.666667`

Gear

seq=Table[GraphData[{"Gear",n},"LovaszNumber"],{n,3,20}]

FindSequenceFunction[seq,n-2]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"LovaszNumber"],{n,20}]

Do[Print[{gn=GraphData[{"Giraffe",{n,n}},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,20}]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"LovaszNumber"],{n,3,10}]

Do[Print[{gn=GraphData[{"Goldberg",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,3,10}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["LovaszNumber"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"LovaszNumber"],
Ceiling[m n/2]
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n

A000982

Entity["Graph",{"Grid",{n,n}}]["LovaszNumber"]

seq=Table[GraphData[{"Grid",{n,n}},"LovaszNumber"],{n,20}]

FindSequenceFunction[seq,n]//FullSimplify

Table[Ceiling[n^2/2],{n,20}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["LovaszNumber"]

DeleteCases[Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"LovaszNumber"],
Ceiling[k m n/2]
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

Tally[GraphData[{"Grid",{2,3,4}},"DistanceMatrix"]//Normal//Flatten]

Grid n×n×n

A036486

Entity["Graph",{"Grid",{n,n,n}}]["LovaszNumber"]

Internal`ClearEntityValueCache[]

seq=Table[GraphData[{"Grid",{n,n,n}},"LovaszNumber"],{n,10}]

Table[Ceiling[n^3/2],{n,10}]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"LovaszNumber"],{n,10}]

Do[Print[{gn=GraphData[{"HalvedCube",n},"#"],LovaszNumber[GraphData[gn],Method->"Sage"]//AbsoluteTiming}],{n,10}]

<<MathWorld`Graphs`

Do[Print[{gn=GraphData[{"HalvedCube",n},"#"],FullForm@LovaszNumber[GraphData[gn],Method->"SemidefiniteOptimization"]//AbsoluteTiming}],{n,10}]

Do[Print[{gn=GraphData[{"HalvedCube",n},"#"],FullForm@LovaszNumber[GraphData[gn],Method->"Mosek",Tolerance->1*^-15]//AbsoluteTiming}],{n,10}]

Hanoi

A000244

seq=Table[GraphData[{"Hanoi",n},"LovaszNumber"],{n,5}]

Helm

seq=Table[GraphData[{"Helm",n},"LovaszNumber"],{n,3,20}]

FindSequenceFunction[seq,n-2]

Hypercube

Entity["Graph",{"Hypercube",n}]["LovaszNumber"]

seq=Table[GraphData[{"Hypercube",n},"LovaszNumber"],{n,0,10}]

Table[Piecewise[{{1,n==0}},(2^(n-1))],{n,0,10}]

Keller

Entity["Graph",{"Keller",n}]["LovaszNumber"]

seq=Table[GraphData[{"Keller",n},"LovaszNumber"],{n,5}]

King m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"LovaszNumber"],
Floor[(m+1)/2]Floor[(n+1)/2]
},{n,10},{m,n}],1],{_,x_,x_}]

King n×n

A008794

seq=Table[GraphData[{"King",{n,n}},"LovaszNumber"],{n,20}]

Table[Floor[(n+1)/2]^2,{n,20}]

FindSequenceFunction[seq,n]//Factor

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["LovaszNumber"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"LovaszNumber"],
Piecewise[{{Max[m,n],Min[m,n]==1},{4,m==n==2},{XXX,Min[m,n]==2}},Ceiling[m n/2]]
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

A030978

Entity["Graph",{"Knight",{n,n}}]["LovaszNumber"]

seq=Table[GraphData[{"Knight",{n,n}},"LovaszNumber"],{n,20}]

Table[Piecewise[{{4,n==2}},Ceiling[n^2/2]],{n,20}]

Ladder

Entity["Graph",{"Ladder",n}]["LovaszNumber"]

seq=Table[GraphData[{"Ladder",n},"LovaszNumber"],{n,20}]

FindSequenceFunction[seq,n]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"LovaszNumber"],{n,20}]

MengerSponge

A307691

seq=Table[GraphData[{"MengerSponge",n},"LovaszNumber"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["LovaszNumber"]

seq=Table[GraphData[{"MoebiusLadder",n},"LovaszNumber"],{n,3,25}]

Do[Print[{gn=GraphData[{"MoebiusLadder",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,3,25}]

Table[RootApproximant[SetPrecision[5.5980762`,n]],{n,5,10}]

Table[RootApproximant[SetPrecision[7.6955181`,n]],{n,5,10}]

Table[RootApproximant[SetPrecision[9.7552826`,n]],{n,5,10}]

Mycielski

Entity["Graph",{"Mycielski",n}]["LovaszNumber"]

Inferred for n > 9:

seq=Table[GraphData[{"Mycielski",n},"LovaszNumber"],{n,11}]

Table[Piecewise[{{1,n==1||n==2},{(Sqrt[5]),n==3}},3 (2^(n-3))-1],{n,11}]

Do[Print[{gn=GraphData[{"Mycielski",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,11}]

Do[Print[{gn=GraphData[{"Mycielski",n},"#"],SageEvaluate["graphs.MycielskiGraph("<>ToString[n]<>").lovasz_theta()"]//AbsoluteTiming}],{n,11}]

But works fine when run in sage directly?!

sage: time graphs.MycielskiGraph(10).lovasz_theta()
CPU times: user 44.8 ms, sys: 9.1 ms, total: 53.8 ms
Wall time: 31min 44s
383.0

Odd

Entity["Graph",{"Odd",n}]["LovaszNumber"]

seq=Table[GraphData[{"Odd",n},"LovaszNumber"],{n,7}]

Table[Piecewise[{{1,n==1}},Binomial[-2+2 n,-2+n]],{n,7}]

Do[Print[{gn=GraphData[{"Odd",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,7}]

Pan

seq=Table[GraphData[{"Pan",n},"LovaszNumber"],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["LovaszNumber"]

seq=Table[GraphData[{"Path",n},"LovaszNumber"],{n,20}]

Table[Ceiling[n/2],{n,20}]

FindSequenceFunction[seq,n]

PathComplement

seq=Table[GraphData[{"PathComplement",n},"LovaszNumber"],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["LovaszNumber"]

seq=Table[GraphData[{"Prism",n},"LovaszNumber"],{n,3,25}]

Do[Print[{gn=GraphData[{"Prism",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,3,25}]

Table[RootApproximant[SetPrecision[6.6353344,n]],{n,5,10}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"LovaszNumber"],{n,20}]

Do[Print[{gn=GraphData[{"Queen",{n,n}},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,20}]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"LovaszNumber"],{n,20}]

Do[Print[{gn=GraphData[{"Rook",{n,n}},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,3,20}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"LovaszNumber"],{n,10}]

Do[Print[{gn=GraphData[{"RookComplement",{n,n}},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,10}]

SierpinskiCarpet

A013731

seq=Table[GraphData[{"SierpinskiCarpet",n},"LovaszNumber"],{n,4}]

FindSequenceFunction[seq,n]

SierpinskiGasket

A067771

seq=Table[GraphData[{"SierpinskiGasket",n},"LovaszNumber"],{n,5}]

FindSequenceFunction[seq,n]

SierpinskiTetrahedron

A283070

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"LovaszNumber"],{n,6}]

Table[2 (4^(n-1))+2,{n,0,6}]

Do[Print[{gn=GraphData[{"SierpinskiTetrahedron",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,6}]

Spoke n×n

A031940

seq=Table[GraphData[{"Spoke",{n,n}},"LovaszNumber"],{n,5}]

Table[Binomial[n,2]+Piecewise[{{n,Mod[n,2]==1},{n/2+1,Mod[n,2]==0}}],{n,20}]

Table[((-1)^n(2-n)+(2+n+2n^2))/4,{n,20}]

Do[Print[{{"Spoke",{n,n}},LovaszNumber[SpokeGraph[n,n]]//AbsoluteTiming}],{n,10}]

StackedBook

A128223

seq=Table[GraphData[{"StackedBook",{n,n}},"LovaszNumber"],{n,10}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]

StackedPrism

seq=Table[GraphData[{"StackedPrism",{n,n}},"LovaszNumber"],{n,3,5}]

Star

Entity["Graph",{"Star",n}]["LovaszNumber"]

seq=Table[GraphData[{"Star",n},"LovaszNumber"],{n,25}]

Sun

seq=Table[GraphData[{"Sun",n},"LovaszNumber"],{n,3,20}]

FindSequenceFunction[seq,n-2]//Factor

Sunlet

seq=Table[GraphData[{"Sunlet",n},"LovaszNumber"],{n,3,20}]

FindSequenceFunction[seq,n-2]

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"LovaszNumber"],{n,6,10}]

https://core.ac.uk/download/pdf/6714715.pdf

Haemers, W.~H.  ``An Upper Bound for the Shannon Capacity of a Graph.''  {\it Colloq.\ Math.\ Soc.\ J\'anos Bolyai} {\bf 25}, 267--272, 1978.

Table[((n(n-2)(2n-1))/(3(3n-14))),{n,9,10}]

N[%]

LovaszNumber[JohnsonGraph[9,3],Debug->True]//InputForm

???

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"LovaszNumber"],{n,3,10}]

Do[Print[{gn=GraphData[{"TorusGrid",{n,n}},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,3,10}]

Transposition

Entity["Graph",{"Transposition",n}]["LovaszNumber"]

Entity["Graph",{"Transposition",n}]["IndependenceNumber"]

seq=Table[GraphData[{"Transposition",n},"LovaszNumber"],{n,6}]

FindSequenceFunction[Rest@seq,n-1]//FunctionExpand

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["LovaszNumber"]

seq=Table[GraphData[{"Trapezohedron",n},"LovaszNumber"],{n,3,20}]

FindSequenceFunction[seq,n-2]

Triangular

seq=Table[GraphData[{"Triangular",n},"LovaszNumber"],{n,2,10}]

Do[Print[{gn=GraphData[{"Triangular",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,2,10}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"LovaszNumber"],{n,0,10}]

Do[Print[{gn=GraphData[{"TriangularGrid",n},"#"],InputForm@LovaszNumber[GraphData[gn],Method->"Mosek",Tolerance->1.*^-15]//AbsoluteTiming}],{n,0,10}]

Table[RootApproximant[SetPrecision[7.3600896`,n]],{n,5,10}]

N[%,10]

r=ToAlgebraicRoot[SetPrecision[x=7.360089581434081,12],"MaxDegree"->3]

Abs[x-r]

TriangularHoneycombAcuteKnight

A287195

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"LovaszNumber"],{n,20}]

Do[Print[{gn=GraphData[{"TriangularHoneycombAcuteKnight",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"LovaszNumber"],{n,9}]

Do[Print[{gn=GraphData[{"TriangularHoneycombBishop",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,9}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"LovaszNumber"],{n,20}]

Do[Print[{gn=GraphData[{"TriangularHoneycombObtuseKnight",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"LovaszNumber"],{n,10}]

Do[Print[{gn=GraphData[{"TriangularHoneycombQueen",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,10}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"LovaszNumber"],{n,10}]

Do[Print[{gn=GraphData[{"TriangularHoneycombRook",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,10}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"LovaszNumber"],{n,1,20,2}]

Web

seq=Table[GraphData[{"Web",n},"LovaszNumber"],{n,3,20}]

Do[Print[{gn=GraphData[{"Web",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["LovaszNumber"]

seq=Table[GraphData[{"Wheel",n},"LovaszNumber"],{n,4,20}]

Do[Print[{gn=GraphData[{"Wheel",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,4,20}]

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"LovaszNumber"],{n,4,20}]

Do[Print[{gn=GraphData[{"WheelComplement",n},"#"],LovaszNumber[GraphData[gn]]//AbsoluteTiming}],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"LovaszNumber"],{n,2,10}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"LovaszNumber"],{n,20}]

Known

Grid[GraphData[#,{"V","Name","LovaszNumber"}]&/@SortBy[DeleteCases[GraphData["LovaszNumber","Defined"],{_Integer,_}],GraphData[#,"V"]&],Frame->All,Alignment->Left]

Quartic Circulant

f[0,{x_,y_},{n_,j_}]:=n+2x+2y
f[i_,{x_,y_},{n_,j_}]:=2x Cos[2π i/n]+2y Cos[2π i j/n]

LovaszMax[{nn_,jj_},{x_,y_}]:=Module[{i},
Max[Table[f[i,{x,y},{nn,jj}],{i,0,(nn-1)/2}]]
]
LovaszTheta[nn_,jj_]:=Module[{x,y},
MinValue[LovaszMax[{nn,jj},{x,y}],{x,y}]
]
NLovaszTheta[nn_,jj_,opts___]:=Module[{x,y},
RootApproximant[MinValue[LovaszMax[{nn,jj},{x,y}],{x,y},opts,WorkingPrecision->1000]]
]

FullSimplify/@TrigToExp/@Table[LovaszTheta[n,2],{n,3,10,2}]//Timing

Table[NLovaszTheta[n,2],{n,3,20,2}]//Timing

expr=LovaszTable[{11,2},{x,y}]

RootApproximant/@Table[MinValue[LovaszTable[{n,2},{x,y}],{x,y},WorkingPrecision->100],{n,5,15,2}]

NLovaszTheta[13,2]

RootApproximant[%]

N[Root[30613-27951 #1+7502 ((#1)^2)-242 ((#1)^3)-99 ((#1)^4)+((#1)^5)&,4],20]

NLovaszTheta[11,2,WorkingPrecision->200,PrecisionGoal->100,Method->"DifferentialEvolution"]

FullSimplify/@TrigToExp/@Table[LovaszTheta[n,3],{n,5,10,2}]//Timing

Table[NLovaszTheta[n,3],{n,5,20,2}]//Timing

FullSimplify/@TrigToExp/@Table[LovaszTheta[n,4],{n,7,10,2}]//Timing

Table[NLovaszTheta[n,4],{n,7,20,2}]//Timing

Formulas

FullSimplify/@TrigToExp/@Table[n(1-(((1/2)-Cos[((2π)/n)Floor[(n/3)]]-Cos[((2π)/n)(Floor[(n/3)]+1)])/((Cos[((2π)/n)Floor[(n/3)]]-1)(Cos[((2π)/n)(Floor[(n/3)]+1)]-1)))),{n,3,15,2}]

N[%]

FullSimplify/@TrigToExp/@Table[n(1-(((Cos[(π/n)])^2)-Cos[(π/n)]Cos[((2π)/n)Ceiling[((n-3)/6)]]+((Cos[((2π)/n)Ceiling[((n-3)/6)]])^2)-1)/((Cos[(π/n)]+1)(Cos[((2π)/n)Ceiling[((n-3)/6)]]-1)(1-Cos[(π/n)]+Cos[((2π)/n)Ceiling[((n-3)/6)]]))),{n,5,12,2}]

N[%]

Algorithms

Sage

(bad=DeleteCases[
Monitor[{
gn=#,
N@GraphData[#,"LovaszNumber"],
LovaszNumber[GraphData[#],Method->"Sage"]
}&/@GraphData[;;4],
gn],
{_,x_,y_}/;Abs[x-y]<.0001])//AbsoluteTiming

Computed numerical values

Length[todo=SortBy[Select[GraphData[All],MissingQ[GraphData[#,"LovaszNumber"]]&],GraphData[#,{"V","M"}]&]]

p=FirstPosition[todo,{"Fullerene",{50,53}},{0}][[1]]

Module[{
res={#,LovaszNumber[GraphData[#],TimeConstraint->60]//AbsoluteTiming}
},
If[FreeQ[res,$Aborted|$Failed|Failure|GraphData],Print[res]]
]&/@todo;

Debugging

<<MathWorld`Graphs`

K4

CSDP

FullForm@LovaszNumber[GraphData["K4"],Method->"CSDP",Tolerance->1.*^-9]

FullForm@LovaszNumber[GraphData["K4"],Method->"CSDP",Tolerance->1.*^-12]

DSDP

FullForm@LovaszNumber[GraphData["K4"],Method->"DSDP"]

FullForm@LovaszNumber[GraphData["K4"],Method->"DSDP",Tolerance->1.*^-12]

FullForm@LovaszNumber[GraphData["K4"],Method->"DSDP",Tolerance->1.*^-13]

FullForm@LovaszNumber[GraphData["K4"],Method->"DSDP",Tolerance->1.*^-14]

FullForm@LovaszNumber[GraphData["K4"],Method->"DSDP",Tolerance->1.*^-16]

Mosek

FullForm@LovaszNumber[GraphData["K4"],Method->"Mosek"]

FullForm@LovaszNumber[GraphData["K4"],Method->"Mosek",Tolerance->1.*^-8]

FullForm@LovaszNumber[GraphData["K4"],Method->"Mosek",Tolerance->1.*^-10]

FullForm@LovaszNumber[GraphData["K4"],Method->"Mosek",Tolerance->1.*^-20]

SCS

FullForm@LovaszNumber[GraphData["K4"],Method->"SCS"]

FullForm@LovaszNumber[GraphData["K4"],Method->"SCS",Tolerance->1.*^-8]

FullForm@LovaszNumber[GraphData["K4"],Method->"SCS",Tolerance->1.*^-10]

FullForm@LovaszNumber[GraphData["K4"],Method->"SCS",Tolerance->1.*^-20]

{"HalvedCube", 9}

GraphData[{"HalvedCube",9},"LovaszNumber"]

CSDP

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"CSDP"]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"CSDP",Tolerance->1.*^-8]//Timing

DSDP

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"DSDP"]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"DSDP",Tolerance->1.*^-8]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"DSDP",Tolerance->1.*^-9]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"DSDP",Tolerance->1.*^-10]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"DSDP",Tolerance->1.*^-12]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"DSDP",Tolerance->1.*^-15]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"DSDP",Tolerance->1.*^-16]//Timing

Mosek

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"Mosek"]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"Mosek",Tolerance->1.*^-8]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"Mosek",Tolerance->1.*^-9]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"Mosek",Tolerance->1.*^-10]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"Mosek",Tolerance->1.*^-12]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"Mosek",Tolerance->1.*^-16]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"Mosek",Tolerance->1.*^-17]//Timing

SCS

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"SCS"]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"SCS",Tolerance->1.*^-8]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"SCS",Tolerance->1.*^-10]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"SCS",Tolerance->1.*^-10,MaxIterations->1000]//Timing

FullForm@LovaszNumber[GraphData[{"HalvedCube",9}],Method->"SCS",Tolerance->1.*^-10,MaxIterations->10000]//Timing

Checks

Known using Mosek with default Tolerance

Monitor[data={
gn=#,
GraphData[#,"LovaszNumber"],
LovaszNumber[GraphData[#],Method->"Mosek"],
}&/@SIntersection[GraphData["LovaszNumber","Defined"],GraphData[;;200]],
gn];//AbsoluteTiming

Select[data,!FreeQ[#,SemidefiniteOptimization]&][[All,1]]

TextGrid[
Select[{#,#2,#3,Abs[#2-#3]}&@@@DeleteCases[data,{_,_,_SemidefiniteOptimization}],Last[#]≥1*^-6&],
Dividers->All]

TextGrid[
Select[{#,#2,#3,Abs[#2-#3]}&@@@DeleteCases[data,{_,_,_SemidefiniteOptimization}],Last[#]≥1*^-7&],
Dividers->All]

Known using Mosek with Tolerance (10^(-12))

Monitor[data={
gn=#,
GraphData[#,"LovaszNumber"],
LovaszNumber[GraphData[#],Method->"Mosek",Tolerance->1*^-12]
}&/@Intersection[GraphData["LovaszNumber","Defined"],GraphData[;;200]],gn];//AbsoluteTiming

Select[data,!FreeQ[#,SemidefiniteOptimization]&][[All,1]]

TextGrid[
Select[{#,#2,#3,Abs[#2-#3]}&@@@DeleteCases[data,{_,_,_SemidefiniteOptimization}],Last[#]≥1*^-7&],
Dividers->All]

TextGrid[Select[{#,#2,#3,Abs[#2-#3]}&@@@DeleteCases[data,{_,_,_SemidefiniteOptimization}],Last[#]≥1*^-9&],
Dividers->All]

TextGrid[Select[{#,#2,#3,Abs[#2-#3]}&@@@DeleteCases[data,{_,_,_SemidefiniteOptimization}],Last[#]≥1*^-10&],
Dividers->All]

Known using Mosek with Tolerance (10^(-15))

Monitor[data={
gn=#,
GraphData[#,"LovaszNumber"],
LovaszNumber[GraphData[#],Method->"Mosek",Tolerance->1*^-15]
}&/@Intersection[GraphData["LovaszNumber","Defined"],GraphData[;;200]],gn];//AbsoluteTiming

bug(435148): SemidefiniteOptimization[..., Method -> "Mosek", "Tolerance -> 1.*^-15] could issue a message and return a value (instead of unevaluated)

Select[data,!FreeQ[#,SemidefiniteOptimization]&][[All,1]]

TextGrid[
Select[{#,#2,#3,Abs[#2-#3]}&@@@DeleteCases[data,{_,_,_SemidefiniteOptimization}],Last[#]≥1*^-7&],
Dividers->All]

TextGrid[Select[{#,#2,#3,Abs[#2-#3]}&@@@DeleteCases[data,{_,_,_SemidefiniteOptimization}],Last[#]≥1*^-9&],
Dividers->All]

TextGrid[Select[{#,#2,#3,Abs[#2-#3]}&@@@DeleteCases[data,{_,_,_SemidefiniteOptimization}],Last[#]≥1*^-10&],
Dividers->All]

TextGrid[Select[{#,#2,#3,Abs[#2-#3]}&@@@DeleteCases[data,{_,_,_SemidefiniteOptimization}],Last[#]≥1*^-11&],
Dividers->All]

LovaszNumber[GraphData["HigmanSimsBipartiteDoubleGraph"],Method->"Mosek",Tolerance->1.*^-15]//FullForm//Timing

LovaszNumber[GraphData["HigmanSimsBipartiteDoubleGraph"],Method->"Mosek",Tolerance->4.*^-16]//FullForm//Timing

Compute

SemidefiniteOptimization 1-200

pat=_Integer|
_Integer+ Sqrt[_Integer?(LessEqualThan[100])]|
_Integer+_Integer Sqrt[_Integer?(LessEqualThan[100])]|Sqrt[_Integer]|
Rational[_Integer?(LessEqualThan[100]),_Integer?(LessEqualThan[10])]|
_Rational(_Integer?(LessEqualThan[50])+_Integer?(LessEqualThan[10])Sqrt[_Integer?(LessEqualThan[50])]);

Monitor[computed={
gn=#,
InputForm[theta=LovaszNumber[GraphData[#],Method->"Mosek",Tolerance->1*^-15]],
If[NumericQ[theta],r=RootApproximant[SetPrecision[theta,10]],$Failed],
If[NumericQ[theta],Abs[r-theta],$Failed]
}&/@Intersection[GraphData["LovaszNumber","Missing"],GraphData[;;200]],gn];//AbsoluteTiming

TextGrid[possible=Select[computed,1*^-12<=#[[4]]<=1*^-10&],Dividers->All]

TextGrid[prettygood=Select[possible,MatchQ[#[[3]],pat]&],Dividers->All]

TextGrid[good=Select[computed,#[[4]]<=1*^-12&],Dividers->All]

l={#,{0,#3}}&@@@Join[good,prettygood]

SemidefiniteOptimization 201-500

pat=_Integer|
_Integer+ Sqrt[_Integer?(LessEqualThan[100])]|
_Integer+_Integer Sqrt[_Integer?(LessEqualThan[100])]|Sqrt[_Integer]|
Rational[_Integer?(LessEqualThan[200]),_Integer?(LessEqualThan[10])]|
_Rational(_Integer?(LessEqualThan[50])+_Integer?(LessEqualThan[10])Sqrt[_Integer?(LessEqualThan[50])]);

Monitor[computed={
gn=#,
InputForm[theta=LovaszNumber[GraphData[#],Method->"Mosek",Tolerance->1*^-15]],
If[NumericQ[theta],r=RootApproximant[SetPrecision[theta,10]],$Failed],
If[NumericQ[theta],Abs[r-theta],$Failed]
}&/@Intersection[GraphData["LovaszNumber","Missing"],GraphData[201;;500]],gn];//AbsoluteTiming

Cases[computed,{gn_,$Failed,__}:>gn]

TextGrid[somewhatpossible=Select[computed,1*^-10<=#[[4]]<=1*^-8&],Dividers->All]

TextGrid[possible=Select[computed,1*^-12<=#[[4]]<=1*^-10&],Dividers->All]

TextGrid[prettygood=Select[Join[somewhatpossible,possible],MatchQ[#[[3]],pat]&],Dividers->All]

TextGrid[good=Select[computed,#[[4]]<=1*^-12&],Dividers->All]

l={#,{0,#3}}&@@@Join[good,prettygood]

SemidefiniteOptimization 501-750

data={{"Foster504B",{29.736583`,240.80665357752477`}},{"Foster504C",{20.441994`,$Failed}},{"Foster504E",{19.750811`,242.10868867929182`}},{"Foster506A",{19.172408`,237.78908104021227`}},{"PartsGraph509",{54.090501`,169.42698629316965`}},{"HeuleGraph510",{57.394678`,170.21972760696863`}},{"PartsGraph510",{56.659368`,170.487752417711`}},{"HeuleGraph517",{77.071834`,169.08470020416163`}},{"PartsGraph525",{48.753701`,173.43888030021515`}},{"HeuleGraph529",{86.514152`,173.6249348959999`}},{"PartsGraph529",{55.972329`,175.63955916431783`}},{"U42Graph540",{38735.378361`,45.00000000003438`}},{{"GoethalsSeidelBlockDesign",{5,11}},{88493.22711`,45.00000000003283`}},{"TaylorGraphFromConway1",{88775.398765`,9.85714285713566`}},{"TaylorGraphFromConway2",{78219.113124`,$Failed}},{"HeuleGraph553",{151.953772`,187.3758343266598`}},{"PartsGraph553",{76.754202`,188.63809421334196`}},{"Foster570A",{31.772039`,266.6815413553001`}},{"Foster570B",{26.884454`,$Failed}},{{"Cage",{17,5}},{155.884665`,167.6944332255284`}},{"HundredTwentyCellGraph",{31.309513`,249.84471899929346`}},{{"RegularNonplanarDiameter",{3,9,600}},{99.729595`,288.3630949471825`}},{"HeuleGraph610",{87.615704`,208.01707548953092`}},{"Foster620A",{32.296342`,294.86461598300826`}},{{"RegularNonplanarDiameter",{5,5,620}},{105.371542`,266.1529706084029`}},{{"RegularNonplanarDiameter",{5,5,624}},{126.716053`,263.8678666741482`}},{"ExooIsmailescuGraph627",{247.061609`,222.60859691547878`}},{"HeuleGraph633",{108.995056`,216.21185393014323`}},{{"Grassmann",{2,{6,2}}},{5461.403609`,$Failed}},{"Foster660A",{32.762231`,314.5738922299139`}},{"Foster672C",{40.360348`,324.42392467167645`}},{"MoscowSoicherGraph",{10843.044247`,$Failed}},{"U62Graph",{44963.090802`,$Failed}},{"Foster680A",{39.44531`,329.09905769077704`}},{"Foster680B",{39.946867`,$Failed}},{"Rectified600CellGraph",{83.549817`,205.08466175626396`}},{{"DiagonalIntersection",13},{83.339205`,290.1914613967429`}},{"ExtendedTernaryGolayCodeCosetGraph",{364.054147`,$Failed}},{"GamesGraph",{15953.531123`,124.20000000073736`}},{"ShortenedExtendedTernaryGolayCodeCosetGraph",{214.046327`,$Failed}}}/.HoldPattern[InputForm[x_]]:>x;

pat=_Integer|
_Integer+ Sqrt[_Integer?(LessEqualThan[100])]|
_Integer+_Integer Sqrt[_Integer?(LessEqualThan[100])]|Sqrt[_Integer]|
Rational[_Integer?(LessEqualThan[1000]),_Integer?(LessEqualThan[10])]|
_Rational(_Integer?(LessEqualThan[50])+_Integer?(LessEqualThan[10])Sqrt[_Integer?(LessEqualThan[50])]);

Monitor[computed={
gn=#,
InputForm[theta=#2[[2]]],
If[NumericQ[theta],r=RootApproximant[SetPrecision[theta,10]],$Failed],
If[NumericQ[theta],Abs[r-theta],$Failed]
}&@@@data,gn];//AbsoluteTiming

computed

Cases[computed,{gn_,__,$Failed}:>gn]

TextGrid[somewhatpossible=Select[computed,1*^-10<=#[[4]]<=1*^-8&],Dividers->All]

TextGrid[possible=Select[computed,1*^-12<=#[[4]]<=1*^-10&],Dividers->All]

TextGrid[prettygood=Select[Join[somewhatpossible,possible],MatchQ[#[[3]],pat]&],Dividers->All]

TextGrid[good=Select[computed,#[[4]]<=1*^-12&],Dividers->All]

l={#,{0,#3}}&@@@Join[good,prettygood]