Advances in Interdisciplinary Applied Discrete Mathematics (Interdisciplinary Mathematical Sciences)

Annotation. In the past 50 years, discrete mathematics has developed as a far-reaching and popular language for modeling fundamental problems in computer science, biology, sociology, operations research, economics, engineering, etc. The same model may appear in different guises, or a variety of models may have enough similarities such that same ideas and techniques can be applied in diverse applications. This book focuses on fields such as consensus and voting theory, clustering, location theory, mathematical biology, and optimization that have seen an upsurge of new and exciting works over the past two decades using discrete models in modern applications. Featuring survey articles written by experts in these fields, the articles emphasize the interconnectedness of the mathematical models and techniques used in various areas, and elucidate the possibilities for future interdisciplinary research. Additionally, this book discusses recent advances in the fields, highlighting the approach of cross-fertilization of ideas across disciplines Contents......Page 10 Preface......Page 8 Introduction......Page 12 Introduction......Page 16 1.1. Basic Concepts......Page 17 1.2. Potential Compatibility Algorithm......Page 25 1.3. Applications of Compatibility using McMorris' Results......Page 26 1.4. Possible Future Applications......Page 31 References......Page 32 Introduction......Page 36 2.1. Definitions ......Page 37 2.1.1. Preliminaries......Page 38 2.1.2. Type A statistics......Page 39 2.1.3. Type B statistics......Page 40 2.2. Examples of relational statistics for 2 x 2 tables......Page 41 2.2.1. Tetrachoric correlation and odds ratio......Page 42 2.2.2. Epidemiological studies......Page 43 2.2.3. Ecological association......Page 44 2.2.4. Comparing two partitions......Page 45 2.2.5. Test homogeneity......Page 46 2.3.1. Rational functions......Page 47 2.3.2. Chance-corrected statistics......Page 49 2.3.3. Power mean......Page 50 2.3.4. Linear transformations of SSM......Page 52 2.4.2. Inequalities......Page 53 2.4.3. Correction for chance......Page 55 2.4.4. Correction for maximum value......Page 56 References......Page 58 Introduction......Page 64 3.1.1. Basic results on F-tree representations......Page 65 3.1.2. F-tree representations for chordal graphs......Page 67 3.1.3. F-tree representations for other graph classes......Page 68 3.1.4. F-tree representations for distance-hereditary graph......Page 69 3.1.5. Returning to the molecular biology example......Page 70 3.2. Hunter-Worsley/Bonferroni-Type Set Bounds......Page 71 3.2.1. Several classical set bounds......Page 72 3.2.2. Two 2-tree versions of the Hunter-Worsley bound......Page 73 3.2.3. The chordal graph sieve......Page 75 3.2.4. Economical inclusion-exclusion......Page 78 References......Page 79 Introduction......Page 82 4.1. The model......Page 84 4.2. Basic Axioms......Page 85 4.3. The Center Function......Page 87 4.4. The median Function......Page 88 4.4.1. The Median Function on Median Graphs......Page 89 4.4.2. The t-Median Function on Median Semilattices......Page 91 4.4.3. The Median Function on Cube-free Median Networks......Page 94 4.5. The Mean Function on Trees......Page 99 4.6. Concluding Remarks......Page 100 References......Page 101 Introduction......Page 104 5.1. Definitions and Preliminaries......Page 106 5.2. The Expansion Theorem......Page 108 5.3. The Armchair......Page 111 5.4. Median Sets in Median Graphs......Page 113 5.5. Median Graphs in the Mathematical Universe......Page 116 5.6.1. Ternary algebras......Page 117 5.6.3. Semilattices......Page 118 5.6.4. Hypergraphs and convexities......Page 119 5.6.6. Conflict models......Page 120 5.6.7. Transit Functions......Page 121 5.7.1. Quasi-median Graphs......Page 122 5.7.2. Expansions......Page 124 5.7.4. Median-type Graphs......Page 125 5.7.5. Transit Functions......Page 126 5.8. Applications......Page 127 5.8.1. Location Theory......Page 128 5.8.3. Chemistry......Page 129 5.8.5. Literary History......Page 131 5.8.6. Economics and Voting Theory......Page 132 References......Page 133 Introduction......Page 138 6.1. Preliminaries......Page 140 6.2. Generalized path centers and path centroids......Page 142 6.3. Generalized path medians......Page 151 6.4. Conclusions......Page 156 References......Page 157 Introduction......Page 160 7.1. The Monjardet Model of Consensus......Page 161 7.2. Absolute Majority Rules......Page 165 7.3. Social Welfare Functions......Page 171 7.4. Conclusion......Page 175 References......Page 176 Introduction......Page 178 8.2. The Median......Page 183 8.3. Two more central sets that induce K1 or K2......Page 187 8.4. Families of central sets inducing K1 or K2......Page 188 8.5. Central subtrees......Page 194 8.6. Disconnected central sets......Page 201 8.7. Connected central structures......Page 203 References......Page 205 Introduction......Page 210 9.1. Formalizing the Problem......Page 211 9.2. Penalty Functions......Page 213 9.3. The Case of Common Desired Arrival Times......Page 215 9.5. Meaningful Conclusions......Page 216 9.6. Closing Comments......Page 218 References......Page 219 10.1. The problem......Page 222 10.2. Arrow's Theorem and surprising extensions......Page 223 10.3. Still another vote......Page 225 10.4. Finding the actual space of inputs......Page 228 10.4.1. Outline of Arrow's result where "involvement" replaces Pareto......Page 229 10.4.2. Finding the problem......Page 230 10.4.3. Other compatibility and independence conditions......Page 231 10.4.4. Positive conclusions?......Page 232 References......Page 233 Introduction......Page 236 11.1. Mathematics of Evolutionary Biology......Page 237 11.2. Contributions to Intersection Graph Theory......Page 239 11.3.1. Competition Graph Definitions and Applications......Page 240 11.3.2. Competition Numbers and Phylogeny Numbers......Page 242 11.3.3. p-Competition Graphs......Page 243 11.4. Location Functions on Graphs......Page 244 11.5. Contributions to Bioconsensus: An Axiomatic Approach......Page 247 References......Page 249 Author Index......Page 254 Subject Index......Page 260 Symbol Index......Page 268 Contributions of F. R. McMorris to character compatibility analysis / G.F. Estabrook Families of relational statistics for 2 x 2 tables / W. J. Heiser and M. J. Warrens Applications of spanning subgraphs of intersection graphs / Terry A. McKee Axiomatic characterization of location functions / F. R. McMorris, H. M. Mulder and R. V. Vohra Median graphs. A structure theory / H. M. Mulder Generalized centrality in trees / M. J. Pelsmajer and K. B. Reid Consensus centered at majority rule / R. C. Powers Centrality measures in trees / K. B. Reid The port reopening scheduling problem / F. S. Roberts Reexamining the complexities in consensus theory / D. G. Saari The contributions of F. R. McMorris to discrete mathematics and its applications / G. F. Estabrook ... [et al.]. Focuses on fields such as consensus and voting theory, clustering, location theory, mathematical biology, and optimization that have seen an upsurge of exciting works over the years using discrete models in modern applications. This book discusses advances in the fields, highlighting the approach of cross-fertilization of ideas across disciplines.