Caspard Nathalie - Finite ordered sets : concepts, results and uses

FINITE ORDERED SETS Concepts, Results and Uses Ordered sets are ubiquitous in mathematics and have significant applications in computer science, statistics, biology, and the social sciences. As the first book to deal exclusively with finite ordered sets, this book will be welcomed by graduate students and researchers in all of these areas. Beginning with definitions of key concepts and fundamental results (Dilworths and Sperners theorem, interval and semiorders, Galois connection, duality with distributive lattices, coding and dimension theory), the authors then present applications of these structures in fields such as preference modeling and aggregation, operational research and management, cluster and concept analysis, and data mining. Exercises are included at the end of each chapter with helpful hints provided for some of the most difficult examples. The authors also point to further topics of ongoing research. Encyclopedia of Mathematics and Its Applications This series is devoted to significant topics or themes that have wide application in math ematics or mathematical science and for which a detailed development of the abstract theory is less important than a thorough and concrete exploration of the implications and applications.

Books in the Encyclopedia of Mathematics and Its Applications cover their subjects comprehensively. Less important results may be summarized as exercises at the ends of chapters. For technicalities, readers can be referred to the reference list, which is expected to be comprehensive. As a result, volumes are encyclopedic references or manageable guides to major subjects. e n c y c l o p e d i a o f m a t h e m a t i c s a n d i t s a p p l i c a t i o n s All the titles listed below can be obtained from good booksellers or from Cambridge University Press. 91 A. A. A.

Ivanov and S. V. Shpectorov Geometry of Sporadic Groups II 92 P. McMullen and E. Schulte Abstract Regular Polytopes 93 G. Gierz et al.

Continuous Lattices and Domains 94 S. R. Finch Mathematical Constants 95 Y. Jabri The Mountain Pass Theorem 96 G. Gasper and M. C. C.

Pedicchio and W. Tholen (eds.) Categorical Foundations 98 M. E. H. Ismail Classical and Quantum Orthogonal Polynomials in One Variable 99 T. Mora Solving Polynomial Equation Systems II 100 E.

Olivieri and M. Eullia Vares Large Deviations and Metastability 101 A. Kushner, V. Lychagin and V. Rubtsov Contact Geometry and Nonlinear Differential Equations 102 L. W.

Beineke and R. J. Wilson (eds.) with P. J. Cameron Topics in Algebraic Graph Theory 103 O. J.

Staffans Well-Posed Linear Systems 104 J. M. Lewis, S. Lakshmivarahan and S. K. Dhall Dynamic Data Assimilation 105 M.

Lothaire Applied Combinatorics on Words 106 A. Markoe Analytic Tomography 107 P. A. Martin Multiple Scattering 108 R. A. M. M.

Borwein and J. D. Vanderwerff Convex Functions 110 M.-J. Lai and L. L. T. T.

Curtis Symmetric Generation of Groups 112 H. Salzmann, et al. The Classical Fields 113 S. Peszat and J. Zabczyk Stochastic Partial Differential Equations with Lvy Noise 114 J. Beck Combinatorial Games 115 L.

Barreira and Y. Pesin Nonuniform Hyperbolicity 116 D. Z. Arov and H. Dym J-Contractive Matrix Valued Functions and Related Topics 117 R. Glowinski, J.-L.

Lions and J. He Exact and Approximate Controllability for Distributed Parameter Systems 118 A. A. Borovkov and K. A. Borovkov Asymptotic Analysis of Random Walks 119 M.

Deza and M. Dutour Sikiri Geometry of Chemical Graphs 120 T. Nishiura Absolute Measurable Spaces 121 M. Prest Purity, Spectra and Localisation 122 S. Khrushchev Orthogonal Polynomials and Continued Fractions 123 H. Nagamochi and T.

Ibaraki Algorithmic Aspects of Graph Connectivity 124 F. W. King Hilbert Transforms I 125 F. W. King Hilbert Transforms II 126 O. Calin and D.-C.

Chang Sub-Riemannian Geometry 127 M. Grabisch et al. Aggregation Functions 128 L. W. Beineke and R. J.

Wilson (eds) with J. L. Gross and T. W. Tucker Topics in Topological Graph Theory 129 J. Berstel, D.

Perrin and C. Reutenauer Codes and Automata 130 T. G. Faticoni Modules over Endomorphism Rings 131 H. Morimoto Stochastic Control and Mathematical Modeling 132 G. Schmidt Relational Mathematics 133 P.

Kornerup and D. W. Matula Finite Precision Number Systems and Arithmetic 134 Y. Crama and P. L. Hammer (eds.) Boolean Models and Methods in Mathematics, Computer Science, andEngineering 135 V.

Berth and M. Rigo (eds.) Combinatorics, Automata and Number Theory 136 A. Kristly, V. D. Radulescu and C. Varga Variational Principles in Mathematical Physics, Geometry, andEconomics 137 J.

Berstel and C. Reutenauer Noncommutative Rational Series with Applications 138 B. Courcelle and J. Engelfriet Graph Structure and Monadic Second-Order Logic 139 M. Fiedler Matrices and Graphs in Geometry 140 N. B. B.

Paris Hadamard Expansions and Hyperasymptotic Evaluation 142 Y. Crama and P. L. Hammer Boolean Functions 143 A. Arapostathis, V. S.

Borkar and M. K. Ghosh Ergodic Control of Diffusion Processes e n c y c l o p e d i a o f m a t h e m a t i c s a n d i t s a p p l i c a t i o n s Finite Ordered Sets Concepts, Results and Uses N AT H A L I E C A S PA R D Universit Paris-Est Crteil (UPEC) B R U N O L E C L E R C cole des Hautes tudes en Sciences Sociales (EHESS) B E R N A R D M O N J A R D E T Universit Paris I Panthon Sorbonne C A M B R I D G E U N I V E R S I T Y P R E S S Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, So Paulo, Delhi, Tokyo, Mexico City Cambridge University Press The Edinburgh Building, Cambridge CB2 8RU, UK Published in the United States of America by Cambridge University Press, New York www.cambridge.org Information on this title: www.cambridge.org/9781107013698 N. Caspard, B. Leclerc and B. Monjardet 2012 This publication is in copyright.

Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published 2012 Printed in the United Kingdom at the University Press, Cambridge A catalogue record for this publication is available from the British LibraryLibrary of Congress Cataloguing in Publication data Caspard, Nathalie. Finite ordered sets / Nathalie Caspard, Bruno Leclerc, Bernard Monjardet. p. cm. (Encyclopedia of mathematics and its applications ; 144) Includes bibliographical references and index.

ISBN 978-1-107-01369-8 (hardback) 1. Ordered sets. 2. Finite groups. I. II. II.

Monjardet, Bernard, 1938 III. Title. QA171.48.C374 2012 511.32dc23 2011040516 ISBN 978-1-107-01369-8 Hardback Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. Contents PrefacepageConcepts and examples 1.1 Ordered sets 1.2 Examples of uses 1.3 Ordered subsets and extensions 1.4 Particular elements and subsets 1.5 Constructing ordered sets from given ones 1.6 Further topics and references 1.7 Exercises