The universal partition theorem for oriented matroids

We consider realization spaces of a family of oriented matroids of rank three as point configurations in the affine plane. The fundamental problem arises as to which way these realization spaces partition their embedding space. The Universal Partition Theorem roughly states that such a partition can be as complicated as any partition of ℝ ⁿ into elementary semialgebraic sets induced by an arbitrary finite set of polynomials in ℤ[X]. We present the first proof of the Universal Partition Theorem. In particular, it includes the first complete proof of the so-called Universality Theorem. This work was supported by the Deutsche Forschungsgemeinschaft, Graduiertenkolleg “Analyse und Konstruktion in der Mathematik”.     

Oriented matroids with few mutations

This paper defines a “connected sum” operation on oriented matroids of the same rank. This construction is used for three different applications in rank 4. First it provides nonrealizable pseudoplane arrangements with a low number of simplicial regions. This contrasts the case of realizable hyperplane arrangements: by a classical theorem of Shannon every arrangement ofn projective planes in ℝP ^d-1 contains at leastn simplicial regions and every plane is adjacent to at leastd simplicial regions [17], [18]. We construct a class of uniform pseudoarrangements of 4n pseudoplanes in ℝP³ with only 3n+1 simplicial regions. Furthermore, we construct an arrangement of 20 pseudoplanes where one plane is not adjacent to any simplicial region. Finally we disprove the “strong-map conjecture” of Las Vergnas [1]. We describe an arrangement of 12 pseudoplanes containing two points that cannot be simultaneously contained in an extending hyperplane.     

Littlewood–Paley theorem on spaces <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis>(<Emphasis Type="Italic">t</Emphasis>)</Superscript>(ℝ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>)

We point out that if the Hardy–Littlewood maximal operator is bounded on the space L ^p(t)(ℝ), 1 < a ≤ p(t) ≤ b < ∞, t ∈ ℝ, then the well-known characterization of the spaces L ^p (ℝ), 1 < p < ∞, by the Littlewood–Paley theory extends to the space L ^p(t)(ℝ). We show that, for n > 1 , the Littlewood–Paley operator is bounded on L ^p(t) (ℝ ⁿ ), 1 < a ≤ p(t) ≤ b < ∞, t ∈ ℝ ⁿ , if and only if p(t) = const. Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 60, No. 12, pp. 1709–1715, December, 2008.     

Mirror configurations of points and lines and algebraic surfaces of degree four

We prove that mirror nonsingular configurations of m points and n lines in ℝP ³ exist only for m≤3, n≡0 or 1 (mod 4) and for m=0 or 1 (mod 4), n≡0 (mod 2). In addition, we give an elementary proof of V. M. Kharlamov’s well-known result saying that if a nonsingular surface of degree four in ℝP ³ is noncontractible and has M≥5 components, then it is nonmirror. For the cases M=5, 6, 7 and 8, Kharlamov suggested an elementary proof using an analogy between such surfaces and configurations of M−1 points and a line. Our proof covers the remaining cases M=9, 10. Bibliography: 5 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 231, 1995, pp. 299–308. Translated by N. Yu. Netsvetaev.     

Combinatorial obstructions to the lifting of weaving diagrams

This paper deals with various connections of oriented matroids [3] and weaving diagrams of lines in space [9], [16], [27]. We encode the litability problem of a particular weaving diagramD onn lines by the realizability problem of a partial oriented matroid χ _D with2n elements in rank 4. We prove that the occurrence of a certain substructure inD implies that χD is noneuclidean in the sense of Edmonds, Fukuda, and Mandel [12], [14]. Using this criterion we construct an infinite class of minor-minimal noneuclidean oriented matroids in rank 4. Finally, we give an easy algebraic proof for the nonliftability of the alternating weaving diagram on a bipartite grid of 4×4 lines [16].     

The incidence structure of subspaces with well-scaled frames

