Discrete structures and their interactions

Discrete Structures and Their Interactions highlights the connections among various discrete structures, including graphs, directed graphs, hypergraphs, partial orders, finite topologies, and simplicial complexes. It also explores their relationships to classical areas of mathematics, such as linear and multilinear algebra, analysis, probability, logic, and topology.

The text introduces a number of discrete structures, such as hypergraphs, finite topologies, preorders, simplicial complexes, and order ideals of monomials, that most graduate students in combinatorics, and even some researchers in the field, seldom experience. The author explains how these structures have important applications in many areas inside and outside of combinatorics. He also discusses how to recognize valuable research connections through the structures.

Intended for graduate and upper-level undergraduate students in mathematics who have taken an initial course in discrete mathematics or graph theory, this book shows how discrete structures offer new insights into the classical fields of mathematics. It illustrates how to use discrete structures to represent the salient features and discover the underlying combinatorial principles of seemingly unrelated areas of mathematics.

Author Notes

Jason I. Brown is a professor of mathematics at Dalhousie University. He received a Ph.D. from the University of Toronto and has written over 70 refereed articles. His research interests include graphs, hypergraphs, partial order, finite topologies, and simplicial complexes, with a focus on the applications of other fields of mathematics to discrete problems. His mathematical research that uncovered how the Beatles played the opening chord of "A Hard Day's Night" was featured in various media, including NPR and BBC radio, Guitar Player Magazine , and the Wall Street Journal website.

List of Figures	p. xi
Preface	p. xv
About the Author	p. xvii
1 Introduction	p. 1
1.1 Sets	p. 1
1.2 Sequences	p. 2
1.3 Asymptotics	p. 3
1.4 Computational Complexity	p. 3
2 Discrete Structures - A Common Framework	p. 5
2.1 Isomorphism	p. 9
2.2 Substructures	p. 10
2.3 Properties, Parameters and Operations	p. 11
2.4 Representations and Models	p. 12
2.4.1 Geometric Models	p. 13
2.4.2 Algebraic Models	p. 13
2.4.3 Logical Models	p. 16
2.4.4 Probabilistic Models	p. 17
3 Graphs and Directed Graphs	p. 23
3.1 Graphs and Directed Graphs as Models	p. 29
3.1.1 Graph Colourings	p. 29
3.1.2 Reliability	p. 31
3.1.3 Proofs in Matrix Theory	p. 34
3.2 Graphs and Other Branches of Mathematics	p. 38
3.2.1 Graphs and Topology	p. 38
3.2.2 Graphs and Algebra	p. 40
3.2.3 Graphs and Analysis	p. 45
3.2.4 Graphs and Logic	p. 53
3.2.5 Graphs and Probability	p. 55
4 Preorders and Partial Orders	p. 65
4.1 Finite Topologies and Preorders	p. 69
4.1.1 The Correspondence	p. 69
4.1.2 Open Sets	p. 71
4.1.3 The Lattice of All Topologies	p. 72
4.1.4 Algorithmic Considerations	p. 72
4.2 Representing Preorders and Partial Orders	p. 77
4.2.1 Random Preorders and Partial Orders	p. 77
4.2.2 Graphs for Preorders	p. 80
5 Hypergraphs	p. 89
5.1 Applying Hypergraphs	p. 89
5.1.1 Hypergraphs and Graph Colourings	p. 89
5.1.2 Hypergraphs and Generalized Ramsey Theory	p. 93
5.1.3 Designs and Graphs	p. 94
5.1.4 Hypergraphs and Dimension of Partial Orders	p. 99
5.2 Modeling Hypergraphs	p. 102
5.2.1 Criticality and Matrix Rank	p. 102
5.2.2 Criticality and Multilinear Algebra	p. 104
5.2.3 Finite Geometries and Orthogonality	p. 106
5.2.4 Designs from Codes	p. 109
6 Complexes and Multicomplexes	p. 117
6.1 Representations of Complexes and Multicomplexes	p. 126
6.1.1 Topological Realizations of Complexes	p. 126
6.1.2 Connections to Commutative Algebra	p. 130
6.2 Applications of Complexes and Multicomplexes	p. 137
6.2.1 A "Complex" View of. Partial Orders	p. 137
6.2.2 Order Ideals of Monomials and Graph Colourings	p. 139
7 Research Problems	p. 163
Selected Solutions	p. 167
Appendix A Set Theory	p. 171
Appendix B Matrix Theory and Linear Algebra	p. 173
Appendix C Abstract Algebra	p. 175
Appendix D Probability	p. 177
Appendix E Topology	p. 179
Appendix F Logic	p. 181
Bibliography	p. 185
Index	p. 195

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents