Combinatorics for Computer Scientists
Dany Breslauer and Devdatt P. Dubhashi
August 1995.
viii+184 pp.
BRICS Lecture Series
Contents
I Enumeration
1 Inclusion-Exclusion
2 Inclusion-Exclusion II
3 Mobius Inversion
4 Mobius Inversion II
5 Generating functions
6 Generating functions II
7 Yet more on Generating functions
8 Probability Generating Functions
9 A coin flipping game
II Graph Theory
10 Basics
10.1 Graphs
10.2 Subgraphs
10.3 Isomorphism
10.4 Incidence and adjacency matrices
10.5 Paths and cycles
10.6 Degree
10.7 Special graphs
11 Trees
11.1 Cut-vertices and cut-edges
11.2 Cayley's formula
11.3 Application: lower bounds
12 Eulerian and Hamiltonian walks
12.1 Euler tours
12.2 Hamilton cycles
12.3 De Bruijn Sequences
13 Connectivity
13.1 Connectivity and degree
13.2 Menger's Theorem
14 Matching
14.1 Berge's Theorem
14.2 Hall's Theorem
14.3 Konig Theorem
14.4 Tutte's Theorem
15 Edge colouring
15.1 Vizing's Theorem
16 Cliques 119
16.1 Ramsey's Theorem
16.2 Turan's Theorem
17 Vertex colouring
17.1 Chromatic polynomials
17.2 Girth
18 Planar graphs
18.1 The dual graph
18.2 Euler's Formula
18.3 Platonic solids
18.4 Kuratowski's Theorem
18.5 Colouring planar graphs
19 Problems
III Linear Algebra in Combinatorics
20 Invitation to Club Theory
20.1 A Tale of Two Cities
20.2 Phones, networks and addressing
21 Some Club Theory Classics
22 More Club Theory
23 Greedy Algorithms and Matroids
24 Probability Spaces with Limited Independence
http://ifile.it/fljyh8w/comb_for_cs.pdf
