Core theorems for double subsequences and rearrangements

The concepts of subsequence and rearrangement of double sequence are used to present multidimensional analogues of the following core questions. If x is a bounded real sequence and A is a matrix summability method, under what conditions does there exist y, a subsequence (rearrangement) of x such that each number t in the core of x is a limit point of Ay?     

Semigroup identities and proofs

Tamura proved that for any semigroup word U(x, y), if every group satisfying an identity of the form yx ~ xU(x, y)y is abelian, then so is every semigroup that satisfies that identity. Because a group has an identity element and the cancellation property, it is easier to show that a group is abelian than that a semigroup is. If we know that it is, then there must be a sequence of substitutions using xU(x, y)y ~ yx that transforms xy to yx. We examine such sequences and propose finding them as a challenge to proof by computer. Also, every model of y ~ xU(x, y)x is a group. This raises a similar challenge, which we explore in the special case y ~ x ^m y ^p x ⁿ . In addition, we determine the free model with two generators of some of these identities. In particular, we find that the free model for y ~ x ² yx ² has order 32 and is the product of D ₄ (the symmetries of a square), C ₂, and C ₄, and point out relations between such identities and Burnside’s Problem concerning models of x ⁿ ~ y ⁿ . We also examine several identities not related to groups.     

A system of cubic diophantine equations

In this paper we solve x³ + y + 1 ? xyz = 0 completely and study a pair of simultaneous cubic diophantine equations (1) x | y³ + 1 and y | x³ + 1, where x and y are positive integers. The main result in this paper is that there exist an infinite number of sequences such that x and y satisfy (1) if and only if they are consecutive terms of one of these sequences.     

Computing the Selmer group of an isogeny between Abelian varieties using a further isogeny to a Jacobian

This article describes an algorithm for computing the Selmer group of an isogeny between abelian varieties. This algorithm applies when there is an isogeny from the image abelian variety to the Jacobian of a curve. The use of an auxiliary Jacobian simplifies the determination of locally trivial cohomology classes. An example is presented where the rational solutions to x⁴+(y²+1)(x+y)=0 are determined.     

A solution to a spectral poset problem of Lewis and Ohm

We show that there is a 1-dimensional (countable) non-spectral poset X such that for all x≠y∈X, ↑x∩↑y and ↓x∩↓y are finite subsets. On the other hand, we obtain some sufficient conditions for posets to be spectral.     

Max-min of polynomials and exponential diophantine equations

In this paper we study the maximum-minimum value of polynomials over the integer ring Z. In particular, we prove the following: Let F(x,y) be a polynomial over Z. Then, maxx∈Z(T)miny∈Z|F(x,y)|=o(T1/2) as T→∞ if and only if there is a positive integer B such that maxx∈Zminy∈Z|F(x,y)|?B. We then apply these results to exponential diophantine equations and obtain that: Let f(x,y), g(x,y) and G(x,y) be polynomials over Q, G(x,y)∈(Q[x,y]−Q[x])∪Q, and b a positive integer. For every α in Z, there is a y in Z such that f(α,y)+g(α,y)bG(α,y)=0 if and only if for every integer α there exists an h(x)∈Q[x] such that f(x,h(x))+g(x,h(x))bG(x,h(x))≡0, and h(α)∈Z.     

Transitive orientations in bull-reducible Berge graphs

A bull is a graph with five vertices r,y,x,z,s and five edges ry, yx, yz, xz, zs. A graph G is bull-reducible if every vertex of G lies in at most one bull of G. We prove that every bull-reducible Berge graph G that contains no antihole is weakly chordal, or has a homogeneous set, or is transitively orientable. This yields a fast polynomial time algorithm to color the vertices of such a graph exactly.     

Bounding the diameter of a distance-transitive graph

A graph Γ is distance-transitive if for all vertices u, v, x, y such that d(u, v) = d(x, y) there is an automorphism h of Γ such that uh = x, vh = y. We show how to find a bound for the diameter of a bipartite distance-transitive graph given a bound for the order |G_α| of the stabilizer of a vertex.     

