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.
Author(s): Hemanshu Kaul
Series: Interdisciplinary Mathematical Sciences
Publisher: World Scientific Publishing Company
Year: 2010
Language: English
Pages: 273
Tags: Математика;Дискретная математика;
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
