Cutting hyperplane arrangements

We consider a collectionH ofn hyperplanes in E ^d (where the dimensiond is fixed). An ε-cutting forH is a collection of (possibly unbounded)d-dimensional simplices with disjoint interors, which cover all E ^d and such that the interior of any simplex is intersected by at mostεn hyperplanes ofH. We give a deterministic algorithm for finding a (1/r)-cutting withO(r ^d ) simplices (which is asymptotically optimal). Forr≤n ^1−σ, where δ>0 is arbitrary but fixed, the running time of this algorithm isO(n(logn) ^O(1) r ^d−1). In the plane we achieve a time boundO(nr) forr≤n ^1−δ, which is optimal if we also want to compute the collection of lines intersecting each simplex of the cutting. This improves a result of Agarwal, and gives a conceptually simpler algorithm. For ann point setX⊆E ^d and a parameterr, we can deterministically compute a (1/r)-net of sizeO(rlogr) for the range space (X, {X ϒ R; R is a simplex}), In timeO(n(logn) ^O(1) r ^d−1 +r ^O(1)). The size of the (1/r)-net matches the best known existence result. By a simple transformation, this allows us to find ε-nets for other range spaces usually encountered in computational geometry. These results have numerous applications for derandomizing algorithms in computational geometry without affecting their running time significantly. A preliminary version of this paper appeared inProceedings of the Sixth ACM Symposium on Computational Geometry, Berkeley, 1990, pp. 1–9. Work on this paper was supported by DIMACS Center.     

Bernstein-Sato ideals and hyperplane arrangements

We study the relation between zero loci of Bernstein-Sato ideals and roots of b-functions and obtain a criterion to guarantee that roots of b-functions of a reducible polynomial are determined by the zero locus of the associated Bernstein-Sato ideal. Applying the criterion together with a result of Maisonobe we prove that the set of roots of the b-function of a free hyperplane arrangement is determined by its intersection lattice.We also study the zero loci of Bernstein-Sato ideals and the associated relative characteristic cycles for arbitrary central hyperplane arrangements. We prove the multivariable $n/d$ conjecture of Budur for complete factorizations of arbitrary hyperplane arrangements, which in turn proves the strong monodromy conjecture for the associated multivariable topological zeta functions.     

Multivariate splines and hyperplane arrangements

In this paper, we use the so-called conformality method of smoothing cofactor (abbr. CSC) and hyperplane arrangements to study truncated powers and box splines in R². By the relation between hyperplane arrangements and truncated powers, we give the expressions of the truncated powers. Moreover, by means of the CSC method, the least smoothness degrees of the truncated powers and the box splines on each direction of partition edges are studied.     

Reducibility of hyperplane arrangements

Certain problems on reducibility of central hyperplane arrangements are settled. Firstly, a necessary and sufficient condition on reducibility is obtained. More precisely, it is proved that the number of irreducible components of a central hyperplane arrangement equals the dimension of the space consisting of the logarithmic derivations of the arrangement with degree zero or one. Secondly, it is proved that the decomposition of an arrangement into a direct sum of its irreducible components is unique up to an isomorphism of the ambient space. Thirdly, an effective algorithm for determining the number of irreducible components and decomposing an arrangement into a direct sum of its irreducible components is offered. This algorithm can decide whether an arrangement is reducible, and if it is the case, what the defining equations of irreducible components are.     

Tropical hyperplane arrangements and oriented matroids

We study the combinatorial properties of a tropical hyperplane arrangement. We define tropical oriented matroids, and prove that they share many of the properties of ordinary oriented matroids. We show that a tropical oriented matroid determines a subdivision of a product of two simplices, and conjecture that this correspondence is a bijection.     

Broken circuit complexes and hyperplane arrangements

We study Stanley–Reisner ideals of broken circuit complexes and characterize those ones admitting linear resolutions or being complete intersections. These results will then be used to characterize hyperplane arrangements whose Orlik–Terao ideal has the same properties. As an application, we improve a result of Wilf on upper bounds for the coefficients of the chromatic polynomial of a maximal planar graph. We also show that for a matroid with a complete intersection broken circuit complex, the supersolvability of the matroid is equivalent to the Koszulness of its Orlik–Solomon algebra.     

Multiplier ideals of hyperplane arrangements

In this note we compute multiplier ideals of hyperplane arrangements. This is done using the interpretation of multiplier ideals in terms of spaces of arcs by Ein, Lazarsfeld, and Mustata (2004).

     

Alexander invariants of complex hyperplane arrangements

Let be an arrangement of complex hyperplanes. The fundamental group of the complement of is determined by a braid monodromy homomorphism, . Using the Gassner representation of the pure braid group, we find an explicit presentation for the Alexander invariant of . From this presentation, we obtain combinatorial lower bounds for the ranks of the Chen groups of . We also provide a combinatorial criterion for when these lower bounds are attained.

     

