Semispaces of configurations, cell complexes of arrangements.

*(English)*Zbl 0551.05002From the authors’ introduction: ”In [J. Comb. Theory, Ser. A 29, 220-235 (1980; Zbl 0448.05016)] and [Geom. Dedicata 12, 63-74 (1982; Zbl 0494.51002)] we introduced the idea of associating to each numbered configuration of n points, as well as to each numbered arrangement of n lines, a circular sequence of permutations of \(\{\) 1,...,n\(\}\), which encodes in combinatorial terms the orientation properties of the configuration or arrangement; this device has since proven fruitful in solving a number of open problems on configurations and arrangements. The same combinatorial tool, which we call an allowable sequence of permutations, can be used to study equivalence relations on configurations and arrangements as well, and this is what we do in the present paper. Our results include: (i) a criterion, in terms of their associated sequences of permutations, for two numbered configurations of points to be semispace-equivalent, and a related criterion, also in terms of allowable sequences, for two numbered arrangements of lines (or pseudolines) to give rise to isomorphic cell complexes; (ii) a combinatorial characterization of the cell complexes determined by arrangements of pseudolines; (iii) the solution of a discrete version of the isotopy problem; and (iv) the result that if, for a configuration \(\{P_ 1,...,P_ n\}\), one knows how many points lie to the left of each directed line \(P_ iP_ j\), then one can reconstruct precisely which ones do. We end the paper with some open problems.”

Reviewer: J.Libicher

##### MSC:

05A05 | Permutations, words, matrices |

51-02 | Research exposition (monographs, survey articles) pertaining to geometry |

05-02 | Research exposition (monographs, survey articles) pertaining to combinatorics |

51A99 | Linear incidence geometry |

05B25 | Combinatorial aspects of finite geometries |

##### Keywords:

allowable sequence of permutations; numbered configurations of points; arrangements of lines
PDF
BibTeX
XML
Cite

\textit{J. E. Goodman} and \textit{R. Pollack}, J. Comb. Theory, Ser. A 37, 259--293 (1984; Zbl 0551.05002)

Full Text:
DOI

##### References:

[1] | \scJ. R. Alexander, R. L. Bishop, and J. E. Witzel, Indexed arrangements and ordered tableaux, preprint. |

[2] | Bland, R.G; Las Vergnas, M, Orientability of matroids, J. combin. theory ser. B, 24, 94-123, (1978) · Zbl 0374.05016 |

[3] | Cordovil, R, Sur LES matroïdes orientés de rang trois et LES arrangements de pseudodroites dans le plan projectif réel, European J. combin., 3, 307-318, (1982) · Zbl 0501.05021 |

[4] | \scA. S. Dreiding, A. Dress, and H. R. Haegi, Chirotopes, a combinatorial theory of orientation, preprint. |

[5] | \scH. Edelsbrunner and E. Welzl, On the number of line-separations of a finite set in the plane, J. Combin. Theory Ser. A, in press. · Zbl 0616.52003 |

[6] | Folkman, J; Lawrence, J, Oriented matroids, J. combin. theory ser. B, 25, 199-236, (1978) · Zbl 0325.05019 |

[7] | Goodman, J.E, Proof of a conjecture of burr, grünbaum, and sloane, Discrete math., 32, 27-35, (1980) · Zbl 0444.05029 |

[8] | Goodman, J.E; Pollack, R, On the combinatorial classification of nondegenerate configurations in the plane, J. combin. theory ser. A, 29, 220-235, (1980) · Zbl 0448.05016 |

[9] | Goodman, J.E; Pollack, R, A theorem of ordered duality, Geom. dedicata, 12, 63-74, (1982) · Zbl 0494.51002 |

[10] | Goodman, J.E; Pollack, R, Proof of grünbaum’s conjecture on the stretchability of certain arrangements of pseudolines, J. combin. theory ser. A, 29, 385-390, (1980) · Zbl 0457.51006 |

[11] | Goodman, J.E; Pollack, R, Helly-type theorems for pseudoline arrangements in P2, J. combin. theory ser. A, 32, 1-19, (1982) · Zbl 0488.52007 |

[12] | Goodman, J.E; Pollack, R, Three points do not determine a (pseudo-) plane, J. combin. theory ser. A, 31, 215-218, (1981) · Zbl 0479.51002 |

[13] | Goodman, J.E; Pollack, R, A combinatorial perspective on some problems in geometry, (), 383-394 |

[14] | Goodman, J.E; Pollack, R, Multidimensional sorting, SIAM J. comp., 12, 484-507, (1983) · Zbl 0525.68038 |

[15] | \scJ. E. Goodman and R. Pollack, A discrete version of the isotopy conjecture, in “Discrete Geometry and Convexity,” New York Academy of Sciences, in press. · Zbl 0578.52002 |

[16] | Goodman, J.E; Pollack, R, On the number of k-subsets of a set of n points in the plane, J. combin. theory ser. A, 36, 101-104, (1984) · Zbl 0523.51003 |

[17] | Grünbaum, B, Arrangements and spreads, (), No. 10 · Zbl 0249.50011 |

[18] | Levi, F, Die teilung der projektiven ebene durch gerade oder pseudogerade, Ber. verh. Sächs. gesellsch. wiss. Leipzig math. phys. kl., 78, 256-267, (1926) · JFM 52.0575.01 |

[19] | \scR. Jamison, A survey of the slopes problem, in “Discrete Geometry and Convexity,” New York Academy of Sciences, in press. |

[20] | Moise, E, Geometric topology in dimensions 2 and 3, (1977), Springer-Verlag New York · Zbl 0349.57001 |

[21] | Ringel, G, Teilungen der ebene durch geraden oder topologische geraden, Math. Z., 64, 79-102, (1956) · Zbl 0070.16108 |

[22] | R. Stanley, On the number of reduced decompositions of elements of Coxeter groups, European J. Combin., in press. · Zbl 0587.20002 |

[23] | Ungar, P, 2N noncollinear points determine at least 2N directions, J. combin. theory ser. A, 33, 343-347, (1982) · Zbl 0496.05001 |

[24] | \scT. Zaslavsky, Combinatorial ordered geometry. I. Bilateral geometry, preprint. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.