Combinatorial Groupoids,Cubical Complexes,and the Lovász Conjecture

This paper lays the foundation for a theory of combinatorial groupoids that allows us to use concepts like “holonomy”, “parallel transport”, “bundles”, “combinatorial curvature”, etc. in the context of simplicial (polyhedral) complexes, posets, graphs, polytopes and other combinatorial objects. We introduce a new, holonomy-type invariant for cubical complexes, leading to a combinatorial “Theorema Egregium” for cubical complexes that are non-embeddable into cubical lattices. Parallel transport of Hom-complexes and maps is used as a tool to extend Babson–Kozlov–Lovász graph coloring results to more general statements about nondegenerate maps (colorings) of simplicial complexes and graphs. The author was supported by grants 144014 and 144026 of the Serbian Ministry of Science and Technology.     

Symmetric functions,codes of partitions and the KP hierarchy

We consider an operator of Bernstein for symmetric functions and give an explicit formula for its action on an arbitrary Schur function. This formula is given in a remarkably simple form when written in terms of some notation based on the code of a partition. As an application, we give a new and very simple proof of a classical result for the KP hierarchy, which involves the Plücker relations for Schur function coefficients in a τ-function for the hierarchy. This proof is especially compact because we are able to restate the Plücker relations in a form that is symmetrical in terms of partition code notation.     

Polynomial Hierarchy, Betti Numbers, and a Real Analogue of Toda’s Theorem

Toda (in SIAM J. Comput. 20(5):865–877, 1991) proved in 1989 that the (discrete) polynomial time hierarchy, PH, is contained in the class P ^#P , namely the class of languages that can be decided by a Turing machine in polynomial time given access to an oracle with the power to compute a function in the counting complexity class #P. This result, which illustrates the power of counting, is considered to be a seminal result in computational complexity theory. An analogous result in the complexity theory over the reals (in the sense of Blum–Shub–Smale real machines in Bull. Am. Math. Soc. (NS) 21(1): 1–46, 1989) has been missing so far. In this paper we formulate and prove a real analogue of Toda’s theorem. Unlike Toda’s proof in the discrete case, which relied on sophisticated combinatorial arguments, our proof is topological in nature. As a consequence of our techniques, we are also able to relate the computational hardness of two extremely well-studied problems in algorithmic semi-algebraic geometry: the problem of deciding sentences in the first-order theory of the reals with a constant number of quantifier alternations, and that of computing Betti numbers of semi-algebraic sets. We obtain a polynomial time reduction of the compact version of the first problem to the second. This latter result may be of independent interest to researchers in algorithmic semi-algebraic geometry.     

Strong Normalizability of Typed Lambda-Calculi for Substructural Logics

The strong normalization theorem is uniformly proved for typed λ-calculi for a wide range of substructural logics with or without strong negation. We would like to thank the referees for their valuable comments and suggestions. This research was supported by the Alexander von Humboldt Foundation. The second author is grateful to the Foundation for providing excellent working conditions and generous support of this research. This work was also supported by the Japanese Ministry of Education, Culture, Sports, Science and Technology, Grant-in-Aid for Young Scientists (B) 20700015, 2008.     

Poisson convergence,in large deviations,for the superposition of independent point processes

For a small buffer queueing system fed by many flows of a large class of traffic processes we show the single server queue and associated sample paths behave as if fed by marked Poisson traffic in a large deviations limit. The timescale of events of interest tends to zero, so we study the log moment generating function as time tends to zero. The associated rate function depends only on the mean arrival rate and the moment generating function of the arrivals. These results are useful in estimating drop probabilities while studying the effect of small buffers on communication protocols. Research supported by EPSRC Grant GR/S86266/01.     

Regularity and Variationality of Solutions to Hamilton—Jacobi Equations. Part II: Variationality,Existence, Uniqueness

We formulate an Hamilton–Jacobi partial differential equation

Symmetries,Lagrangian and Conservation Laws for the Maxwell Equations

