1 option
A course in combinatorics / J.H. van Lint and R.M. Wilson.
Math/Physics/Astronomy Library QA164 .L56 1992
Available
- Format:
- Book
- Author/Creator:
- Lint, Jacobus Hendricus van, 1932-
- Language:
- English
- Subjects (All):
- Combinatorial analysis.
- Physical Description:
- xii, 530 pages : illustrations ; 26 cm
- Place of Publication:
- Cambridge [England] ; New York : Cambridge University Press, 1992.
- Summary:
- Combinatorics deals with ways of arranging and distributing mathematical objects, and involves ideas from geometry, algebra and analysis. The breadth of its theory is matched by that of its applications, which include topics as diverse as codes, circuit design and algorithm complexity. So, it has become essential for workers in many scientific fields, for example, electrical engineering and computer science, to have some knowledge of the subject.
- Contents:
- 1. Graphs 1
- Terminology of graphs and digraphs
- Eulerian circuits
- Hamiltonian circuits
- 2. Trees 11
- Cayley's theorem
- Spanning trees and the greedy algorithm
- 3. Colorings of graphs and Ramsey's theorem 20
- Brooks' theorem
- Ramsey's theorem and Ramsey numbers
- The Erdos-Szekeres theorem
- 4. Turan's theorem and extremal graphs 29
- Turan's theorem and extremal graph theory
- 5. Systems of distinct representatives 35
- Bipartite graphs
- P. Hall's condition
- SDRs
- Konig's theorem
- Birkhoff's theorem
- 6. Dilworth's theorem and extremal set theory 42
- Partially ordered sets
- Dilworth's theorem
- Sperner's theorem
- Symmetric chains
- The Erdos-Ko-Rado theorem
- 7. Flows in networks 49
- The Ford-Fulkerson theorem
- The integrality theorem
- Ageneralization of Birkhoff's theorem
- 8. De Bruijn sequences 56
- The number of De Bruijn sequences
- 9. The addressing problem for graphs 62
- Quadratic forms
- Winkler's theorem
- 10. The principle of inclusion and exclusion; inversion formulae 70
- Inclusion-exclusion
- Derangements
- Euler indicator
- Mobius function
- Mobius inversion
- Burnside's lemma
- Probleme des menages
- 11. Permanents 79
- Bounds on permanents
- Schrijver's proof of the Minc conjecture
- Fekete's lemma
- Permanents of doubly stochastic matrices
- 12. The Van der Waerden conjecture 91
- The early results of Marcus and Newman
- London's theorem
- Egoritsjev's proof
- 13. Elementary counting; Stirling numbers 100
- Stirling numbers of the first and second kind
- Bell numbers
- Generating functions
- 14. Recursions and generating functions 109
- Elementary recurrences
- Catalan numbers
- Counting of trees
- Joyal theory
- Lagrange inversion
- 15. Partitions 132
- The function Pk(n)
- The partition function
- Ferrers diagrams
- Euler's identity
- Asymptotics
- The Jacobi triple product identity
- Young tableaux and the hook formula
- 16. (0,1)-Matrices 148
- Matrices with given line sums
- Counting (0,1)-matrices
- 17. Latin squares 157
- Orthogonal arrays
- Conjugates and isomorphism
- Partial and incomplete latin squares
- Counting Latin squares
- The Evans conjecture
- 18. Hadamard matrices, Reed-Muller codes 172
- Hadamard matrices and conference matrices
- Recursive constructions
- Paley matrices
- Williamson's method
- Excess of a Hadamard matrix
- First order Reed-Muller codes
- 19. Designs 187
- 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
- 20. Codes and designs 214
- Terminology of coding theory
- The Hamming bound
- The Singleton bound
- Weight enumerators and MacWilliams' theorem
- The Assmus-Mattson theorem
- Symmetry codes
- The Golay codes
- Codes from projective planes
- 21. Strongly regular graphs and partial geometries 231
- The Bose-Mesner algebra
- Eigenvalues
- The integrality condition
- Quasisymmetric designs
- The Krein condition
- The absolute bound
- Uniqueness theorems
- Partial geometries
- 22. Orthogonal Latin squares 250
- Pairwise orthogonal Latin squares and nets
- Euler's conjecture
- The Bose-Parker-Shrikhande theorem
- Asymptotic existence
- Orthogonal arrays and transversal designs
- Dlifference methods, orthogonal subsquares
- 23. Projective and combinatorial geometries 269
- Projective and affine geometries
- Quality
- Pasch's axiom
- Desargues' theorem
- Combinatorial geometries
- Geometric lattices
- Greene's theorem
- 24. Gaussian numbers and q-analogues 291
- Chains in the lattice of subspaces, q-analogue of Sperner's theorem
- Interpretation of the coefficients of the Gaussian polynomials
- Spreads
- 25. Lattices and Mobius inversion
- 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 298
- 26. Combinatorial designs and projective geometries
- Arcs and subplanes in projective planes
- Blocking sets
- Quadratic and Hermitian forms
- Unitals
- Generalized quadrangles
- Mobius planes 313
- 27. Difference sets and automorphisms
- Automorphisms of symmetric designs
- Paley-Todd and Stanton-Sprott difference sets
- Singer's theorem 329
- 28. Difference sets and the group ring
- The Multiplier Theorem and extensions
- Homomorphisms and further necessary conditions 342
- 29. Codes and symmetric designs
- The sequence of codes of a symmetric design
- Wilbrink's theorem 355
- 30. Association schemes
- Examples, the eigenmatrices and orthogonality relations
- Formal duality, the distribution vector of a subset
- Delsarte's inequalities
- Polynomial schemes
- Perfect codes and tight designs 364
- 31. Algebraic graph theory: eigenvalue techniques
- Tournaments and the Graham-Pollak theorem
- The spectrum of a graph
- Hoffman's theorem
- Shannon capacity
- Applications of interlacing and Perron-Frobenius 390
- 32. Graphs: planarity and duality
- Deletion and contraction
- The chromatic polynomial, Euler's formula
- Whitney duality, matroids 403
- 33. Graphs: colorings and embeddings
- The Five Color Theorem, embeddings and colorings on arbitrary surfaces
- The Heawood conjecture
- The Edmonds embedding technique 427
- 34. Electrical networks and squared squares
- The matrix-tree theorem
- The network of a squared rectangle
- Kirchhoff's theorem 449
- 35. Polya theory of counting 461
- The cycle index of a permutation group
- Counting orbits
- Weights, necklaces, the symmetric group
- Stirling numbers 461
- 36. Baranyai's theorem
- One-factorizations of complete graphs and complete designs 475.
- Notes:
- Includes bibliographical references and indexes.
- ISBN:
- 0521410576
- 0521422604
- OCLC:
- 27813322
The Penn Libraries is committed to describing library materials using current, accurate, and responsible language. If you discover outdated or inaccurate language, please fill out this feedback form to report it and suggest alternative language.