Multigraphs with Δ ≥ 3 are Totally-(2Δ−1)-Choosable

The total graph T(G) of a multigraph G has as its vertices the set of edges and vertices of G and has an edge between two vertices if their corresponding elements are either adjacent or incident in G. We show that if G has maximum degree Δ(G), then T(G) is (2Δ(G) − 1)-choosable. We give a linear-time algorithm that produces such a coloring. The best previous general upper bound for Δ(G) > 3 was , by Borodin et al. When Δ(G) = 4, our algorithm gives a better upper bound. When Δ(G)∈{3,5,6}, our algorithm matches the best known bound. However, because our algorithm is significantly simpler, it runs in linear time (unlike the algorithm of Borodin et al.).     

(S − 1,S) Perishable systems with stochastic leadtimes

This article discusses a one-to-one ordering perishable system, in which reorders are processed in the order of their arrival and the processing times are arbitrarily distributed, and as such, the leadtimes are not independent. The Markov renewal techniques are employed to obtain the various operating characteristics for the case of Poisson demand and exponential lifetimes. The problem of minimizing the steady state expected cost rate is also discussed, and in the special case of exponential processing times, the optimal stock level is derived explicitly.     

The Contraction of S2p−1 to Hp−1

 A contraction of the sphere , considered as the homogeneous space , to the Heisenberg group is defined. The infinite dimensional irreducible unitary representations of Heisenberg group are then shown to be the limits of the irreducible representations of which are class-1 with respect to . Our results generalise the earlier results of Fulvio Ricci. (Received 1 July 1998; in revised form 3 November 1998)     

The Johnson graph J(d,r) is unique if (d,r) ≠ (2, 8)

We use the classical Root Systems to show the Johnson graph J(d, r) (2 ⩽ 2d ⩽ r < ∞) is the unique distance-regular graph with its intersection numbers when (d, r) ≠ (2, 8). Since this exceptional case has been dealt with by Chang [6] this completes the characterization problem for Johnson graph.     

On Turán’s (3,4)-problem with forbidden subgraphs

We identify three 3-graphs on five vertices that are missing in all known extremal configurations for Turán’s (3,4)-problem and prove Turán’s conjecture for 3-graphs that are additionally known not to contain any induced copies of these 3-graphs. Our argument is based on an (apparently) new technique of “indirect interpretation” that allows us to retrieve additional structure from hypothetical counterexamples to Turán’s conjecture, but in rather loose and limited sense. We also include two miscellaneous calculations in flag algebras that prove similar results about some other additional forbidden subgraphs.     

L(d1, d2,..., dt)-Number λ(Cn; d1, d2,...,dt) of Cycles

