A decomposition theory for matroids. I. General results

A new matroid decomposition with several attractive properties leads to a new theorem of alternatives for matroids. A strengthened version of this theorem for binary matroids says roughly that to any binary matroid at least one of the following statements must apply: (1) the matroid is decomposable, (2) several elements can be removed (in any order) without destroying 3-connectivity, (3) the matroid belongs to one of 2 well-specified classes or has 10 elements or less. The latter theorem is easily specialized to graphic matroids. These theorems seem particularly useful for the determination of minimal violation matroids, a subject discussed in part II.     

Color-bounded hypergraphs, I: General results

The concept of color-bounded hypergraph is introduced here. It is a hypergraph (set system) with vertex set X and edge set E={E₁,…,E_m}, where each edge E_i is associated with two integers s_i and t_i such that 1≤s_i≤t_i≤|E_i|. A vertex coloring φ:X→N is considered to be feasible if the number of colors occurring in E_i satisfies s_i≤|φ(E_i)|≤t_i, for all i≤m.Color-bounded hypergraphs generalize the concept of ‘mixed hypergraphs’ introduced by Voloshin [V. Voloshin, The mixed hypergraphs, Computer Science Journal of Moldova 1 (1993) 45-52], and a recent model studied by Drgas-Burchardt and ?azuka [E. Drgas-Burchardt, E. ?azuka, On chromatic polynomials of hypergraphs, Applied Mathematics Letters 20 (12) (2007) 1250-1254] where only lower bounds s_i were considered.We discuss the similarities and differences between our general model and the more particular earlier ones. An important issue is the chromatic spectrum-strongly related to the chromatic polynomial-which is the sequence whose kth element is the number of allowed colorings with precisely k colors (disregarding color permutations). Problems concerning algorithmic complexity are also considered.     

Regularization with differential operators. I. General theory

The method of regularization is used to obtain least squares solutions of the linear equation Kx = y, where K is a bounded linear operator from one Hilbert space into another and the regularizing operator L is a closed densely defined linear operator. Existence, uniqueness, and convergence analyses are developed. An application is given to the special case when K is a first kind integral operator and L is an nth order differential operator in the Hilbert space L²[a, b].     

General theoretical results on rectilinear embedability of graphs

In the design of certain kinds of electronic circuits the following question arises: given a non-negative integerk, what graphs admit of a plane embedding such that every edge is a broken line formed by horizontal and vertical segments and having at mostk bends? Any such graph is said to bek-rectilinear. No matter whatk is, an obvious necessary condition fork-rectilinearity is that the degree of each vertex does not exceed four. Our main result is that every planar graphH satisfying this condition is 3-rectilinear: in fact, it is 2-rectilinear with the only exception of the octahedron. We also outline a polynomial-time algorithm which actually constructs a plane embedding ofH with at most 2 bends (3 bends ifH is the octahedron) on each edge. The resulting embedding has the property that the total number of bends does not exceed 2n, wheren is the number of vertices ofH.     

Topological geometrodynamics,Part I: General theory