In this paper, the incidence structure of classes of subspaces that generalize the regular (unimodular) subspaces of rational coordinate spaces is studied. Let F the a field and S - F β {0}. A subspace, V, of a coordinate space over F is S-regular if every elementary vector of V can be scaled by an element of F β {0} so that all of its non-zero entries are elements of S. A subspace that is {−1, +1 }-regular over the rational field is regular.Associated with a subspace, V, over an arbitrary (respectively, ordered) field is a matroid (oriented matroid) having as circuits (signed circuits) the set of supports (signed supports) of elementary vectors of V. Fundamental representation properties are established for the matroids that arise from certain classes of subspaces. Matroids that are (minor) minimally non-representable by various classes of subspaces are identified. A unique representability results is established for the oriented matroids of subspaces that are dyadic (i.e., {±2⁰, ±2¹, ±2², …}-regular) over the rationals. A self-dual characterization is established for the matroids of S-regular subspaces which generalizes Minty's characterization of regular spaces as digraphoids.     

Two constructions of oriented matroids with disconnected extension space

The extension space ℰ(ℳ) of an oriented matroid ℳ is the poset of all one-element extensions of ℳ, considered as a simplicial complex. We present two different constructions leading to rank 4 oriented matroids with disconnected extension space. We prove especially that if an elementf is not contained in any mutation of a rank 4 oriented matroid ℳ, then ℰ(ℳ\f) contains an isolated point. A uniform nonrealizable arrangement of pseudoplanes with this property is presented. The examples described contrast results of Sturmfels and Ziegler [12] who proved that for rank 3 oriented matroids the extension space has the homotopy type of the 2-sphere.     

Dilations and Completions for Gabor Systems

Let be a full rank time-frequency lattice in ℝ ^d ×ℝ ^d . In this note we first prove that any dual Gabor frame pair for a Λ-shift invariant subspace M can be dilated to a dual Gabor frame pair for the whole space L ²(ℝ ^d ) when the volume v(Λ) of the lattice Λ satisfies the condition v(Λ)≤1, and to a dual Gabor Riesz basis pair for a Λ-shift invariant subspace containing M when v(Λ)>1. This generalizes the dilation result in Gabardo and Han (J. Fourier Anal. Appl. 7:419–433, [2001]) to both higher dimensions and dual subspace Gabor frame pairs. Secondly, for any fixed positive integer N, we investigate the problem whether any Bessel–Gabor family G(g,Λ) can be completed to a tight Gabor (multi-)frame G(g,Λ)∪(∪ _j=1 ^N G(g _j ,Λ)) for L ²(ℝ ^d ). We show that this is true whenever v(Λ)≤N. In particular, when v(Λ)≤1, any Bessel–Gabor system is a subset of a tight Gabor frame G(g,Λ)∪G(h,Λ) for L ²(ℝ ^d ). Related results for affine systems are also discussed. Communicated by Chris Heil.     

Existence principles for higher-order nonlocal boundary-value problems and their applications to singular Sturm-Liouville problems