Dominant regions in noncrystallographic hyperplane arrangements

For a crystallographic root system, dominant regions in the Catalan hyperplane arrangement are in bijection with antichains in a partial order on the positive roots. For a noncrystallographic root system, the analogous arrangement and regions have importance in the representation theory of an associated graded Hecke algebra. Since there is also an analogous root order, it is natural to hope that a similar bijection can be used to understand these regions. We show that such a bijection does hold for type H₃ and for type I₂(m), including arbitrary ratio of root lengths when m is even, but does not hold for type H₄. We give a criterion that explains this failure and a list of the 16 antichains in the H₄ root order which correspond to empty regions.     

The Monodromy Conjecture for hyperplane arrangements

The Monodromy Conjecture asserts that if c is a pole of the local topological zeta function of a hypersurface, then exp(2πic) is an eigenvalue of the monodromy on the cohomology of the Milnor fiber. A stronger version of the conjecture asserts that every such c is a root of the Bernstein-Sato polynomial of the hypersurface. In this note we prove the weak version of the conjecture for hyperplane arrangements. Furthermore, we reduce the strong version to the following conjecture: −n/d is always a root of the Bernstein-Sato polynomial of an indecomposable essential central hyperplane arrangement of d hyperplanes in C ⁿ .     

Bijections between affine hyperplane arrangements and valued graphs

We show new bijective proofs of previously known formulas for the number of regions of some deformations of the braid arrangement, by means of a bijection between the no-broken-circuit sets of the corresponding integral gain graphs and some kinds of labelled binary trees. This leads to new bijective proofs for the Shi, Catalan, and similar hyperplane arrangements.     

Descent algebras, hyperplane arrangements, and shuffling cards

Two notions of riffle shuffling on finite Coxeter groups are given: one using Solomon's descent algebra and another using random walk on chambers of hyperplane arrangements. These coincide for types ,,,, and rank two groups but not always. Both notions have the same simple eigenvalues. The hyperplane definition is especially natural and satisfies a positivity property when is crystallographic and the relevant parameter is a good prime. The hyperplane viewpoint suggests deep connections with Lie theory and leads to a notion of riffle shuffling for arbitrary real hyperplane arrangements and oriented matroids.     

Lower central series and free resolutions of hyperplane arrangements

If is the complement of a hyperplane arrangement, and is the cohomology ring of over a field of characteristic , then the ranks, , of the lower central series quotients of can be computed from the Betti numbers, , of the linear strand in a minimal free resolution of over . We use the Cartan-Eilenberg change of rings spectral sequence to relate these numbers to the graded Betti numbers, , of a minimal resolution of over the exterior algebra .

From this analysis, we recover a formula of Falk for , and obtain a new formula for . The exact sequence of low-degree terms in the spectral sequence allows us to answer a question of Falk on graphic arrangements, and also shows that for these arrangements, the algebra is Koszul if and only if the arrangement is supersolvable.

We also give combinatorial lower bounds on the Betti numbers, , of the linear strand of the free resolution of over ; if the lower bound is attained for , then it is attained for all . For such arrangements, we compute the entire linear strand of the resolution, and we prove that all components of the first resonance variety of are local. For graphic arrangements (which do not attain the lower bound, unless they have no braid subarrangements), we show that is determined by the number of triangles and subgraphs in the graph.

     

Derivation modules of orthogonal duals of hyperplane arrangements

Let A be an n × d matrix having full rank n. An orthogonal dual A^⊥ of A is a (d-n) × d matrix of rank (d−n) such that every row of A^⊥ is orthogonal (under the usual dot product) to every row of A. We define the orthogonal dual for arrangements by identifying an essential (central) arrangement of d hyperplanes in n-dimensional space with the n × d matrix of coefficients of the homogeneous linear forms for which the hyperplanes are kernels. When n ≥ 5, we show that if the matroid (or the lattice of intersection) of an n-dimensional essential arrangement contains a modular copoint whose complement spans, then the derivation module of the orthogonally dual arrangement ^⊥ has projective dimension at least ⌈ n(n+2)/4 ⌉ - 3.Hal Schenck partially supported by NSF DMS 03-11142, NSA MDA 904-03-1-0006, and ATP 010366-0103.     

Bruhat order, smooth Schubert varieties, and hyperplane arrangements

The aim of this article is to link Schubert varieties in the flag manifold with hyperplane arrangements. For a permutation, we construct a certain graphical hyperplane arrangement. We show that the generating function for regions of this arrangement coincides with the Poincaré polynomial of the corresponding Schubert variety if and only if the Schubert variety is smooth. We give an explicit combinatorial formula for the Poincaré polynomial. Our main technical tools are chordal graphs and perfect elimination orderings.