A bound for the number of different basic solutions generated by the simplex method

In this short paper, we give an upper bound for the number of different basic feasible solutions generated by the simplex method for linear programming problems (LP) having optimal solutions. The bound is polynomial of the number of constraints, the number of variables, and the ratio between the minimum and the maximum values of all the positive elements of primal basic feasible solutions. When the problem is primal nondegenerate, it becomes a bound for the number of iterations. The result includes strong polynomiality for Markov Decision Problem by Ye (http://www.stanford.edu/~yyye/simplexmdp1.pdf, 2010) and utilize its analysis. We also apply our result to an LP whose constraint matrix is totally unimodular and a constant vector b of constraints is integral.     

Geometric Permutations

A difference permutation is a structure which serves as an instrument to recognize important properties of permutations. Since special permutations are models for orthoschemes in generalized hyperbolic spaces (Minkowskian spaces) of dimension d there difference permutations give informations on the type of such orthoschemes. In this note with the help of difference permutations especially geometric permutations are explained which describe the structure of the concerning orthoschemes. This knowledge is necessary to count the numbers of orthoscheme types and special chains of orthoschemes as shown in B?hm (http://www.minet.uni-jena.de/preprints/boehm_08/Napiercycles.pdf).     

On the Pfaffian Number of Graphs

In 2006, Norine conjectured that a graph is k-Pfaffian but not ($k-1$)-Pfaffian if and only if k is a power of four [Norine, S., Drawing 4-Pfaffian graphs on the torus, Combinatorica (accepted for publication), http://www.math.princeton.edu/~snorin/papers.html.]. Recently, we presented a graph that is a counter-example to that conjecture [Miranda, A. A. A. and C. L. Lucchesi, Matching signatures and Pfaffian graphs, Technical report, Institute of Computing – University of Campinas – UNICAMP (2009). URL http://www.ic.unicamp.br/~reltech/2009/09-06.pdf]. In this article, we present an alternative proof that this graph is a counter-example to the conjecture. In fact, we present a graph that is not 4-Pfaffian and give a simple proof that it is 10-Pfaffian, using new methods.     

Local minimizers of the Ginzburg-Landau functional with prescribed degrees

We consider, in a smooth bounded multiply connected domain D⊂R², the Ginzburg-Landau energy subject to prescribed degree conditions on each component of ∂D. In general, minimal energy maps do not exist [L. Berlyand, P. Mironescu, Ginzburg-Landau minimizers in perforated domains with prescribed degrees, preprint, 2004]. When D has a single hole, Berlyand and Rybalko [L. Berlyand, V. Rybalko, Solution with vortices of a semi-stiff boundary value problem for the Ginzburg-Landau equation, J. Eur. Math. Soc. (JEMS), in press, 2008, http://www.math.psu.edu/berlyand/publications/publications.html] proved that for small ε local minimizers do exist. We extend the result in [L. Berlyand, V. Rybalko, Solution with vortices of a semi-stiff boundary value problem for the Ginzburg-Landau equation, J. Eur. Math. Soc. (JEMS), in press, 2008, http://www.math.psu.edu/berlyand/publications/publications.html]: Eε(u) has, in domains D with 2,3,… holes and for small ε, local minimizers. Our approach is very similar to the one in [L. Berlyand, V. Rybalko, Solution with vortices of a semi-stiff boundary value problem for the Ginzburg-Landau equation, J. Eur. Math. Soc. (JEMS), in press, 2008, http://www.math.psu.edu/berlyand/publications/publications.html]; the main difference stems in the construction of test functions with energy control.     

Spatial power indices with applications on real voting data from the Chamber of Deputies of the Czech Parliament

Participants in parliamentary voting—usually political parties—are evaluated with a value that assigns them predicted power with respect to their strength by so called power indices. However, in real world, political parties’ representatives act not strictly as predicted in theory. One possibility how the representatives differ from theory is the way they form coalitions; the coalitions can be announced (for example official governmental coalition parties in multiparty parliaments) or hidden. To incorporate the coalition forming influence, Bilal et al. (http://aei.pitt.edu/2052/1/001591_1.pdf, 2001) proposed to consider additional weights to possible coalitions into power indices. This article applies the concept of additional weights to calculate an ex post power distribution using Shapley–Shubik power index together with Banzhaf power index on real voting data, namely the data from the Chamber of Deputies of the Czech Parliament with the emphasis on the State Budget voting issues during 2006–2010 parliamentary period.     

Curvelets and Fourier Integral Operators

A recent body of work introduced new tight-frames of curvelets E. Candès, D. Donoho, in: (i) Curvelets – a suprisingly effective nonadaptive representation for objects with edges (A. Cohen, C. Rabut, L. Schumaker (Eds.)), Vanderbilt University Press, Nashville, 2000, pp. 105–120; (ii) http://www.acm.caltech.edu/~emmanuel/publications.html, 2002 to address key problems in approximation theory and image processing. This paper shows that curvelets essentially provide optimally sparse representations of Fourier Integral Operators. To cite this article: E. Candès, L. Demanet, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

Hereditarily aspherical compacta

The notion of (strongly) hereditarily aspherical compacta introduced by Daverman (1991) is modified. The main results are: Theorem. If is a hereditarily aspherical compactum, then ANR. In particular, is strongly hereditarily aspherical.

Theorem. Suppose is a cell-like map of compacta and is shape aspherical for each closed subset of . Then

1.

Y is hereditarily shape aspherical,

2.

is a hereditary shape equivalence,

3.

.

Theorem. Suppose is a group containing integers. Then the following conditions are equivalent:

1.

and ,

2.

.

Theorem. Suppose is a group containing integers. If and , then is hereditarily shape aspherical.

Theorem. Let be a two-dimensional, locally connected and semilocally simply connected compactum. Then, for any compactum

     

Embeddings of open manifolds

Let be the simplicial group of homeomorphisms of . The following theorems are proved.

Theorem A. Let be a topological manifold of dim 5 with a finite number of tame ends , . Let be the simplicial group of end preserving homeomorphisms of . Let be a periodic neighborhood of each end in , and let be manifold approximate fibrations. Then there exists a map such that the homotopy fiber of is equivalent to , the simplicial group of homeomorphisms of which have compact support.

Theorem B. Let be a compact topological manifold of dim 5, with connected boundary , and denote the interior of by . Let be the restriction map and let be the homotopy fiber of over . Then is isomorphic to for , where is the concordance space of .

Theorem C. Let be a manifold approximate fibration with dim 5. Then there exist maps and for , such that , where is a compact and connected manifold and is the infinite cyclic cover of .

     

On close to linear cocycles

If we have a flow and a cocycle on this flow, , then is called close to linear if can be written as the direct sum of a linear (constant) cocycle and a cocycle in the closure of the coboundaries. Many of the desirable consequences of linearity hold for such cocycles and, in fact, a close to linear cocycle is cohomologous to a cocycle which is norm close to a linear one. Furthermore in the uniquely ergodic case all cocycles are close to linear. We also establish that a close to linear cocycle which is covering is cohomologous to one with the special property that it can be extended by piecewise linearity to an invertible cocycle from to itself. This implies that a suspension obtained from a close to linear cocycle is isomorphic to a time change of the suspension obtained from the identity cocycle.

     

Subaveraging estimate for

Let be a smooth real hypersurface of and a compact submanifold of . We generalize a result of A. Boggess and R. Dwilewicz giving, under some geometric conditions on and , an estimate of the submeanvalue on of any function on a neighbourhood of , by the norm of on a neighbourhood of in .

     

Minimal rank and reflexivity of operator spaces

Let be an -dimensional space of linear operators between the linear spaces and over an algebraically closed field . Improving results of Larson, Ding, and Li and Pan we show the following.

Theorem. Let be a basis of . Assume that every nonzero operator in has rank larger than . Then a linear operator belongs to if and only if for every , is a linear combination of .

     

Real connective K-theory and the quaternion group

Let be the real connective K-theory spectrum. We compute and for groups whose Sylow 2-subgroup is quaternion of order 8. Using this we compute the coefficients of the fixed points of the Tate spectrum for and . The results provide a counterexample to the optimistic conjecture of Greenlees and May [9, Conj. 13.4], by showing, in particular, that is not a wedge of Eilenberg-Mac Lane spectra, as occurs for groups of prime order.

     

Approximation of the equilibrium distribution by distributions of equal point charges with minimal energy

Let denote the classical equilibrium distribution (of total charge ) on a convex or -smooth conductor in with nonempty interior. Also, let be any th order ``Fekete equilibrium distribution' on , defined by point charges at th order ``Fekete points'. (By definition such a distribution minimizes the energy for -tuples of point charges on .) We measure the approximation to by for by estimating the differences in potentials and fields,

both inside and outside the conductor . For dimension we obtain uniform estimates at distance from the outer boundary of . Observe that throughout the interior of (Faraday cage phenomenon of electrostatics), hence on the compact subsets of . For the exterior of the precise results are obtained by comparison of potentials and energies. Admissible sets have to be regular relative to capacity and their boundaries must allow good Harnack inequalities. For the passage to interior estimates we develop additional machinery, including integral representations for potentials of measures on Lipschitz boundaries and bounds on normal derivatives of interior and exterior Green functions. Earlier, one of us had considered approximations to the equilibrium distribution by arbitrary distributions of equal point charges on . In that context there is an important open problem for the sphere which is discussed at the end of the paper.

     

Approximation by polynomials with nonnegative coefficients and the spectral theory of positive operators

For a compact subset of symmetric with respect to conjugation and a continuous function, we obtain sharp conditions on and that insure that can be approximated uniformly on by polynomials with nonnegative coefficients. For a real Banach space, a closed but not necessarily normal cone with , and a bounded linear operator with , we use these approximation theorems to investigate when the spectral radius of belongs to its spectrum . A special case of our results is that if is a Hilbert space, is normal and the 1-dimensional Lebesgue measure of is zero, then . However, we also give an example of a normal operator (where is unitary and ) for which and .

     

Existence of unliftable modules

Let be a commutative Noetherian local ring, and let where is a non-zerodivisor of contained in . Then a finitely generated -module is said to lift to if there exists a finitely generated -module such that is -regular and . In this paper we give a general construction of finitely generated -modules of finite projective dimension over which fail to lift to provided and the depth of is at least 2.

     

Perturbing a product of stable flows

Suppose that and are axiom A flows with attractors and . Then the attractor for the product flow on the product manifold is no longer hyperbolic (although there is a hyperbolic action of ).

It is easy to see that the attractor cannot explode but we show here that it cannot implode: for any flow sufficiently close to any attractor whose basin is not too thin is -dense in .

     

Fine structure of the space of spherical minimal immersions

The space of congruence classes of full spherical minimal immersions of a given source dimension and algebraic degree is a compact convex body in a representation space of the special orthogonal group . In Ann. of Math. 93 (1971), 43--62 DoCarmo and Wallach gave a lower bound for and conjectured that the estimate was sharp. Toth resolved this ``exact dimension conjecture' positively so that all irreducible components of became known. The purpose of the present paper is to characterize each irreducible component of in terms of the spherical minimal immersions represented by the slice . Using this geometric insight, the recent examples of DeTurck and Ziller are located within .

     

A uniqueness theorem for harmonic functions

The main result of this note is the following theorem: Theorem 1. Let be a half ball in and . Assume that is in and harmonic in , and that for every positive integer there exists a constant such that

Then .

First we prove it for , and then we show by induction that it holds for all .

     

Approximation from locally finite-dimensional shift-invariant spaces

After exploring some topological properties of locally finite-dimensional shift-invariant subspaces of , we show that if provides approximation order , then it provides the corresponding simultaneous approximation order. In the case is generated by a compactly supported function in , it is proved that provides approximation order in the -norm with if and only if the generator is a derivative of a compactly supported function that satisfies the Strang-Fix conditions.