Разделение пространства гиперплоскостями

Введение

Разделение пространства гиперплоскостями
В геометрии и комбинаторике расположение гиперплоскостей — это расположение конечного множества гиперплоскостей A в линейном, аффинном или проективном пространстве S.
Вопросы, касающиеся расположения гиперплоскостей A, обычно связаны с геометрическими, топологическими или другими свойствами комплемента, M(A), который представляет собой множество, остающееся после удаления гиперплоскостей из всего пространства. Можно задаться вопросом, как эти свойства связаны с самим расположением и его полурешеткой пересечений. Полурешетка пересечений A, обозначаемая L(A), — это множество всех подпространств, получаемых в результате пересечения некоторых гиперплоскостей; среди этих подпространств находятся само S, все отдельные гиперплоскости, все пересечения пар гиперплоскостей и т. д. (за исключением, в аффинном случае, пустого множества). Эти подпространства пересечения также называются плоскими элементами A. Полурешетка пересечений L(A) частично упорядочена по отношению к обратному включению. Если все пространство S двумерно, гиперплоскости являются прямыми; такое расположение часто называют расположением прямых. Исторически первыми исследованными были расположения прямых в вещественном пространстве. Если S трехмерно, то мы имеем расположение плоскостей.

Пересечение полуметалла и матроя

Полурешетка пересечений L(A) является полурешеткой объединений и, в частности, геометрической полурешеткой. Если расположение линейное или проективное, или если пересечение всех гиперплоскостей непусто, то решетка пересечений является геометрической решеткой. (Именно поэтому полурешетка должна быть упорядочена обратным включением, а не включением, которое может показаться более естественным, но не даст геометрическую (полу)решетку.) Когда L(A) является решеткой, матроид, порожденный A, обозначаемый M(A), имеет A в качестве базового множества и функцию ранга r(S) := codim(I), где S – любое подмножество A, а I – пересечение гиперплоскостей из S. В общем случае, когда L(A) является полурешеткой, существует аналогичная матроидная структура, называемая полуматроидом, которая является обобщением матроида (и имеет ту же связь с полурешеткой пересечений, что и матроид с решеткой в случае решетки), но не является матроидом, если L(A) не является решеткой.

Алгебра Орлика-Соломона

Полурешетка пересечений определяет другой комбинаторный инвариант расположения – алгебру Орлика-Соломона. Для её определения фиксируем коммутативный субальгир K базового поля и формируем внешнюю алгебру E векторного пространства, порожденного гиперплоскостями. На E определяется структура цепного комплекса с обычным оператором границы. Алгебра Орлика-Соломона – это фактор-алгебра E по идеалу, порожденному элементами вида, для которых пересечение пусто, и границами элементов того же вида, для которых коразмерность меньше p.

Реальные договоренности

В реальном аффинном пространстве дополнение несвязно: оно состоит из отдельных частей, называемых ячейками, областями или камерами, каждая из которых является либо ограниченной областью, являющейся выпуклым политопом, либо неограниченной областью, являющейся выпуклой полиэдрической областью, уходящей в бесконечность. Каждая плоская часть А также разделена на части гиперплоскостями, не содержащими эту плоскую часть; эти части называются гранями А. Области являются гранями, поскольку всё пространство является плоской частью. Грани коразмерности 1 могут называться фасетами А. Полурешётка граней расположения – это множество всех граней, упорядоченных по включению. Добавление дополнительного верхнего элемента к полурешётке граней даёт решётку граней. В двух измерениях (то есть в реальной аффинной плоскости) каждая область является выпуклым многоугольником (если она ограничена) или выпуклой многоугольной областью, уходящей в бесконечность. Например, если расположение состоит из трёх параллельных прямых, то полурешётка пересечений состоит из плоскости и трёх прямых, но не из пустого множества. Существует четыре области, ни одна из которых не ограничена. Если добавить прямую, пересекающую три параллельные прямые, то полурешётка пересечений состоит из плоскости, четырёх прямых и трёх точек пересечения. Существует восемь областей, по-прежнему ни одна из которых не ограничена. Если добавить ещё одну прямую, параллельную последней, то будет 12 областей, из которых две – ограниченные параллелограммы. Типичные задачи, связанные с расположением в n-мерном реальном пространстве, заключаются в определении количества областей, количества граней размерности 4 или количества ограниченных областей. На эти вопросы можно ответить, исходя только из полурешётки пересечений. Например, две основные теоремы Заславского (1975) утверждают, что число областей аффинного расположения равно (−1)ⁿpA(−1), а число ограниченных областей равно (−1)ⁿpA(1). Аналогично, число k-мерных граней или ограниченных граней можно определить как коэффициент при xⁿ⁻ᵏ в выражении (−1)ⁿwA(−x, −1) или (−1)ⁿwA(−x, 1). Был разработан быстрый алгоритм для определения грани расположения гиперплоскостей, содержащей заданную точку. Другой вопрос о расположении в реальном пространстве – определить, сколько областей являются симплексами (n-мерное обобщение треугольников и тетраэдров). На этот вопрос нельзя ответить, основываясь только на полурешётке пересечений. Проблема Мак-Маллена состоит в поиске наименьшего расположения заданной размерности в общем положении в реальном проективном пространстве, для которого не существует ячейки, касающейся всех гиперплоскостей. Реальное линейное расположение, помимо своей полурешётки граней, имеет частично упорядоченное множество областей, различное для каждой области. Это множество формируется путём выбора произвольной базовой области B₀ и сопоставления каждой области R множества S(R), состоящего из гиперплоскостей, разделяющих R и B. Области частично упорядочены так, что R₁ ≥ R₂ если S(R₁, R) содержит S(R₂, R). В особом случае, когда гиперплоскости возникают из корневой системы, полученное частично упорядоченное множество является соответствующей группой Вейля со слабым порядком. В общем случае, множество областей ранжируется по количеству разделяющих гиперплоскостей, и его функция Мёбиуса была вычислена. Вадим Шехтман и Александр Варченко ввели матрицу, индексированную по областям. Элемент матрицы для областей и задан произведением неопределённых переменных для каждой гиперплоскости H, разделяющей эти две области. Если эти переменные специализируются на значении q, то это называется q-матрицей (над евклидовой областью) для расположения, и значительная информация содержится в её нормальной форме Смита.

