O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Pattern Recognition on Oriented Matroids

Book Description

Pattern Recognition on Oriented Matroids covers a range of innovative problems in combinatorics, poset and graph theories, optimization, and number theory that constitute a far-reaching extension of the arsenal of committee methods in pattern recognition. The groundwork for the modern committee theory was laid in the mid-1960s, when it was shown that the familiar notion of solution to a feasible system of linear inequalities has ingenious analogues which can serve as collective solutions to infeasible systems. A hierarchy of dialects in the language of mathematics, for instance, open cones in the context of linear inequality systems, regions of hyperplane arrangements, and maximal covectors (or topes) of oriented matroids, provides an excellent opportunity to take a fresh look at the infeasible system of homogeneous strict linear inequalities – the standard working model for the contradictory two-class pattern recognition problem in its geometric setting. The universal language of oriented matroid theory considerably simplifies a structural and enumerative analysis of applied aspects of the infeasibility phenomenon.

The present book is devoted to several selected topics in the emerging theory of pattern recognition on oriented matroids: the questions of existence and applicability of matroidal generalizations of committee decision rules and related graph-theoretic constructions to oriented matroids with very weak restrictions on their structural properties; a study (in which, in particular, interesting subsequences of the Farey sequence appear naturally) of the hierarchy of the corresponding tope committees; a description of the three-tope committees that are the most attractive approximation to the notion of solution to an infeasible system of linear constraints; an application of convexity in oriented matroids as well as blocker constructions in combinatorial optimization and in poset theory to enumerative problems on tope committees; an attempt to clarify how elementary changes (one-element reorientations) in an oriented matroid affect the family of its tope committees; a discrete Fourier analysis of the important family of critical tope committees through rank and distance relations in the tope poset and the tope graph; the characterization of a key combinatorial role played by the symmetric cycles in hypercube graphs.

Contents
Oriented Matroids, the Pattern Recognition Problem, and Tope Committees
Boolean Intervals
Dehn–Sommerville Type Relations
Farey Subsequences
Blocking Sets of Set Families, and Absolute Blocking Constructions in Posets
Committees of Set Families, and Relative Blocking Constructions in Posets
Layers of Tope Committees
Three-Tope Committees
Halfspaces, Convex Sets, and Tope Committees
Tope Committees and Reorientations of Oriented Matroids
Topes and Critical Committees
Critical Committees and Distance Signals
Symmetric Cycles in the Hypercube Graphs

