The negative cycles polyhedron and hardness of checking some polyhedral properties

Given a graph G=(V,E) and a weight function on the edges w:E→ℝ, we consider the polyhedron P(G,w) of negative-weight flows on G, and get a complete characterization of the vertices and extreme directions of P(G,w). Based on this characterization, and using a construction developed in Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008), we show that, unless P=NP, there is no output polynomial-time algorithm to generate all the vertices of a 0/1-polyhedron. This strengthens the NP-hardness result of Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008) for non 0/1-polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1-polytopes (Bussiech and Lübbecke in Comput. Geom., Theory Appl. 11(2):103–109, 1998). As further applications, we show that it is NP-hard to check if a given integral polyhedron is 0/1, or if a given polyhedron is half-integral. Finally, we also show that it is NP-hard to approximate the maximum support of a vertex of a polyhedron in ℝ ⁿ within a factor of 12/n.     

Leading coefficients of Kazhdan–Lusztig polynomials for Deodhar elements

We show that the leading coefficient of the Kazhdan–Lusztig polynomial P _x,w (q) known as μ(x,w) is always either 0 or 1 when w is a Deodhar element of a finite Weyl group. The Deodhar elements have previously been characterized using pattern avoidance in Billey and Warrington (J. Algebraic Combin. 13(2):111–136, [2001]) and Billey and Jones (Ann. Comb. [2008], to appear). In type A, these elements are precisely the 321-hexagon avoiding permutations. Using Deodhar’s algorithm (Deodhar in Geom. Dedicata 63(1):95–119, [1990]), we provide some combinatorial criteria to determine when μ(x,w)=1 for such permutations w. The author received support from NSF grants DMS-9983797 and DMS-0636297.     

The symmetrized Sine addition formula

As a continuation of An and Yang (Integral Equ Oper Theory 66:183–195, 2010) in this paper, the symmetrized Sine addition formula

Tetravalent half-arc-transitive graphs of order 2<Emphasis Type="Italic">pq</Emphasis>

A graph is half-arc-transitive if its automorphism group acts transitively on its vertex set, edge set, but not arc set. Let p and q be primes. It is known that no tetravalent half-arc-transitive graphs of order 2p ² exist and a tetravalent half-arc-transitive graph of order 4p must be non-Cayley; such a non-Cayley graph exists if and only if p−1 is divisible by 8 and it is unique for a given order. Based on the constructions of tetravalent half-arc-transitive graphs given by Marušič (J. Comb. Theory B 73:41–76, 1998), in this paper the connected tetravalent half-arc-transitive graphs of order 2pq are classified for distinct odd primes p and q.     

On maximal actions and <Emphasis Type="Italic">w</Emphasis>-maximal actions of finite hypergroups

Sunder and Wildberger (J. Algebr. Comb. 18, 135–151, 2003) introduced the notion of actions of finite hypergroups, and studied maximal irreducible actions and *-actions. One of the main results of Sunder and Wildberger states that if a finite hypergroup K admits an irreducible action which is both a maximal action and a *-action, then K arises from an association scheme. In this paper we will first show that an irreducible maximal action must be a *-action, and hence improve Sunder and Wildberger’s result (Theorem 2.9). Another important type of actions is the so-called w-maximal actions. For a w-maximal action π:K→Aff (X), we will prove that π is faithful and |X|≥|K|, and |K| is the best possible lower bound of |X|. We will also discuss the strong connectivity of the digraphs induced by a w-maximal action.     

Quotient spaces determined by algebras of continuous functions

We prove that if X is a locally compact σ-compact space, then on its quotient, γ(X) say, determined by the algebra of all real valued bounded continuous functions on X, the quotient topology and the completely regular topology defined by this algebra are equal. It follows from this that if X is second countable locally compact, then γ(X) is second countable locally compact Hausdorff if and only if it is first countable. The interest in these results originated in [1] and [7] where the primitive ideal space of a C*-algebra was considered.     

Distributive Lattices with a Generalized Implication: Topological Duality

In this paper we introduce the notion of generalized implication for lattices, as a binary function ⇒ that maps every pair of elements of a lattice to an ideal. We prove that a bounded lattice A is distributive if and only if there exists a generalized implication ⇒ defined in A satisfying certain conditions, and we study the class of bounded distributive lattices A endowed with a generalized implication as a common abstraction of the notions of annihilator (Mandelker, Duke Math J 37:377–386, 1970), Quasi-modal algebras (Celani, Math Bohem 126:721–736, 2001), and weakly Heyting algebras (Celani and Jansana, Math Log Q 51:219–246, 2005). We introduce the suitable notions of morphisms in order to obtain a category, as well as the corresponding notion of congruence. We develop a Priestley style topological duality for the bounded distributive lattices with a generalized implication. This duality generalizes the duality given in Celani and Jansana (Math Log Q 51:219–246, 2005) for weakly Heyting algebras and the duality given in Celani (Math Bohem 126:721–736, 2001) for Quasi-modal algebras.     