In real affine space, the complement is disconnected: it is made up of separate pieces called cells or regions or chambers, each of which is either a bounded region that is a convex polytope, or an unbounded region that is a convex polyhedral region which goes off to infinity. Each flat of A is also divided into pieces by the hyperplanes that do not contain the flat; these pieces are called the faces of A. The regions are faces because the whole space is a flat. The faces of codimension 1 may be called the facets of A. The face semilattice of an arrangement is the set of all faces, ordered by inclusion. Adding an extra top element to the face semilattice gives the face lattice. In two dimensions (i. e., in the real affine plane) each region is a convex polygon (if it is bounded) or a convex polygonal region which goes off to infinity. As an example, if the arrangement consists of three parallel lines, the intersection semilattice consists of the plane and the three lines, but not the empty set. There are four regions, none of them bounded. If we add a line crossing the three parallels, then the intersection semilattice consists of the plane, the four lines, and the three points of intersection. There are eight regions, still none of them bounded. If we add one more line, parallel to the last, then there are 12 regions, of which two are bounded parallelograms. Typical problems about an arrangement in n dimensional real space are to say how many regions there are, or how many faces of dimension 4, or how many bounded regions. These questions can be answered just from the intersection semilattice. For instance, two basic theorems, from Zaslavsky (1975), are that the number of regions of an affine arrangement equals (−1)npA(−1) and the number of bounded regions equals (−1)npA(1). Similarly, the number of k dimensional faces or bounded faces can be read off as the coefficient of xn−k in (−1)n wA (−x, −1) or (−1)nwA(−x, 1). designed a fast algorithm to determine the face of an arrangement of hyperplanes containing an input point. Another question about an arrangement in real space is to decide how many regions are simplices (the n dimensional generalization of triangles and tetrahedra). This cannot be answered based solely on the intersection semilattice. The McMullen problem asks for the smallest arrangement of a given dimension in general position in real projective space for which there does not exist a cell touched by all hyperplanes. A real linear arrangement has, besides its face semilattice, a poset of regions, a different one for each region. This poset is formed by choosing an arbitrary base region, B0, and associating with each region R the set S(R) consisting of the hyperplanes that separate R from B. The regions are partially ordered so that R1 ≥ R2 if S(R1, R) contains S(R2, R). In the special case when the hyperplanes arise from a root system, the resulting poset is the corresponding Weyl group with the weak order. In general, the poset of regions is ranked by the number of separating hyperplanes and its Möbius function has been computed
Vadim Schechtman and Alexander Varchenko introduced a matrix indexed by the regions. The matrix element for the region and is given by the product of indeterminate variables for every hyperplane H that separates these two regions. If these variables are specialized to be all value q, then this is called the q matrix (over the Euclidean domain ) for the arrangement and much information is contained in its Smith normal form.

Технические особенности

Иногда удобно допускать, чтобы вырожденная гиперплоскость, представляющая собой всё пространство S, входила в состав расположения. Если A содержит вырожденную гиперплоскость, то у него нет областей, поскольку дополнение пусто. Однако у него всё равно есть плоскости, полурешётка пересечений и грани. Предыдущее обсуждение исходило из того, что вырожденная гиперплоскость не входит в расположение. Иногда требуется допускать повторение гиперплоскостей в расположении. Мы не рассматривали эту возможность в предыдущем обсуждении, но это не влияет на суть дела.