An L(d1,d2,...,dt)-labeling of a graph G is a function f from its vertex set V(G) to the set {0, 1,..., k} for some positive integer k such that {f(x) - f(y)| ≥ di, if the distance between vertices x and y in G is equal to i for i = 1,2,...,t. The L(d1,d2,...,dt)-number λ(G;d1,d2,... ,dt) of G is the smallest integer number k such that G has an L(d1,d2,... ,dt)labeling with max{f(x)|x ∈ V(G)} = k. In this paper, we obtain the exact values for λ(Cn; 2, 2,1) and λ(Cn; 3, 2, 1), and present lower and upper bounds for λ(Cn; 2,..., 2,1,..., 1)     

Randomized first order algorithms with applications to ℓ 1-minimization

In this paper we propose randomized first-order algorithms for solving bilinear saddle points problems. Our developments are motivated by the need for sublinear time algorithms to solve large-scale parametric bilinear saddle point problems where cheap online assessment of the solution quality is crucial. We present the theoretical efficiency estimates of our algorithms and discuss a number of applications, primarily to the problem of ? ₁ minimization arising in sparsity-oriented signal processing. We demonstrate, both theoretically and by numerical examples, that when seeking for medium-accuracy solutions of large-scale ? ₁ minimization problems, our randomized algorithms outperform significantly (and progressively as the sizes of the problem grow) the state-of-the art deterministic methods.     

Linking (n − 2)-dimensional panels inn-space I: (k − 1,k)-graphs and (k − 1,k)-frames

A (k – 1,k)-graph is a multi-graph satisfyinge (k – 1)v – k for every non-empty subset ofe edges onv vertices, with equality whene = |E(G)|. A (k – 1,k)-frame is a structure generalizing an (n – 2, 2)-framework inn-space, a structure consisting of a set of (n – 2)-dimensional bodies inn-space and a set of rigid bars each joining a pair of bodies using ball joints. We prove that a graph is the graph of a minimally rigid (with respect to edges) (k – 1,k)-frame if and only if it is a (k – 1,k)-graph. Rigidity here means infinitesimal rigidity or equivalently statical rigidity.     

The tree and forest spaces with applications to initial-value problem methods

Tree and forest spaces, which are at the heart of the theory of Runge–Kutta methods, are formulated recursively, and it is shown that the forest space is an algebra. To obtain order conditions in a systematic manner, Banach algebras are introduced to generate both the elementary weights for a general Runge–Kutta method and the corresponding quantities based on the Picard integral. To connect these two concepts, the Picard integral is written as the limiting case of an s-stage Runge–Kutta method, equivalent to s steps of the Euler method, as s tends to infinity. This approach makes it possible to make direct use of the tree space without going over to the dual space. By choosing linear combinations of trees, appropriate to a particular application, it is shown how to obtain alternative ways of writing the order conditions. This leads to a simpler and more direct derivation of particular methods.     

The generalized singular value decomposition and the general (A-λB)-problem

In the study of the canonical structure of matrix pencilsA-B, the column and row nullities ofA andB and the possible common nullspaces give information about the Kronecker structure ofA-B. It is shown how to extract the significant information concerning these nullspaces from the generalized singular value decomposition (GSVD) of the matrix pair (A, B), These properties are the basis for the RGSVD-algorithm that will be published elsewhere [9]. An algorithm for the numerical computation of the transformation matrices (V, X), used in an equivalence transformationV ^H (A-B)X, is presented and discussed. A generalizedQZ-decomposition (GQZD) of a matrix pair (A, B) is also formulated, giving a unitary equivalent transformationV ^H (A-B)Q. If during the computationsX gets too illconditioned we switch to the GQZD, sacrificing a simple diagonal structure of the transformedB-part in order to maintain stability.Dedicated to Germund Dahlquist, on the occasion of his 60th birthday.     

On the equation −Δu + e u − 1 = 0 with measures as boundary data

If Ω is a bounded domain in ${\mathbb{R}^N}$ , we study conditions on a Radon measure μ on ?Ω for solving the equation ?Δu + e ^u ? 1 = 0 in Ω with u = μ on ?Ω. The conditions are expressed in terms of Orlicz capacities.     

The central limit theorem for stationary Markov processes with normal generator—with applications to hypergroups

We extend the central limit theorem for additive functionals of a stationary, ergodic Markov chain with normal transition operator due to Gordin and Lif?ic, 1981 [A remark about a Markov process with normal transition operator, In: Third Vilnius Conference on Probability and Statistics 1, pp. 147–48] to continuous-time Markov processes with normal generators. As examples, we discuss random walks on compact commutative hypergroups as well as certain random walks on non-commutative, compact groups.     

The Monge-Ampère Equation for Strictly $(n−1)$-Convex Functions with Neumann Condition

A $C^2$ function on $\mathbb{R}^n$ is called strictly $(n-1)$-convex if the sum of any $n-1$ eigenvalues of its Hessian is positive. In this paper, we establish a global $C^2$ estimates to the Monge-Ampère equation for strictly $(n-1)$-convex functions with Neumann condition. By the method of continuity, we prove an existence theorem for strictly $(n-1)$-convex solutions of the Neumann problems.     

A regression approach to ROC surface, with applications to Alzheimer’s disease

We consider the estimation of three-dimensional ROC surfaces for continuous tests given covariates.Three way ROC analysis is important in our motivating example where patients with Alzheimer’s disease are usually classified into three categories and should receive different category-specific medical treatment.There has been no discussion on how covariates affect the three way ROC analysis.We propose a regression framework induced from the relationship between test results and covariates.We consider several practical cases and the corresponding inference procedures.Simulations are conducted to validate our methodology.The application on the motivating example illustrates clearly the age and sex effects on the accuracy for Mini-Mental State Examination of Alzheimer’s disease.