Table of Contents

  1. Cover
  2. Title page
  3. Copyright
  4. Dedication
  5. Contents
  6. Committees for Pattern Recognition: Infeasible Systems of Linear Inequalities, Hyperplane Arrangements, and Realizable Oriented Matroids
    1. Infeasible Systems of Homogeneous Strict Linear Inequalities and Their Committees
    2. Arrangements of Oriented Linear Hyperplanes and Committees of Regions
    3. Realizable Simple Oriented Matroids and Tope Committees
  7. 1 Oriented Matroids, the Pattern Recognition Problem, and Tope Committees
    1. 1.1 Preliminaries
    2. 1.2 Pattern Recognition on Oriented Matroids
    3. 1.3 The Existence of a Tope Committee: Reorientations
    4. 1.4 Graphs Related to Tope Committees
    5. 1.5 Selected Mathematical Concepts and Tools for an Analysis of Infeasible Systems of Constraints
    6. Notes
  8. 2 Boolean Intervals
    1. 2.1 Long f- and h-Vectors of Face Systems
    2. 2.2 Face Systems, Distinguished Bases, and Change of Basis Matrices
    3. 2.3 Partitions of Face Systems into Boolean Intervals, and the Long f- and h-Vectors. Dehn–Sommerville Type Relations
    4. Notes
  9. 3 Dehn–Sommerville Type Relations
    1. 3.1 Dehn–Sommerville Type Relations for the Long h-Vectors
    2. 3.2 Dehn–Sommerville Type Relations for the Long f-Vectors
    3. 3.3 The Long f-Vectors of DS-Systems, and Integer Points in Rational Convex Polytopes
    4. 3.4 The Long h-Vectors of DS-Systems, and Integer Points in Rational Convex Polytopes
    5. Notes
  10. 4 Farey Subsequences
    1. 4.1 The Farey Subsequence f (B(n), m)
    2. 4.2 The Farey Subsequence f (B(2m), m)
    3. 4.3 Farey Duality
    4. Notes
  11. 5 Blocking Sets of Set Families, and Absolute Blocking Constructions in Posets
    1. 5.1 Blocking Elements and Complementing Elements of Subposets
    2. 5.2 Blocking Elements in Direct Products of Posets
    3. 5.3 The Blocker Map and the Complementary Map on Antichains
    4. 5.4 The Lattice of Blockers
    5. 5.5 Deletion and Contraction
    6. 5.6 The Blocker, Deletion, Contraction, and Maps on Posets
    7. 5.7 The Blocker, Deletion, Contraction, Powers of 2, and the Self-Dual Clutters
    8. 5.8 The (X, k)-Blocker Map
    9. 5.9 (X, k)-Deletion and (X, k)-Contraction
    10. Notes
  12. 6 Committees of Set Families, and Relative Blocking Constructions in Posets
    1. 6.1 Relatively Blocking Elements of Antichains
    2. 6.2 Absolutely Blocking Elements of Antichains, and Convex Subposets
    3. 6.3 A Connection Between Absolute and Relative Blocking Constructions
    4. 6.4 The Structure of the Subposets of Relatively Blocking Elements, and Their Enumeration
    5. 6.5 Principal Order Ideals and Farey Subsequences
    6. 6.6 Relatively Blocking Elements in Graded Posets, and Farey Subsequences
    7. 6.7 Relatively Blocking Elements in the Boolean Lattices
    8. 6.8 Relatively Blocking Elements b with the Property b ∧ −b = Ô in the Boolean Lattices of Subsets of the Sets ±{1, . . ., m}
    9. 6.9 Relatively Blocking Elements in the Posets Isomorphic to the Face Lattices of Crosspolytopes
    10. 6.10 Relatively Blocking Elements in the Principal Order Ideals of Binomial Posets
    11. Notes
  13. 7 Layers of Tope Committees
    1. 7.1 Layers of Tope Committees, and Relatively Blocking Elements in the Boolean Lattice of Tope Subsets
    2. 7.2 Layers of Tope Committees, and Relatively Blocking Elements in the Poset of Tope Subsets Containing No Pairs of Opposites
    3. Notes
  14. 8 Three-Tope Committees
    1. 8.1 Three-Tope Committees and Anti-committees
    2. 8.2 Committees of Size 3 Whose Topes Have Maximal Positive Parts
    3. Notes
  15. 9 Halfspaces, Convex Sets, and Tope Committees
    1. 9.1 Halfspaces and Tope Committees
    2. 9.2 Convex Sets and Tope Committees
    3. 9.3 Tope Committees Containing No Pairs of Opposites
    4. Notes
  16. 10 Tope Committees and Reorientations of Oriented Matroids
    1. 10.1 The Number of Tope Committees
    2. 10.2 The Number of Tope Committees Containing No Pairs of Opposites
    3. 10.3 Tope Committees and Reorientations of Oriented Matroids on One-Element Subsets of the Ground Sets
    4. Notes
  17. 11 Topes and Critical Committees
    1. 11.1 Symmetric Cycles in the Tope Graph, and Maximal Positive Bases of Rt
    2. 11.2 Topes and Critical Committees
    3. Notes
  18. 12 Critical Committees and Distance Signals
    1. 12.1 The Distance Signal of a Symmetric Cycle in the Tope Graph
    2. 12.2 Critical Committees and Distance Signals
    3. Notes
  19. 13 Symmetric Cycles in the Hypercube Graphs
    1. 13.1 Decompositions of Topes with Respect to Symmetric Cycles in the Tope Graphs
    2. 13.2 Basic Metric Properties of Decompositions
    3. 13.3 Symmetric Cycles in the Hypercube Graphs
    4. Notes
  20. Bibliography
  21. List of Notation
  22. Index