## Discrete Mathematics Lecture Notes Incomplete Preliminary Version

The best asymptotic constant is c =ln2+ o(1). Copyright c 2003 ...... Draw two non-isomorphic regular graphs of the same degree on 6 vertices. ...... In discrete mathematics, theoretical computer science, and statistical physics, we often have to ...
Discrete Mathematics Lecture Notes Incomplete Preliminary Version Instructor: L´aszl´o Babai Last revision: June 22, 2003 Last update: October 24, 2003

Contents 1 Logic

1

1.1

Quantifier notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

2 Asymptotic Notation

5

2.1

Limit of sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2

Asymptotic Equality and Inequality . . . . . . . . . . . . . . . . . . . . . . . .

6

2.3

Little-oh notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.4

Big-Oh, Omega, Theta notation (O, Ω, Θ) . . . . . . . . . . . . . . . . . . . . .

10

2.5

Prime Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.6

Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

2.7

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

3 Convex Functions and Jensen’s Inequality

15

4 Basic Number Theory

19

4.1

Introductory Problems: g.c.d., congruences, multiplicative inverse, Chinese Remainder Theorem, Fermat’s Little Theorem . . . . . . . . . . . . . . . . . . . .

19

4.2

Gcd, congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

4.3

Arithmetic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

4.4

Prime Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

4.5

Quadratic Residues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

4.6

Lattices and diophantine approximation . . . . . . . . . . . . . . . . . . . . . .

35

iii

iv

CONTENTS

5 Counting

37

5.1

Binomial coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

5.2

Recurrences, generating functions . . . . . . . . . . . . . . . . . . . . . . . . . .

40

6 Graphs and Digraphs

43

6.1

Graph Theory Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

6.2

Digraph Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

7 Finite Probability Spaces

63

7.1

Finite Probability Spaces and Events . . . . . . . . . . . . . . . . . . . . . . . .

63

7.2

Random Variables and Expected Value . . . . . . . . . . . . . . . . . . . . . . .

68

7.3

Standard deviation and Chebyshev’s Inequality . . . . . . . . . . . . . . . . . .

70

7.4

Independence of random variables . . . . . . . . . . . . . . . . . . . . . . . . .

71

7.5

Chernoff’s Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

7.6

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

77

8 Finite Markov Chains 8.2

Problems . . . . . . . . . . . . . . .