Mathematics for Computer Science

Glossary of Symbols901

symbol meaning

R path relation of relationR; reflexive transitive closure ofR

RC positive path relation ofR; transitive closure ofR

fbxg merge of walkfwith end vertexx

and walkgwith start vertexx

fbg merge of walkfand walkg

wheref’s end vertex equalsg’s start vertex

hu—vi undirected edge connecting verticesu¤v

E.G/ the edges of graphG

V.G/ the vertices of graphG

Cn the length-nundirected cycle

Ln the length-nline graph

Kn then-vertex complete graph

Hn then-dimensional hypercube

L.G/ the “left” vertices of bipartite graphG

R.G/ the “right” vertices of bipartite graphG

Kn;m the complete bipartite graph withnleft andmright vertices

.G/ chromatic number of simple graphG

Hn thenth Harmonic number

Pn

iD 1 1=i

 asymptotic equality

nŠ nfactorialWWDn
.n1/


 2 
 1

n

m

WWDnŠ=mŠ..nm/Š; the binomial coefficient

o./ asymptotic notation “little oh”

O./ asymptotic notation “big oh”

‚./ asymptotic notation “Theta”

./ asymptotic notation “big Omega”

!./ asymptotic notation “little omega”

PrŒAç probability of eventA

Pr



AjB



conditional probability ofAgivenB

S sample space

IA indicator variable for eventA

PDF probability density function

CDF cumulative distribution function

ExŒRç expectation of random variableR

ExŒRjAç conditional expectation ofRgiven eventA

Ex^2 ŒRç abbreviation for.ExŒRç/^2

VarŒRç variance ofR

Var^2 ŒRç the square of the variance ofR

R standard deviation ofR