The recent status of topological geometrodynamics (TGD) is reviewed. One can end up with TGD either by starting from the energy problem of general relativity or from the need to generalize hadronic or superstring models. The basic principle of the theory is `Do not quantize!' meaning that quantum physics is reduced to Kähler geometry and spinor structure of the infinite-dimensional space of 3-surfaces in 8-dimensional space H=M⁴₊×CP₂ with physical states represented by classical spinor fields. General coordinate invariance implies that classical theory becomes an exact part of the quantum theory and configuration space geometry and that space-time surfaces are generalized Bohr orbits. The uniqueness of the infinite-dimensional Kähler geometric existence fixes imbedding space and the dimension of the space-time highly uniquely and implies that superconformal and supercanonical symmetries acting on the lightcone boundary δM⁴₊×CP₂ are cosmologies symmetries.The work with the p-adic aspects of TGD, the realization of the possible role of quaternions and octonions in the formulation of quantum TGD, the discovery of infinite primes, and TGD inspired theory of consciousness encouraged the vision about TGD as a generalized number theory. The vision leads to a considerable generalization of TGD and to an extension of the symmetries of the theory to include superconformal and Super-Kac-Moody symmetries associated with the group P×SU(3)×U(2)_ew (P denotes the Poincaré group) acting as the local symmetries of the theory. Quantum criticality, which can be seen as a prediction of the theory, fixes the value spectrum for the coupling constants of the theory.The proper mathematical and physical interpretation of the p-adic numbers has remained a long-lasting challenge. Both TGD inspired theory of consciousness and the vision about physics as a generalized number theory suggest that p-adic space-time regions obeying p-adic counterparts of the field equations are geometric correlates of mind in the sense that they provide cognitive representations for the physics in the real space-time regions representing matter. Evolution identified as a gradual increase of the infinite p-adic prime characterizing the entire Universe is basic prediction of the theory.S-matrix elements can be identified as Glebsch–Gordan coefficients between interacting and free Super-Kac-Moody algebra representations and it is now possible to give Feynmann rules for the S-matrix in the approximation that elementary particles correspond to the so-called CP₂ type extremals.     

Critical angles between two convex cones I. General theory

The concept of critical (or principal) angle between two linear subspaces has applications in statistics, numerical linear algebra, and other areas. Such concept has been abundantly studied in the literature, both from a theoretical and computational point of view. Part I of this work is an attempt to build a general theory of critical angles for a pair of closed convex cones. The need of such theory is motivated, among other reasons, by some specific problems arising in regression analysis of cone-constrained data, see Tenenhaus (Psychometrika 53:503–524, 1988). Angle maximization and/or angle minimization problems involving a pair of convex cones are at the core of our discussion. Such optimization problems are nonconvex in general and their numerical resolution offer a number of challenges. Part II of this work focusses on the practical computation of the maximal and/or minimal angle between specially structured cones.     

Generalized Watson transforms I: General theory

This paper introduces two main concepts, called a generalized Watson transform and a generalized skew-Watson transform, which extend the notion of a Watson transform from its classical setting in one variable to higher dimensional and noncommutative situations. Several construction theorems are proved which provide necessary and sufficient conditions for an operator on a Hilbert space to be a generalized Watson transform or a generalized skew-Watson transform. Later papers in this series will treat applications of the theory to infinite-dimensional representation theory and integral operators on higher dimensional spaces.

     

Differential symmetry breaking operators: I. General theory and F-method

We prove a one-to-one correspondence between differential symmetry breaking operators for equivariant vector bundles over two homogeneous spaces and certain homomorphisms for representations of two Lie algebras, in connection with branching problems of the restriction of representations. We develop a new method (F-method) based on the algebraic Fourier transform for generalized Verma modules, which characterizes differential symmetry breaking operators by means of certain systems of partial differential equations. In contrast to the setting of real flag varieties, continuous symmetry breaking operators of Hermitian symmetric spaces are proved to be differential operators in the holomorphic setting. In this case, symmetry breaking operators are characterized by differential equations of second order via the F-method.     

The thermodynamic limit of quantum Coulomb systems Part I. General theory

This article is the first in a series dealing with the thermodynamic properties of quantum Coulomb systems.In this first part, we consider a general real-valued function E defined on all bounded open sets of R³. Our aim is to give sufficient conditions such that E has a thermodynamic limit. This means that the limit E(Ωn)|Ωn|⁻¹ exists for all ‘regular enough’ sequence Ωn with growing volume, |Ωn|→∞, and is independent of the considered sequence.The sufficient conditions presented in our work all have a clear physical interpretation. In the next paper, we show that the free energies of many different quantum Coulomb systems satisfy these assumptions, hence have a thermodynamic limit.     

Tractability of quasilinear problems I: General results

The tractability of multivariate problems has usually been studied only for the approximation of linear operators. In this paper we study the tractability of quasilinear multivariate problems. That is, we wish to approximate nonlinear operators S_d(·,·) that depend linearly on the first argument and satisfy a Lipschitz condition with respect to both arguments. Here, both arguments are functions of d variables. Many computational problems of practical importance have this form. Examples include the solution of specific Dirichlet, Neumann, and Schrödinger problems. We show, under appropriate assumptions, that quasilinear problems, whose domain spaces are equipped with product or finite-order weights, are tractable or strongly tractable in the worst case setting.This paper is the first part in a series of papers. Here, we present tractability results for quasilinear problems under general assumptions on quasilinear operators and weights. In future papers, we shall verify these assumptions for quasilinear problems such as the solution of specific Dirichlet, Neumann, and Schrödinger problems.     

Similarity of operator blocks and canonical forms. I. General results,feedback equivalence and kronecker indices

In the present paper the problem of classifying blocks of matrices up to similarity is considered. The notion of block similarity used here is a natural generalization of similarity for matrices. The invariants are described and canonical forms are given. This theory of block-similarity provides a general framework, which includes the state feedback theory for systems, the theory of Kronecker equivalence and a similarity theory for non-everywhere defined operators. New applications, in particular to factorization problems, are also obtained.     

Spectral measures,I: General theory in a topological vector space

Part I of this paper is devoted to the general theory of spectral measures in topological vector spaces. We extend the Hilbert space theory to this setting and generalize the notion of spectral measure in some useful ways to provide a framework for Part II, etc.     

Deformation theory of objects in homotopy and derived categories I: General theory

This is the first paper in a series. We develop a general deformation theory of objects in homotopy and derived categories of DG categories. Namely, for a DG module E over a DG category we define four deformation functors Defh(E), coDefh(E), Def(E), coDef(E). The first two functors describe the deformations (and co-deformations) of E in the homotopy category, and the last two - in the derived category. We study their properties and relations. These functors are defined on the category of artinian (not necessarily commutative) DG algebras.     

General convergence results for stochastic approximations via weak convergence theory

The paper treats general convergence conditions for a class of algorithms for finding the minima of a function f(x) when f(x) is of unknown (or partly unknown) form, and when only noise corrupted observations can be taken. Such problems occur frequently in adaptive processes, and in many applications to statistics and estimation. The algorithms are of the stochastic approximation type. Several forms are dealt with—for estimation in either discrete or continuous time, with and without side constraints, and with or without periodic search renewal. The algorithms can be considered as sequential Monte Carlo methods for systems optimization. The innovations partly concern the method of proof. However, an interesting “constrained” and “renewed” algorithm is also considered. By using ideas from the theory of weak convergence of probability measures, we can get relatively short proofs, under much weaker conditions than heretofore required. For example, the noise can be correlated, and there are fewer restrictions on the step size. Furthermore, the nature of the method permits generalizations to more abstract cases (which occur for example, if we are optimizing a distributed parameter system). The results can be extended in many directions and variations of the technique can be used to get bounds on rates of convergence. Special forms of the method can be applied to many well-known “adaptive” procedures.     

Weighted norm inequalities, off-diagonal estimates and elliptic operators. Part I: General operator theory and weights

This is the first part of a series of four articles. In this work, we are interested in weighted norm estimates. We put the emphasis on two results of different nature: one is based on a good-λ inequality with two parameters and the other uses Calderón-Zygmund decomposition. These results apply well to singular “non-integral” operators and their commutators with bounded mean oscillation functions. Singular means that they are of order 0, “non-integral” that they do not have an integral representation by a kernel with size estimates, even rough, so that they may not be bounded on all Lp spaces for 1<p<∞. Pointwise estimates are then replaced by appropriate localized Lp-Lq estimates. We obtain weighted Lp estimates for a range of p that is different from (1,∞) and isolate the right class of weights. In particular, we prove an extrapolation theorem “à la Rubio de Francia” for such a class and thus vector-valued estimates.     

Fractional perfect b-matching polytopes I: General theory

The fractional perfect b-matching polytope of an undirected graph G is the polytope of all assignments of nonnegative real numbers to the edges of G such that the sum of the numbers over all edges incident to any vertex v   is a prescribed nonnegative number _bv$b_v$. General theorems which provide conditions for nonemptiness, give a formula for the dimension, and characterize the vertices, edges and face lattices of such polytopes are obtained. Many of these results are expressed in terms of certain spanning subgraphs of G which are associated with subsets or elements of the polytope. For example, it is shown that an element u of the fractional perfect b-matching polytope of G is a vertex of the polytope if and only if each component of the graph of u either is acyclic or else contains exactly one cycle with that cycle having odd length, where the graph of u is defined to be the spanning subgraph of G whose edges are those at which u is positive.