Weak Type Inequality for a Family of Singular Integral Operators Related with the Gaussian Measure

In this paper we study a family of singular integral operators that generalizes the higher order Gaussian Riesz Transforms and find the right weight w to make them continuous from L ¹(wdγ) into L ^1, ∞(dγ), being Some boundedness properties of these operators had already been derived by Urbina (Ann Scuola Norm Sup Pisa Cl Sci 17(4):531–567, 1990) and Pérez (J Geom Anal 11(3):491–507, 2001).      

First-Fit is Linear on Posets Excluding Two Long Incomparable Chains

A poset is (r+s)(\underline{r}+\underline{s})-free if it does not contain two incomparable chains of size r and s, respectively. We prove that when r and s are at least 2, the First-Fit algorithm partitions every (r+s)(\underline{r}+\underline{s})-free poset P into at most 8(r − 1)(s − 1)w chains, where w is the width of P. This solves an open problem of Bosek et al. (SIAM J Discrete Math 23(4):1992–1999, 2010).     

赋权图的w密度和w平衡性

The notion of w-density for the graphs with positive weights on vertices and nonnegative weights on edges is introduced. A weighted graph is called w-balanced if its w-density is no less than the w-density of any subgraph of it. In this paper,a good characterization of w-balanced weighted graphs is given. Applying this characterization ,many large w-balanced weighted graphs are formed by combining smaller ones. In the case where a graph is not w-balanced,a polynomial-time algorithm to find a subgraph of maximum w-density is proposed. It is shown that the w-density theory is closely related to the study of SEW(G,w) games.     

On-line Chain Partitioning of Up-growing Interval Orders

On-line chain partitioning problem of on-line posets has been open for the past 20 years. The best known on-line algorithm uses chains to cover poset of width w. Felsner (Theor. Comput. Sci., 175(2):283–292, 1997) introduced a variant of this problem considering only up-growing posets, i.e. on-line posets in which each new point is maximal at the moment of its arrival. He presented an algorithm using chains for width w posets and proved that his solution is optimal. In this paper, we study on-line chain partitioning of up-growing interval orders. We prove lower bound and upper bound to be 2w−1 for width w posets. Piotr Micek and Bartłomiej Bosek are scholars of the project which is co-financed from the European Social Fund and national budget in the frame of The Integrated Regional Operational Programme.     

Quasi exponential decay of a finite difference space discretization of the 1-d wave equation by pointwise interior stabilization

We consider the wave equation on an interval of length 1 with an interior damping at ξ. It is well-known that this system is well-posed in the energy space and that its natural energy is dissipative. Moreover, as it was proved in Ammari et al. (Asymptot Anal 28(3–4):215–240, 2001), the exponential decay property of its solution is equivalent to an observability estimate for the corresponding conservative system. In this case, the observability estimate holds if and only if ξ is a rational number with an irreducible fraction x = \fracpq,\xi=\frac{p}{q}, where p is odd, and therefore under this condition, this system is exponentially stable in the energy space. In this work, we are interested in the finite difference space semi-discretization of the above system. As for other problems (Zuazua, SIAM Rev 47(2):197–243, 2005; Tcheugoué Tébou and Zuazua, Adv Comput Math 26:337–365, 2007), we can expect that the exponential decay of this scheme does not hold in general due to high frequency spurious modes. We first show that this is indeed the case. Secondly we show that a filtering of high frequency modes allows to restore a quasi exponential decay of the discrete energy. This last result is based on a uniform interior observability estimate for filtered solutions of the corresponding conservative semi-discrete system.     

Autotopisms and Isotopisms of Trilinear Alternating Forms

For a trilinear alternating form f on a vector space V, a generalization of the group of automorphisms group of autotopisms Atp(f), is introduced. An autotopism of f is a triple (α, β, γ) of automorphisms of V satisfying f(u, v, w) = f(α(u), β(v), γ(w)) for all u, v, w ∈ V. Basic results concerning this group are presented, and it is shown that the subgroup of Atp(f) containing autotopisms with identity in one coordinate is Abelian and that a mapping in this group has no fixed points if and only if its order is not a power of two.

Moreover, the notion of equivalence of two trilinear alternating forms is generalized in a similar way, and a partial result is given.

