Combinatorial Theory

by Hall, Marshall

• ISBN13: 9780471315186
• ISBN10: 0471315184
• Edition: 2nd
• Format: Paperback
• Copyright: 1998-07-16
• Publisher: Wiley-Interscience

Summary

Includes proof of van der Waerden's 1926 conjecture on permanents, Wilson's theorem on asymptotic existence, and other developments in combinatorics since 1967. Also covers coding theory and its important connection with designs, problems of enumeration, and partition. Presents fundamentals in addition to latest advances, with illustrative problems at the end of each chapter. Enlarged appendixes include a longer list of block designs.

Author Biography

Marshall Hall is the author of Combinatorial Theory, 2nd Edition, published by Wiley.

Table of Contents

Permutations And Combinations	1	(7)
Definitions	1	(3)
Applications to Probability	4	(4)
Problems	6	(2)
Inversion Formulae	8	(12)
The Principle of Inclusion and Exclusion. Mobius Inversion	8	(7)
Partially Ordered Sets and Their Mobius Functions	15	(5)
Problems	18	(2)
Generating Functions And Recursions	20	(11)
Rules and Properties	20	(4)
Combinatorial Problems	24	(7)
Problems	28	(3)
Partitions	31	(17)
Partitions. Identities and Arithmetic Properties	31	(12)
Asymptotic Properties of p(n)	43	(5)
Problems	46	(2)
Distinct Representatives	48	(25)
The Theorems of P. Hall and D. Konig	48	(8)
The Permanent	56	(2)
Proof of the van der Waerden Conjecture	58	(11)
Permanents of Integral Matrices with Constant Line Sum	69	(4)
Problems	72	(1)
Ramsey's Theorem	73	(4)
Statement of the Theorem	73	(1)
Application of Ramsey's Theorem	74	(3)
Problems	75	(2)
Some Extremal Problems	77	(8)
The Assignment Problem	77	(4)
Dilworth's Theorem	81	(4)
Problems	84	(1)
Convex Spaces And Linear Programming	85	(25)
Convex Spaces. Convex Cones and Their Duals	85	(4)
Linear Inequalities	89	(7)
Linear Programming. The Simplex Method	96	(14)
Graphical Methods. Debruijn Sequences	110	(16)
Complete Cycles	110	(2)
Theorems on Graphs	112	(2)
Proof of the DeBruijn Theorem	114	(4)
Strongly Regular Graphs	118	(4)
Finite Permutation Groups of Rank 3	122	(4)
Block Designs	126	(21)
General Discussion	126	(3)
Elementary Theorems on Block Design	129	(4)
The Bruck - Ryser - Chowla Theorem	133	(6)
Statement of the Hasse - Minkowski Theorem. Applications	139	(8)
Difference Sets	147	(52)
Examples and Definitions	147	(3)
Finite Fields	150	(5)
The Theorem of Singer	155	(4)
The Multiplier Theorem	159	(5)
Difference Sets in General Groups	164	(6)
Some Families of Difference Sets	170	(29)
Finite Geometries	199	(23)
Foundations	199	(4)
Finite Geometries as Block Designs	203	(2)
Finite Planes	205	(6)
Some Types of Finite Planes	211	(11)
Orthogonal Latin Squares	222	(16)
Orthogonality and Orthogonal Arrays	222	(1)
Main Theorems	223	(5)
Constructions of Orthogonal Squares	228	(6)
The End of the Euler Conjecture	234	(4)
Hadamard Matrices	238	(26)
Paley's Constructions	238	(16)
Williamson's Method	254	(3)
An Infinite Class of Williamson Matrices	257	(4)
Three Recent Methods	261	(3)
General Constructions Of Block Designs	264	(72)
Methods of Construction	264	(1)
Basic Definitions. The Hanani Theorems	264	(7)
Direct Construction Methods	271	(6)
Triple Systems	277	(12)
Block Designs with k Greater Than 3	289	(4)
Wilson's Theorem	293	(12)
Some Infinite Families of Designs	305	(15)
Biplanes	320	(16)
Theorems On Completion And Embedding	336	(40)
Connor's Method	336	(12)
Copositive and Completely Positive Quadratic Forms	348	(11)
Rational Completions of Incidence Matrices	359	(9)
Integral Solutions of the Incidence Equation	368	(8)
Coding Theory And Block Designs	376	(29)
Error Correcting Codes	376	(1)
Weight Enumerators. The MacWilliams Equations	377	(4)
Applications of Codes to Designs. General Theory	381	(5)
Group Invariants. Gleason's Theorem and Its Generalizations	386	(4)
Applications to Planes of Order 10	390	(9)
The Symmetric (41, 16, 6) Design	399	(6)
Appendix I Balanced Incomplete Block Designs with from 3 to 20 Replications	405	(19)
Appendix II Hadamard Matrices of the Williamson Type	424	(4)
Bibliography	428	(9)
Index	437