| Preface to the first edition |
|
xi | |
| Preface to the second edition |
|
xiii | |
|
|
|
1 | (11) |
|
Terminology of graphs and digraphs, Eulerian circuits, Hamiltonian circuits |
|
|
|
|
|
12 | (12) |
|
Cayley's theorem, spanning trees and the greedy algorithm, search trees, strong connectivity |
|
|
|
Colorings of graphs and Ramsey's theorem |
|
|
24 | (13) |
|
Brooks' theorem, Ramsey's theorem and Ramsey numbers, the Lovasz sieve, the Erdos-Szekeres theorem |
|
|
|
Turan's theorem and extremal graphs |
|
|
37 | (6) |
|
Turan's theorem and extremal graph theory |
|
|
|
Systems of distinct representatives |
|
|
43 | (10) |
|
Bipartite graphs, P. Hall's condition, SDRs, Konig's theorem, Birkhoff's theorem |
|
|
|
Dilworth's theorem and extremal set theory |
|
|
53 | (8) |
|
Partially ordered sets, Dilworth's theorem, Sperner's theorem, symmetric chains, the Erdos-Ko-Rado theorem |
|
|
|
|
|
61 | (10) |
|
The Ford-Fulkerson theorem, the integrality theorem, a generalization of Birkhoff's theorem, circulations |
|
|
|
|
|
71 | (6) |
|
The number of De Bruijn sequences |
|
|
|
Two (0, 1, *) problems: addressing for graphs and a hash-coding scheme |
|
|
77 | (12) |
|
Quadratic forms, Winkler's theorem, associative block designs |
|
|
|
The principle of inclusion and exclusion; inversion formulae |
|
|
89 | (9) |
|
Inclusion---exclusion, derangements, Euler indicator, Mobius function, Mobius inversion, Burnside's lemma, probleme des menages |
|
|
|
|
|
98 | (12) |
|
Bounds on permanents, Schrijver's proof of the Minc conjecture, Fekete's lemma, permanents of doubly stochastic matrices |
|
|
|
The Van der Waerden conjecture |
|
|
110 | (9) |
|
The early results of Marcus and Newman, London's theorem, Egoritsjev's proof |
|
|
|
Elementary counting; Stirling numbers |
|
|
119 | (10) |
|
Stirling numbers of the first and second kind, Bell numbers, generating functions |
|
|
|
Recursions and generating functions |
|
|
129 | (23) |
|
Elementary recurrences, Catalan numbers, counting of trees, Joyal theory, Lagrange inversion |
|
|
|
|
|
152 | (17) |
|
The function pk(n), the partition function, Ferrers diagrams, Euler's identity, asymptotics, the Jacobi triple product identity, Young tableaux and the hook formula |
|
|
|
|
|
169 | (13) |
|
Matrices with given line sums, counting (0,1)-matrices |
|
|
|
|
|
182 | (17) |
|
Orthogonal arrays, conjugates and isomorphism, partial and incomplete Latin squares, counting Latin squares, the Evans conjecture, the Dinitz conjecture |
|
|
|
Hadamard matrices, Reed---Muller codes |
|
|
199 | (16) |
|
Hadamard matrices and conference matrices, recursive constructions, Paley matrices, Williamson's method, excess of a Hadamard matrix, first order Reed-Muller codes |
|
|
|
|
|
215 | (29) |
|
The Erdos-De Bruijn theorem, Steiner systems, balanced incomplete block designs, Hadamard designs, counting, (higher) incidence matrices, the Wilson-Petrenjuk theorem, symmetric designs, projective planes, derived and residual designs, the Bruck-Ryser-Chowla theorem, constructions of Steiner triple systems, write-once memories |
|
|
|
|
|
244 | (17) |
|
Terminology of coding theory, the Hamming bound, the Singleton bound, weight enumerators and Mac Williams' theorem, the Assmus-Mattson theorem, symmetry codes, the Golay codes, codes from projective planes |
|
|
|
Strongly regular graphs and partial geometries |
|
|
261 | (22) |
|
The Bose-Mesner algebra, eigenvalues, the integrality condition, quasisymmetric designs, the Krein condition, the absolute bound, uniqueness theorems, partial geometries, examples, directed strongly regular graphs, neighborhood regular graphs |
|
|
|
|
|
283 | (20) |
|
Pairwise orthogonal Latin squares and nets, Euler's conjecture, the Bose-Parker-Shrikhande theorem, asymptotic existence, orthogonal arrays and transversal designs, difference methods, orthogonal subsquares |
|
|
|
Projective and combinatorial geometries |
|
|
303 | (22) |
|
Projective and affine geometries, duality, Pasch's axiom, Desargues' theorem, combinatorial geometries, geometric lattices, Greene's theorem |
|
|
|
Gaussian numbers and q-analogues |
|
|
325 | (8) |
|
Chains in the lattice of subspaces, q-analogue of Sperner's theorem, interpretation of the coefficients of the Gaussian polynomials, spreads |
|
|
|
Lattices and Mobius inversion |
|
|
333 | (18) |
|
The incidence algebra of a poset, the Mobius function, chromatic polynomial of a graph, Weisner's theorem, complementing permutations of geometric lattices, connected labeled graphs, MDS codes |
|
|
|
Combinatorial designs and projective geometries |
|
|
351 | (18) |
|
Arcs and subplanes in projective planes, blocking sets, quadratic and Hermitian forms, unitals, generalized quadrangles, Mobius planes |
|
|
|
Difference sets and automorphisms |
|
|
369 | (14) |
|
Block's lemma, automorphisms of symmetric designs, Paley-Todd and Stanton-Sprott difference sets, Singer's theorem |
|
|
|
Difference sets and the group ring |
|
|
383 | (13) |
|
The Multiplier Theorem and extensions, homomorphisms and further necessary conditions |
|
|
|
Codes and symmetric designs |
|
|
396 | (9) |
|
The sequence of codes of a symmetric design, Wilbrink's theorem |
|
|
|
|
|
405 | (27) |
|
Examples, the eigenmatrices and orthogonality relations, formal duality, the distribution vector of a subset, Delsarte's inequalities, polynomial schemes, perfect codes and tight designs |
|
|
|
(More) algebraic techniques in graph theory |
|
|
432 | (19) |
|
Tournaments and the Graham-Pollak theorem, the spectrum of a graph, Hoffman's theorem, Shannon capacity, applications of interlacing and Perron-Frobenius |
|
|
|
|
|
451 | (8) |
|
Vertex connectivity, Menger's theorem, Tutte connectivity |
|
|
|
|
|
459 | (13) |
|
The chromatic polynomial, Kuratowski's theorem, Euler's formula, the Five Color Theorem, list-colorings |
|
|
|
|
|
472 | (19) |
|
Whitney duality, circuits and cutsets, MacLane's theorem |
|
|
|
Embeddings of graphs on surfaces |
|
|
491 | (16) |
|
Embeddings on arbitrary surfaces, the Ringel-Youngs theorem, the Heawood conjecture, the Edmonds embedding technique |
|
|
|
Electrical networks and squared squares |
|
|
507 | (15) |
|
The matrix-tree theorem, De Bruijn sequences, the network of a squared rectangle, Kirchhoff's theorem |
|
|
|
|
|
522 | (14) |
|
The cycle index of a permutation group, counting orbits, weights, necklaces, the symmetric group, Stirling numbers |
|
|
|
|
|
536 | (6) |
|
One-factorizations of complete graphs and complete designs |
|
|
|
Appendix 1. Hints and comments on problems |
|
|
542 | (36) |
|
Hints, suggestions, and comments on the problems in each chapter |
|
|
|
Appendix 2. Formal power series |
|
|
578 | (6) |
|
Formal power series ring, formal derivatives, inverse functions, residues, the Lagrange-Burmann formula |
|
|
| Name Index |
|
584 | (6) |
| Subject Index |
|
590 | |
Other versions by this Author