We present existence principles for the nonlocal boundary-value problem (φ(u^(p−1)))′=g(t,u,...,u^(p−1), α_k(u)=0, 1≤k≤p−1, where p ≥ 2, π: ℝ → ℝ is an increasing and odd homeomorphism, g is a Carathéodory function that is either regular or has singularities in its space variables, and α _k: C ^p−1[0, T] → ℝ is a continuous functional. An application of the existence principles to singular Sturm-Liouville problems (−1)ⁿ(φ(u⁽²ⁿ⁻⁾))′=f(t,u,...,u⁽²ⁿ⁻¹⁾), u^(2k)(0)=0, α_ku^(2k)(T)+b_ku^(2k=1)(T)=0, 0≤k≤n−1, is given. Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 60, No. 2, pp. 240–259, February, 2008.     

Optimal Meshes for Finite Elements of Arbitrary Order

Given a function f defined on a bounded domain Ω⊂ℝ² and a number N>0, we study the properties of the triangulation T_N\mathcal{T}_{N} that minimizes the distance between f and its interpolation on the associated finite element space, over all triangulations of at most N elements. The error is studied in the norm X=L ^p for 1≤p≤∞, and we consider Lagrange finite elements of arbitrary polynomial degree m−1. We establish sharp asymptotic error estimates as N→+∞ when the optimal anisotropic triangulation is used, recovering the results on piecewise linear interpolation (Babenko et al. in East J. Approx. 12(1), 71–101, 2006; Babenko, submitted; Chen et al. in Math. Comput. 76, 179–204, 2007) and improving the results on higher degree interpolation (Cao in SIAM J. Numer. Anal. 45(6), 2368–2391, 2007, SIAM J. Sci. Comput. 29, 756–781, 2007, Math. Comput. 77, 265–286, 2008). These estimates involve invariant polynomials applied to the m-th order derivatives of f. In addition, our analysis also provides practical strategies for designing meshes such that the interpolation error satisfies the optimal estimate up to a fixed multiplicative constant. We partially extend our results to higher dimensions for finite elements on simplicial partitions of a domain Ω⊂ℝ ^d .     

Solutions in Sobolev spaces of vector refinement equations with a general dilation matrix

In this paper, we present a necessary and sufficient condition for the existence of solutions in a Sobolev space W_p^k(ℝ^s) (1≤p≤∞) to a vector refinement equation with a general dilation matrix. The criterion is constructive and can be implemented. Rate of convergence of vector cascade algorithms in a Sobolev space W_p^k(ℝ^s) will be investigated. When the dilation matrix is isotropic, a characterization will be given for the L_p (1≤p≤∞) critical smoothness exponent of a refinable function vector without the assumption of stability on the refinable function vector. As a consequence, we show that if a compactly supported function vector φ∈L_p(ℝ^s) (φ∈C(ℝ^s) when p=∞) satisfies a refinement equation with a finitely supported matrix mask, then all the components of φ must belong to a Lipschitz space Lip(ν,L_p(ℝ^s)) for some ν>0. This paper generalizes the results in R.Q. Jia, K.S. Lau and D.X. Zhou (J. Fourier Anal. Appl. 7 (2001) 143–167) in the univariate setting to the multivariate setting. Dedicated to Professor Charles A. Micchelli on the occasion of his 60th birthday Mathematics subject classifications (2000) 42C20, 41A25, 39B12. Research was supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC Canada) under Grant G121210654.     

Oriented matroids and Ky Fan’s theorem

L. Lovász (Matroids and Sperner’s Lemma, Europ. J. Comb. 1 (1980), 65–66) has shown that Sperner’s combinatorial lemma admits a generalization involving a matroid defined on the set of vertices of the associated triangulation. We prove that Ky Fan’s theorem admits an oriented matroid generalization of similar nature. Classical Ky Fan’s theorem is obtained as a corollary if the underlying oriented matroid is chosen to be the alternating matroid C ^m,r .     

Linear Inequalities for Rank 3 Geometric Lattices

The flag Whitney numbers (also referred to as the flag f-numbers) of a geometric lattice count the number of chains of the lattice with elements having specified ranks. We give a collection of inequalities which imply all the linear inequalities satisfied by the flag Whitney numbers of rank 3 geometric lattices. We further describe the smallest closed convex set containing the flag Whitney numbers of rank 3 geometric lattices as well as the smallest closed convex set containing the flag Whitney numbers of those lattices corresponding to oriented matroids.     

Carathéodory-type Theorems à la Bárány

We generalise the famous Helly–Lovász theorem leading to a generalisation of the Bárány–Carathéodory theorem for oriented matroids in dimension ≤3. We also provide a non-metric proof of the latter colourful theorem for arbitrary dimensions and explore some generalisations in dimension 2.     

The Graph of Triangulations of a Point Configuration with d +4 Vertices Is 3-Connected