Characterizations of isomorphisms and derivations of some algebras

Let ? be a zero-product preserving bijective bounded linear map from a unital algebra A onto a unital algebra B such that ?(1)=k. We show that if A is a CSL algebra on a Hilbert space or a J-lattice algebra on a Banach space then there exists an isomorphism ψ from A onto B such that ?=kψ. For a nest algebra A in a factor von Neumann algebra, we characterize the linear maps on A such that δ(x)y+xδ(y)=0 for all x,y∈A with xy=0.     

The diophantine equation x3 + 3y3 = 2n

It is proved that the equation of the title has a finite number of integral solutions (x, y, n) and necessary conditions are given for (x, y, n) in order that it can be a solution (Theorem 2). It is also proved that for a given odd x₀ there is at most one integral solution (y, n), n ≥ 3, to x₀³ + 3y³ = 2ⁿ and for a given odd y₀ there is at most one integral solution (x, n), n ≥ 3, to x³ + 3y₀³ = 2ⁿ.     

Strong commutativity preserving maps in prime rings with involution

Let A be a prime ring of characteristic not 2, with center Z(A) and with involution *. Let S be the set of symmetric elements of A. Suppose that f:S→A is an additive map such that [f(x),f(y)]=[x,y] for all x,y∈S. Then unless A is an order in a 4-dimensional central simple algebra, there exists an additive map μ:S→Z(A) such that f(x)=x+μ(x) for all x∈S or f(x)=-x+μ(x) for all x∈S.     

Analogues of some Tauberian theorems for bounded variation

In this paper definitions for “bounded variation”, “subsequences”, “Pringsheim limit points”, and “stretchings” of a double sequence are presented. Using these definitions and the notion of regularity for four dimensional matrices, the following two questions will be answered. First, if there exists a four dimensional regular matrix A such that Ay = Σ _k,l=1,1 ^∞∞ a _m,n,k,l y _k,l is of bounded variation (BV) for every subsequence y of x, does it necessarily follow that x ∈ BV? Second, if there exists a four dimensional regular matrix A such that Ay ∈ BV for all stretchings y of x, does it necessarily follow that x ∈ BV? Also some natural implications and variations of the two Tauberian questions above will be presented.     

Clique or hole in claw-free graphs

Given a claw-free graph and two non-adjacent vertices x and y without common neighbours we prove that there exists a hole through x and y unless the graph contains the obvious obstruction, namely a clique separating x and y. We derive two applications: We give a necessary and sufficient condition for the existence of an induced x-z path through y, where x,y,z are prescribed vertices in a claw-free graph; and we prove an induced version of Menger?s theorem between four terminal vertices. Finally, we improve the running time for detecting a hole through x and y and for the Three-in-a-Tree problem, if the input graph is claw-free.     

On the complexity of paths avoiding forbidden pairs

Given a graph G=(V,E), two fixed vertices s,t∈V and a set F of pairs of vertices (called forbidden pairs), the problem of a path avoiding forbidden pairs is to find a path from s to t that contains at most one vertex from each pair in F. The problem is known to be NP-complete in general and a few restricted versions of the problem are known to be in P. We study the complexity of the problem for directed acyclic graphs with respect to the structure of the forbidden pairs.We write x?y if and only if there exists a path from x to y and we assume, without loss of generality, that for every forbidden pair (x,y)∈F we have x?y. The forbidden pairs have a halving structure if no two pairs (u,v),(x,y)∈F satisfy v?x or v=x and they have a hierarchical structure if no two pairs (u,v),(x,y)∈F satisfy u?x?v?y. We show that the PAFP problem is NP-hard even if the forbidden pairs have the halving structure and we provide a surprisingly simple and efficient algorithm for the PAFP problem with the hierarchical structure.     

Note on Locating Pairs of Vertices on Hamiltonian Cycles

