Pattern Recognition on Oriented Matroids / Edition 1

by Andrey O. Matveev

Overview

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

Product Details

ISBN-13:	9783110530711
Publisher:	De Gruyter
Publication date:	09/11/2017
Pages:	231
Product dimensions:	6.69(w) x 9.45(h) x (d)
Age Range:	18 Years

About the Author

Andrey O. Matveev, Ekaterinburg, Russian Federation.

Table of Contents

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 1

Arrangements of Oriented Linear Hyperplanes and Committees of Regions 3

Realizable Simple Oriented Matroids and Tope Committees 3

1 Oriented Matroids, the Pattern Recognition Problem, and Tope Committees 5

1.1 Preliminaries 5

1.2 Pattern Recognition on Oriented Matroids -10

1.3 The Existence of a Tope Committee: Reorientations 17

1.4 Graphs Related to Tope Committees 29

1.5 Selected Mathematical Concepts and Tools for an Analysis of Infeasible Systems of Constraints 39

Notes 50

2 Boolean Intervals 54

2.1 Long f- and h-Vectors of Face Systems 55

2.2 Face Systems, Distinguished Bases, and Change of Basis Matrices 58

2.3 Partitions of Face Systems into Boolean Intervals, and the Long f- and h-Vectors. Dehn-Sommerville Type Relations 62

Notes 65

3 Dehn-Sommerville Type Relations 67

3.1 Dehn-Sommerville Type Relations for the Long h-Vectors 67

3.2 Dehn-Sommerville Type Relations for the Long f-Vectors 70

3.3 The Long f-Vectors of DS-Systems, and Integer Points in Rational Convex Polytopes 72

3.4 The Long h-Vectors of DS-Systems, and Integer Points in Rational Convex Polytopes 78

Notes 81

4 Farey Subsequences 82

4.1 The Farey Subsequence F(B(n), m) 83

4.2 The Farey Subsequence F(B(2m), m) 84

4.3 Farey Duality 85

Notes 87

5 Blocking Sets of Set Families, and Absolute Blocking Constructions in Posets 88

5.1 Blocking Elements and Complementing Elements of Subposets 90

5.2 Blocking Elements in Direct Products of Posets 93

5.3 The Blocker Map and the Complementary Map on Antichains 94

5.4 The Lattice of Blockers 97

5.5 Deletion and Contraction 99

5.6 The Blocker, Deletion, Contraction, and Maps on Posets 103

5.7 The Blocker, Deletion, Contraction, Powers of 2, and the Self-Dual Clutters 106

5.8 The(X, K)-Blocker Map 108

5.9 (X, K)-Deletion and (X, K)-Contraction 112

Notes 116

6 Committees of Set Families, and Relative Blocking Constructions in Posets 118

6.1 Relatively Blocking Elements of Antichains 119

6.2 Absolutely Blocking Elements of Antichains, and Convex Subposets 122

6.3 A Connection Between Absolute and Relative Blocking Constructions 127

6.4 The Structure of the Subposets of Relatively Blocking Elements, and Their Enumeration 127

6.5 Principal Order Ideals and Farey Subsequences 130

6.6 Relatively Blocking Elements in Graded Posets, and Farey Subsequences 132

6.7 Relatively Blocking Elements in the Boolean Lattices 134

6.8 Relatively Blocking Elements b with the Property b Λ -b = ô in the Boolean Lattices of Subsets of the Sets ±{1,…, m} 136

6.9 Relatively Blocking Elements in the Posets Isomorphic to the Face Lattices of Crosspolytopes 138

6.10 Relatively Blocking Elements in the Principal Order Ideals of Binomial Posets 140

Notes 142

7 Layers of Tope Committees 143

7.1 Layers of Tope Committees, and Relatively Blocking Elements in the Boolean Lattice of Tope Subsets 143

7.2 Layers of Tope Committees, and Relatively Blocking Elements in the Poset of Tope Subsets Containing No Pairs of Opposites 146

Notes 149

8 Three-Tope Committees 150

8.1 Three-Tope Committees and Anti-committees 150

8.2 Committees of Size 3 Whose Topes Have Maximal Positive Parts 153

Notes 156

9 Halfspaces, Convex Sets, and Tope Committees 157

9.1 Halfspaces and Tope Committees 159

9.2 Convex Sets and Tope Committees 162

9.3 Tope Committees Containing No Pairs of Opposites 164

Notes 166

10 Tope Committees and Reorientations of Oriented Matroids 167

10.1 The Number of Tope Committees 168

10.2 The Number of Tope Committees Containing No Pairs of Opposites 169

10.3 Tope Committees and Reorientations of Oriented Matroids on One-Element Subsets of the Ground Sets 171

Note 173

11 Topes and Critical Committees 174

11.1 Symmetric Cycles in the Tope Graph, and Maximal Positive Bases of R^t 174

11.2 Topes and Critical Committees 176

Notes 180

12 Critical Committees and Distance Signals 181

12.1 The Distance Signal of a Symmetric Cycle in the Tope Graph 181

12.2 Critical Committees and Distance Signals 184

Notes 187

13 Symmetric Cycles in the Hypercube Graphs 188

13.1 Decompositions of Topes with Respect to Symmetric Cycles in the Tope Graphs 189

13.2 Basic Metric Properties of Decompositions 192

13.3 Symmetric Cycles in the Hypercube Graphs 194

Notes 197

Bibliography 199

List of Notation 209

Index 217