Invitation to Discrete Mathematics 2/e

Name: Invitation to Discrete Mathematics 2/e
Brand: Oxford University Press
Price: 97.19 EUR
Availability: OnlineOnly

MATOUSEK JIRI(Autor*in)

Oxford University Press

1. Auflage

Erschienen am 9. Oktober 2008

462 Seiten

E-Book

PDF mit Adobe-DRM

Systemvoraussetzungen

978-0-19-152467-7 (ISBN)

97,19 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Adobe-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Intro
Contents
1 Introduction and basic concepts
1.1 An assortment of problems
1.2 Numbers and sets: notation
1.3 Mathematical induction and other proofs
1.4 Functions
1.5 Relations
1.6 Equivalences and other special types of relations
2 Orderings
2.1 Orderings and how they can be depicted
2.2 Orderings and linear orderings
2.3 Ordering by inclusion
2.4 Large implies tall or wide
3 Combinatorial counting
3.1 Functions and subsets
3.2 Permutations and factorials
3.3 Binomial coefficients
3.4 Estimates: an introduction
3.5 Estimates: the factorial function
3.6 Estimates: binomial coefficients
3.7 Inclusion-exclusion principle
3.8 The hatcheck lady & co.
4 Graphs: an introduction
4.1 The notion of a graph
isomorphism
4.2 Subgraphs, components, adjacency matrix
4.3 Graph score
4.4 Eulerian graphs
4.5 Eulerian directed graphs
4.6 2-connectivity
4.7 Triangle-free graphs: an extremal problem
5 Trees
5.1 Definition and characterizations of trees
5.2 Isomorphism of trees
5.3 Spanning trees of a graph
5.4 The minimum spanning tree problem
5.5 Jarník's algorithm and Boruvka's algorithm
6 Drawing graphs in the plane
6.1 Drawing in the plane and on other surfaces
6.2 Cycles in planar graphs
6.3 Euler's formula
6.4 Coloring maps: the four-color problem
7 Double-counting
7.1 Parity arguments
7.2 Sperner's theorem on independent systems
7.3 An extremal problem: forbidden four-cycles
8 The number of spanning trees
8.1 The result
8.2 A proof via score
8.3 A proof with vertebrates
8.4 A proof using the Prüfer code
8.5 Proofs working with determinants
8.6 The simplest proof?
9 Finite projective planes
9.1 Definition and basic properties
9.2 Existence of finite projective planes
9.3 Orthogonal Latin squares
9.4 Combinatorial applications
10 Probability and probabilistic proofs
10.1 Proofs by counting
10.2 Finite probability spaces
10.3 Random variables and their expectation
10.4 Several applications
11 Order from disorder: Ramsey's theorem
11.1 A party of six
11.2 Ramsey's theorem for graphs
11.3 A lower bound for the Ramsey numbers
12 Generating functions
12.1 Combinatorial applications of polynomials
12.2 Calculation with power series
12.3 Fibonacci numbers and the golden section
12.4 Binary trees
12.5 On rolling the dice
12.6 Random walk
12.7 Integer partitions
13 Applications of linear algebra
13.1 Block designs
13.2 Fisher's inequality
13.3 Covering by complete bipartite graphs
13.4 Cycle space of a graph
13.5 Circulations and cuts: cycle space revisited
13.6 Probabilistic checking
Appendix: Prerequisites from algebra
Bibliography
Hints to selected exercises
Index
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
Z

Systemvoraussetzungen

Als PDF speichern Als Link merken