We study the graph of bistellar flips between triangulations of a vector configuration A with d+4 elements in rank d+1 (i.e. with corank 3), as a step in the Baues problem. We prove that the graph is connected in general and 3-connected for acyclic vector configurations, which include all point configurations of dimension d with d+4 elements. Hence, every pair of triangulations can be joined by a finite sequence of bistellar flips and, in the acyclic case, every triangulation has at least three geometric bistellar neighbours. In corank 4, connectivity is not known and having at least four flips is false. In corank 2, the results are trivial since the graph is a cycle. Our methods are based on a dualization of the concept of triangulation of a point or vector configuration A to that of a virtual chamber of its Gale transform B , introduced by de Loera et al. in 1996. As an additional result we prove a topological representation theorem for virtual chambers, stating that every virtual chamber of a rank 3 vector configuration B can be realized as a cell in some pseudo-chamber complex of B in the same way that regular triangulations appear as cells in the usual chamber complex. All the results in this paper generalize to triangulations of corank 3 oriented matroids and virtual chambers of rank 3 oriented matroids, realizable or not. The details for this generalization are given in the Appendix. Received March 1, 1999, and in revised form September 7, 1999.     

Piecewise-Linear Approximations of Multidimensional Functions

We develop explicit, piecewise-linear formulations of functions f(x):ℝ ⁿ ↦ℝ, n≤3, that are defined on an orthogonal grid of vertex points. If mixed-integer linear optimization problems (MILPs) involving multidimensional piecewise-linear functions can be easily and efficiently solved to global optimality, then non-analytic functions can be used as an objective or constraint function for large optimization problems. Linear interpolation between fixed gridpoints can also be used to approximate generic, nonlinear functions, allowing us to approximately solve problems using mixed-integer linear optimization methods. Toward this end, we develop two different explicit formulations of piecewise-linear functions and discuss the consequences of integrating the formulations into an optimization problem.     

On classification of orthogonal multiplications à la do carmo-wallach

The space of range-equivalence classes of full orthogonal multiplications F: ℝ ⁿ ×ℝ ⁿ →ℝ ^p , n≤p ≤n ², is shown to be a compact convex body lying in so(n)⊗so(n). Furthermore, the dimension of the space of equivalence classes is determined to be (n ²(n−1)²)/4−n(n−1).     

Gumbel statistics for the longest interval of identical spins in a one-dimensional Gibbs measure

We consider one-dimensional Gibbs measures on spin configurations σ ∈ {–1,+1}^ℤ. For N ∈ ℕ let l _N denote the length of the longest interval of consecutive spins of the same kind in the interval [0,N]. We show that the distribution of a suitable continuous modification l _c (N) of l _N converges to the Gumbel distribution, i.e., for some α, β ∈ (0, ∞) and γ ∈ ℝ, lim _{N →∞} ℙ(l _c (N) ≤ α log N + βx + γ) = e ^{–e –x} . Received: 2 September 2002     

Compositions of isometric immersions¶in higher codimension

Given a submanifold M ⁿ of Euclidean space ℝ ^{n + p} with codimension p≤6, under generic conditions on its second fundamental form, we show that any other isometric immersion of M ⁿ into ℝ ^{n + p + q} , 0≤q≤n− 2p−1 and 2q≤n+ 1 if q≥ 5, must be locally a composition of isometric immersions. This generalizes several previous results on rigidity and compositions of submanifolds. We also provide conditions under which our result is global. 14 March 2001     

On the theory of mappings with finite area distortion

It is shown that mappings in ℝⁿ with finite distortion of area in all dimensions 1 ≤ k ≤ n − 1 satisfy certain modulus inequalities in terms of inner and outer dilatations of the mappings; in particular, generalizations of the well-known Poletskii inequality for quasiregular mappings are proved. The theory developed is applicable, for example, to the class of finitely bi-Lipschitz mappings, which is a natural generalization of the bi-Lipschitz mappings, as well as isometries and quasi-isometries in ℝⁿ.