Authentication schemes from actions on graphs, groups, or rings

We propose a couple of general ways of constructing authentication schemes from actions of a semigroup on a set, without exploiting any specific algebraic properties of the set acted upon. Then we give several concrete realizations of this general idea, and in particular, we describe several authentication schemes with long-term private keys where forgery (a.k.a. impersonation) is NP-hard. Computationally hard problems that can be employed in these realizations include the Graph Colorability problem, the Diophantine problem, and many others.     

Multiple periodic solutions of scalar second order differential equations

We prove multiplicity of periodic solutions for a scalar second order differential equation with an asymmetric nonlinearity, thus generalizing previous results by Lazer and McKenna (1987) [1] and Del Pino, Manasevich and Murua (1992) [2]. The main improvement lies in the fact that we do not require any differentiability condition on the nonlinearity. The proof is based on the use of the Poincaré-Birkhoff Fixed Point Theorem.     

Numerical simulation of two-dimensional Bingham fluid flow by semismooth Newton methods

This paper is devoted to the numerical simulation of two-dimensional stationary Bingham fluid flow by semismooth Newton methods. We analyze the modeling variational inequality of the second kind, considering both Dirichlet and stress-free boundary conditions. A family of Tikhonov regularized problems is proposed and the convergence of the regularized solutions to the original one is verified. By using Fenchel’s duality, optimality systems which characterize the original and regularized solutions are obtained. The regularized optimality systems are discretized using a finite element method with (cross-grid P₁)-Q₀ elements for the velocity and pressure, respectively. A semismooth Newton algorithm is proposed in order to solve the discretized optimality systems. Using an additional relaxation, a descent direction is constructed from each semismooth Newton iteration. Local superlinear convergence of the method is also proved. Finally, we perform numerical experiments in order to investigate the behavior and efficiency of the method.     

A lower bound for the spectral radius of a digraph

We show that the spectral radius ρ(D) of a digraph D with n vertices and c₂ closed walks of length 2 satisfies Moreover, equality occurs if and only if D is the symmetric digraph associated to a -regular graph, plus some arcs that do not belong to cycles. As an application of this result, we construct new sharp upper bounds for the low energy of a digraph, which extends Koolen and Moulton bounds of the energy to digraphs.     

On the signless Laplacian spectral radius of graphs with cut vertices

In this paper, we show that among all the connected graphs with n vertices and k cut vertices, the maximal signless Laplacian spectral radius is attained uniquely at the graph G_n,k, where G_n,k is obtained from the complete graph K_n-k by attaching paths of almost equal lengths to all vertices of K_n-k. We also give a new proof of the analogous result for the spectral radius of the connected graphs with n vertices and k cut vertices (see [A. Berman, X.-D. Zhang, On the spectral radius of graphs with cut vertices, J. Combin. Theory Ser. B 83 (2001) 233-240]). Finally, we discuss the limit point of the maximal signless Laplacian spectral radius.     

Inverting linear combinations of identity and generalized Catalan matrices

We introduce the notion of the generalized Catalan matrix as a kind of lower triangular Toeplitz matrix whose nonzero elements involve the generalized Catalan numbers. Inverse of the linear combination of the Pascal matrix with the identity matrix is computed in Aggarwala and Lamoureux (2002) [1]. In this paper, continuing this idea, we invert various linear combinations of the generalized Catalan matrix with the identity matrix. A simple and efficient approach to invert the Pascal matrix plus one in terms of the Hadamard product of the Pascal matrix and appropriate lower triangular Toeplitz matrices is considered in Yang and Liu (2006) [14]. We derive representations for inverses of linear combinations of the generalized Catalan matrix and the identity matrix, in terms of the Hadamard product which includes the Generalized Catalan matrix and appropriate lower triangular Toeplitz matrix.     

Hypergeometric systems of Gelfand-type equations and series in orthogonal polynomials

We describe multivariable hypergeometric series in orthogonal polynomials. These series are solutions of special systems of Gelfand-type equations. The difference andq-analogs are also given.     

The First in Vivo Observation of C–N Coupling in Mammalian Brain

[5-¹³C,¹⁵N]Glutamine, with ¹J(¹³C–¹⁵N) of 16 Hz, was observed in vivo in the brain of spontaneously breathing rats by ¹³C MRS at 4.7 T. The brain [5-¹³C]glutamine peak consisted of the doublet from [5-¹³C,¹⁵N]glutamine and the center [5-¹³C,¹⁴N]glutamine peak, resulting in an apparent triplet with a separation of 8 Hz. The time course of formation of brain [5-¹³C,¹⁵N]glutamine was monitored in vivo with a time resolution of 20–35 min. This [5-¹³C,¹⁵N]glutamine was formed by glial uptake of released neurotransmitter [5-¹³C]glutamate and its reaction with ¹⁵NH₃ catalyzed by the glia-specific glutamine synthetase. The neurotransmitter glutamate C5 was selectively¹³C-enriched by intravenous [2,5-¹³C]glucose infusion to ¹³C-label whole-brain glutamate C5, followed by [¹²C]glucose infusion to chase ¹³C from the small and rapidly turning-over glial glutamate pool, leaving ¹³C mainly in the neurotransmitter [5-¹³C]glutamate pool, which is sequestered in vesicles until release. Hence, the observed [5-¹³C,¹⁵N]glutamine arises from a coupling between ¹³C of neuronal origin and ¹⁵N of glial origin. Measurement of the rate of brain [5-¹³C,¹⁵N]glutamine formation provides a novel noninvasive method of studying the kinetics of neurotransmitter uptake into glia in vivo, a process that is crucial for protecting the brain from glutamate excitotoxicity.     

Characteristic functional equations of polynomials and the morera-carleman theorem

Several characteristic functional equations satisfied by classes of polynomials of bounded degree are examined in connection with certain generalizations of the Morera-Carleman Theorem. Certain functional equations which have nonanalytic polynomial solutions are also considered.     

Linear algorithms for testing the sign stability of a matrix and for findingZ-maximum matchings in acyclic graphs

Summary Ann×n real matrixA=(a _ij ) isstable if each eigenvalue has negative real part, andsign stable (orqualitatively stable) if each matrix B with the same sign-pattern asA is stable, regardless of the magnitudes ofB's entries. Sign stability is of special interest whenA is associated with certain models from ecology or economics in which the actual magnitudes of thea _ij may be very difficult to determine. Using a characterization due to Quirk and Ruppert, and to Jeffries, an efficient algorithm is developed for testing the sign stability ofA. Its time-and-space-complexity are both 0(n ²), and whenA is properly presented that is reduced to 0(max{n, number of nonzero entries ofA}). Part of the algorithm involves maximum matchings, and that subject is treated for its own sake in two final sections.