Given a fixed positive integer k ≥ 2, let G be a simple graph of order n ≥ 6k. It is proved that if the minimum degree of G is at least n/2 + 1, then for every pair of vertices x and y, there exists a Hamiltonian cycle such that the distance between x and y along that cycle is precisely k.     

Optimal Pricing for Optimal Transport

Suppose that c(x, y) is the cost of transporting a unit of mass from x ∈ X to y ∈ Y and suppose that a mass distribution μ on X is transported optimally (so that the total cost of transportation is minimal) to the mass distribution ν on Y. Then, roughly speaking, the Kantorovich duality theorem asserts that there is a price f(x) for a unit of mass sold (say by the producer to the distributor) at x and a price g(y) for a unit of mass sold (say by the distributor to the end consumer) at y such that for any x ∈ X and y ∈ Y, the price difference g(y) ? f(x) is not greater than the cost of transportation c(x, y) and such that there is equality g(y) ? f(x) = c(x, y) if indeed a nonzero mass was transported (via the optimal transportation plan) from x to y. We consider the following optimal pricing problem: suppose that a new pricing policy is to be determined while keeping a part of the optimal transportation plan fixed and, in addition, some prices at the sources of this part are also kept fixed. From the producers’ side, what would then be the highest compatible pricing policy possible? From the consumers’ side, what would then be the lowest compatible pricing policy possible? We have recently introduced and studied settings in c-convexity theory which gave rise to families of c-convex c-antiderivatives, and, in particular, we established the existence of optimal c-convex c-antiderivatives and explicit constructions of these optimizers were presented. In applications, it has turned out that this is a unifying language for phenomena in analysis which used to be considered quite apart. In the present paper we employ optimal c-convex c-antiderivatives and conclude that these are natural solutions to the optimal pricing problems mentioned above. This type of problems drew attention in the past and existence results were previously established in the case where X = Y = ? ⁿ under various specifications. We solve the above problem for general spaces X, Y and real-valued, lower semicontinuous cost functions c. Furthermore, an explicit construction of solutions to the general problem is presented.     

Dictators on blocks: Generalizations of social choice impossibility theorems

This paper extends impossibility theorems of Arrow and others to cases in which social comparisons between alternatives in a set X of social alternatives may be made only for each pair {x, y} in a certain subset of distinct pairs taken from X. With E the set of pairs within which social comparisons may be made, G = (X, E) is an undirected graph without loops. The social comparison between x and y for {x, y} ∈ E is to be based on the preferences of individuals in a finite society S. Each individual is presumed to prefer x to y or prefer y to x (not both) for every {x, y} ∈ E and may hold any preference relation that does not cycle in G. A profile is an assignment of one such relation to each individual in S. The paper examines binary social comparison procedures which map each profile into a social preference relation over the pairs in E, subject to x socially preferred to y whenever {x, y} ∈ E and everyone in S prefers x to y. Individual i ∈ S is a dictator [weak dictator] on {x, y} ∈ E iff x is socially preferred to y [x ranks as high as y socially] whenever i prefers x to y, and similarly with x and y interchanged, regardless of the preferences of the other individuals in S. An individual is a dictator [weak dictator] on a subgraph of G iff he is a dictator [weak dictator] on every edge in the subgraph. Under each of three ordering conditions on social preferences, there is a dictator or weak dictator on every block of G which has three or more points, different blocks can have different dictators, and bridges in E need not have dictators.     

Score vectors of tournaments

A tournament T on any set X is a dyadic relation such that for any x, y ∈ X (a) (x, x) ? T and (b) if x ≠ y then (x, y) ∈ T iff (y, x) ? T. The score vector of T is the cardinal valued function defined by R(x) = |{y ∈ X : (x, y) ∈ T}|. We present theorems for infinite tournaments analogous to Landau's necessary and sufficient conditions that a vector be the score vector for some finite tournament. Included also is a new proof of Landau's theorem based on a simple application of the “marriage” theorem.