Examples of forms with both trivial (Atp(f) = Aut(f)) and nontrivial groups of autotopisms are presented.     

Fixed-point-free elements in <Emphasis Type="Italic">p</Emphasis>-groups

In this paper we prove that there exists no function F(m, p) (where the first argument is an integer and the second a prime) such that, if G is a finite permutation p-group with m orbits, each of size at least p ^F(m,p), then G contains a fixed-point-free element. In particular, this gives an answer to a conjecture of Peter Cameron; see [4], [6].     

Ring semigroups whose subsemigroups form a chain

A multiplicative semigroup S is called a ring semigroup if an addition may be defined on S so that (S,+,⋅) is a ring. Such semigroups have been well-studied in the literature (see Bell in Words, Languages and Combinatorics, pp. 24–31, World Scientific, Singapore, 1994; Jones in Semigroup Forum 47(1):1–6, 1993; Jones and Ligh in Semigroup Forum 17(2):163–173, 1979). In this note, we use Mihăilescu’s Theorem (formerly Catalan’s Conjecture) to characterize the ring semigroups whose subsemigroups containing 0 form a chain with respect to set inclusion.     

A comparison of asymptotic analytical formulae with finite-difference approximations for pricing zero coupon bond

In this paper we solve numerically a degenerate parabolic equation with dynamical boundary condition for pricing zero coupon bond and compare numerical solution with asymptotic analytical solution. First, we discuss an approximate analytical solution of the model and its order of accuracy. Then, starting from the divergent form of the equation we implement the finite-volume method of Song Wang (IMA J Numer Anal 24:699–720, 2004) to discretize the differential problem. We show that the system matrix of the discretization scheme is a M-matrix, so that the discretization is monotone. This provides the non-negativity of the price with respect to time if the initial distribution is nonnegative. Numerical experiments demonstrate second order of convergence for difference scheme when the node is not too close to the point of degeneration.     

Convergence rate of McCormick relaxations

Theory for the convergence order of the convex relaxations by McCormick (Math Program 10(1):147–175, 1976) for factorable functions is developed. Convergence rules are established for the addition, multiplication and composition operations. The convergence order is considered both in terms of pointwise convergence and of convergence in the Hausdorff metric. The convergence order of the composite function depends on the convergence order of the relaxations of the factors. No improvement in the order of convergence compared to that of the underlying bound calculation, e.g., via interval extensions, can be guaranteed unless the relaxations of the factors have pointwise convergence of high order. The McCormick relaxations are compared with the αBB relaxations by Floudas and coworkers (J Chem Phys, 1992, J Glob Optim, 1995, 1996), which guarantee quadratic convergence. Illustrative and numerical examples are given.     

Steiner triple systems with two disjoint subsystems

It is shown that there exists a triangle decomposition of the graph obtained from the complete graph of order v by removing the edges of two vertex disjoint complete subgraphs of orders u and w if and only if u,w, and v are odd, (mod 3), and . Such decompositions are equivalent to group divisible designs with block size 3, one group of size u, one group of size w, and v – u – w groups of size 1. This result settles the existence problem for Steiner triple systems having two disjoint specified subsystems, thereby generalizing the well‐known theorem of Doyen and Wilson on the existence of Steiner triple systems with a single specified subsystem. © 2005 Wiley Periodicals, Inc. J Combin Designs     

More Problems for MaxCon: Contingent Particularity and Stuff-Thing Coincidence

Ned Markosian argues (Australasian Journal of Philosophy 76:213-228, 1998a; Australasian Journal of Philosophy 82:332-340, 2004a, The Monist 87:405-428, 2004b) that simples are ‘maximally continuous’ entities. This leads him to conclude that there could be non-particular ‘stuff’ in addition to things. I first show how an ensuing debate on this issue McDaniel (Australasian Journal of Philosophy 81(2):265-275, 2003); Markosian (Australasian Journal of Philosophy 82:332-340, 2004a) ended in deadlock. I attempt to break the deadlock. Markosian’s view entails stuff-thing coincidence, which I show is just as problematic as the more oft-discussed thing-thing coincidence. Also, the view entails that every particular is only contingently so. If there is a world W like our own, but with ether, then there would be only one object in W. But, since merely adding ether to a world does not destroy the entities in it, then W contains counterparts of all the entities in the actual world—they just are not things. Hence, if simples are maximally continuous, then every actual particular is only contingently so. This in turn entails the following disjunction: (i) identity is contingent or intransitive, or (ii) there are no things at all in the actual world, or (iii) the distinction between stuff and things is one without a difference. I recommend that we reject this stuff-thing dualism.