The evolution equations of Maxwell’s equations has a Lagrangian written in terms of the electric E and magnetic H fields, but admit neither Lorentz nor conformal transformations. The additional equations ∇⋅E=0, ∇⋅H=0 guarantee the Lorentz and conformal invariance, but the resulting system is overdetermined, and hence does not have a Lagrangian. The aim of the present paper is to attain a harmony between these two contradictory properties and provide a correspondence between symmetries and conservation laws using the Lagrangian for the evolutionary part of Maxwell’s equations.     

Hypercontractivity, Nash inequalities and subordination for classes of nonlinear semigroups

A suitable notion of hypercontractivity for a nonlinear semigroup {T _t } is shown to imply Nash-type inequalities for its generator H, provided a subhomogeneity property holds for the energy functional (u,Hu). We use this fact to prove that, for semigroups generated by operators of p-Laplacian-type, hypercontractivity implies ultracontractivity. Then we introduce the notion of subordinated nonlinear semigroups when the corresponding Bernstein function is f(x)=x ^α , and write an explicit formula for the associated generator. It is shown that hypercontractivity still holds for the subordinated semigroup and, hence, that Nash-type inequalities hold as well for the subordinated generator.     

Absorbing Angles,Steiner Minimal Trees,and Antipodality

We give a new proof that a star {op _i :i=1,…,k} in a normed plane is a Steiner minimal tree of vertices {o,p ₁,…,p _k } if and only if all angles formed by the edges at o are absorbing (Swanepoel in Networks 36: 104–113, 2000). The proof is simpler and yet more conceptual than the original one. We also find a new sufficient condition for higher-dimensional normed spaces to share this characterization. In particular, a star {op _i :i=1,…,k} in any CL-space is a Steiner minimal tree of vertices {o,p ₁,…,p _k } if and only if all angles are absorbing, which in turn holds if and only if all distances between the normalizations \frac1||p_i||p_i\frac{1}{\Vert p_{i}\Vert}p_{i} equal 2. CL-spaces include the mixed ℓ ₁ and ℓ _∞ sum of finitely many copies of ℝ.     

Benders,metric and cutset inequalities for multicommodity capacitated network design

Solving multicommodity capacitated network design problems is a hard task that requires the use of several strategies like relaxing some constraints and strengthening the model with valid inequalities. In this paper, we compare three sets of inequalities that have been widely used in this context: Benders, metric and cutset inequalities. We show that Benders inequalities associated to extreme rays are metric inequalities. We also show how to strengthen Benders inequalities associated to non-extreme rays to obtain metric inequalities. We show that cutset inequalities are Benders inequalities, but not necessarily metric inequalities. We give a necessary and sufficient condition for a cutset inequality to be a metric inequality. Computational experiments show the effectiveness of strengthening Benders and cutset inequalities to obtain metric inequalities.     

Magnetically-Induced Buckling of a Whirling Conducting Rod with Applications to Electrodynamic Space Tethers

We study the effect of a magnetic field on the behaviour of a slender conducting elastic structure, motivated by stability problems of electrodynamic space tethers. Both static (buckling) and dynamic (whirling) instability are considered and we also compute post-buckling configurations. The equations used are the geometrically exact Kirchhoff equations. Magnetic buckling of a welded rod is found to be described by a surprisingly degenerate bifurcation, which is unfolded when both transverse anisotropy of the rod and angular velocity are considered. By solving the linearised equations about the (quasi-) stationary solutions, we find various secondary instabilities. Our results are relevant for current designs of electrodynamic space tethers and potentially for future applications in nano- and molecular wires.     

Global Existence,Decay, and Blow up of Solutions of a Singular Nonlocal Viscoelastic Problem

In this work we consider a nonlinear hyperbolic one-dimensional viscoelastic nonlocal problem with a nonlocal boundary condition. We establish a blow up result for large initial data and a decay result for small enough initial data.     

Symmetric chains,Gelfand–Tsetlin chains,and the Terwilliger algebra of the binary Hamming scheme

The de Bruijn–Tengbergen–Kruyswijk (BTK) construction is a simple algorithm that produces an explicit symmetric chain decomposition of a product of chains. We linearize the BTK algorithm and show that it produces an explicit symmetric Jordan basis (SJB). In the special case of a Boolean algebra, the resulting SJB is orthogonal with respect to the standard inner product and, moreover, we can write down an explicit formula for the ratio of the lengths of the successive vectors in these chains (i.e., the singular values). This yields a new constructive proof of the explicit block diagonalization of the Terwilliger algebra of the binary Hamming scheme. We also give a representation theoretic characterization of this basis that explains its orthogonality, namely, that it is the canonically defined (up to scalars) symmetric Gelfand–Tsetlin basis.     

Compression Schemes, Stable Definable Families, and o-Minimal Structures

We show that any family of sets uniformly definable in an o-minimal structure has an extended compression scheme of size equal to the number of parameters in the defining formula.     

Inexact Josephy–Newton framework for generalized equations and its applications to local analysis of Newtonian methods for constrained optimization

We propose and analyze a perturbed version of the classical Josephy–Newton method for solving generalized equations. This perturbed framework is convenient to treat in a unified way standard sequential quadratic programming, its stabilized version, sequential quadratically constrained quadratic programming, and linearly constrained Lagrangian methods. For the linearly constrained Lagrangian methods, in particular, we obtain superlinear convergence under the second-order sufficient optimality condition and the strict Mangasarian–Fromovitz constraint qualification, while previous results in the literature assume (in addition to second-order sufficiency) the stronger linear independence constraint qualification as well as the strict complementarity condition. For the sequential quadratically constrained quadratic programming methods, we prove primal-dual superlinear/quadratic convergence under the same assumptions as above, which also gives a new result.     

Combinatorial Integer Labeling Theorems on Finite Sets with Applications

Tucker’s well-known combinatorial lemma states that, for any given symmetric triangulation of the n-dimensional unit cube and for any integer labeling that assigns to each vertex of the triangulation a label from the set {±1,±2,…,±n} with the property that antipodal vertices on the boundary of the cube are assigned opposite labels, the triangulation admits a 1-dimensional simplex whose two vertices have opposite labels. In this paper, we are concerned with an arbitrary finite set D of integral vectors in the n-dimensional Euclidean space and an integer labeling that assigns to each element of D a label from the set {±1,±2,…,±n}. Using a constructive approach, we prove two combinatorial theorems of Tucker type. The theorems state that, under some mild conditions, there exists two integral vectors in D having opposite labels and being cell-connected in the sense that both belong to the set {0,1} ⁿ +q for some integral vector q. These theorems are used to show in a constructive way the existence of an integral solution to a system of nonlinear equations under certain natural conditions. An economic application is provided.     

Non-Walker Self-Dual Neutral Einstein Four-Manifolds of Petrov Type III

The local structure of the manifolds named in the title is described. Although curvature homogeneous, they are not, in general, locally homogeneous. Not all of them are Ricci-flat, which answers an existence question about type III Jordan-Osserman metrics, raised by Díaz-Ramos, García-Río and Vázquez-Lorenzo (J. Geom. Anal. 16, 39–52, 2006). Work begun during the author’s visit to the University of Santiago de Compostela, supported by Grant MTM2006-01432 (Spain).     

A Mathematica package for q-holonomic sequences and power series

We describe a Mathematica package for dealing with q-holonomic sequences and power series. The package is intended as a q-analogue of the Maple package gfun and the Mathematica package GeneratingFunctions. It provides commands for addition, multiplication, and substitution of these objects, for converting between various representations (q-differential equations, q-recurrence equations, q-shift equations), for computing sequence terms and power series coefficients, and for guessing recurrence equations given initial terms of a sequence. C. Koutschan partially supported by the Austrian Science Foundation (FWF) grants SFB F1305.     

Do we self-regulate actions or perceptions? A test of two computational models

Self-regulation theories in applied psychology disagree about whether action or perceptions are the focus of regulation. Computational models based on the two conceptualizations were constructed and simulated. In one scenario, they performed identically and in conjunction with participants in a study of the goal-level effect (Vancouver et al., Organ Res Methods 8:100–127, 2005). In another scenario they created differentiating predictions and only the computational model based on the self-regulation of perceptions matched the data of participants. Implications for research and practice are discussed.