Interlace polynomials: Enumeration, unimodality and connections to codes

The interlace polynomialq was introduced by Arratia, Bollobás, and Sorkin. It encodes many properties of the orbit of a graph under edge local complementation (ELC). The interlace polynomial Q, introduced by Aigner and van der Holst, similarly contains information about the orbit of a graph under local complementation (LC). We have previously classified LC and ELC orbits, and now give an enumeration of the corresponding interlace polynomials of all graphs of order up to 12. An enumeration of all circle graphs of order up to 12 is also given. We show that there exist graphs of all orders greater than 9 with interlace polynomials q whose coefficient sequences are non-unimodal, thereby disproving a conjecture by Arratia et al. We have verified that for graphs of order up to 12, all polynomials Q have unimodal coefficients. It has been shown that LC and ELC orbits of graphs correspond to equivalence classes of certain error-correcting codes and quantum states. We show that the properties of these codes and quantum states are related to properties of the associated interlace polynomials.     

Graph polynomials from principal pivoting

The recursive computation of the interlace polynomial introduced by Arratia, Bollobás and Sorkin is defined in terms of a new pivoting operation on undirected simple graphs. In this paper, we interpret the new pivoting operation on graphs in terms of standard pivoting (on matrices). Specifically, we show that, up to swapping vertex labels, Arratia et al.'s pivoting operation on a graph is equivalent to a principal pivot transform on the graph's adjacency matrix, provided that all computations are performed in the Galois field F₂. Principal pivoting on adjacency matrices over F₂ has a natural counterpart on isotropic systems. Thus, our view of the interlace polynomial is closely related to the one by Aigner and van der Holst.The observations that adjacency matrices of undirected simple graphs are skew-symmetric in F₂ and that principal pivoting preserves skew-symmetry in all fields suggest to extend Arratia et al.'s pivoting operation to fields other than F₂. Thus, the interlace polynomial extends to polynomials on gain graphs, namely bidirected edge-weighted graphs whereby reversed edges carry non-zero weights that differ only by their sign. Extending a proof by Aigner and van der Holst, we show that the extended interlace polynomial can be represented in a non-recursive form analogous to the non-recursive form of the original interlace polynomial, i.e., the Martin polynomial.For infinite fields it is shown that the extended interlace polynomial does not depend on the (non-zero) gains, as long as they obey a non-singularity condition. These gain graphs are all supported by a single undirected simple graph. Thus, a new graph polynomial is defined for undirected simple graphs. The recursive computation of the new polynomial can be done such that all ends of the recursion correspond to independent sets. Moreover, its degree equals the independence number. However, the new graph polynomial is different from the independence polynomial.     

Extending the Newton-Kantorovich hypothesis for solving equations

The famous Newton-Kantorovich hypothesis (Kantorovich and Akilov, 1982 [3], Argyros, 2007 [2], Argyros and Hilout, 2009 [7]) has been used for a long time as a sufficient condition for the convergence of Newton’s method to a solution of an equation in connection with the Lipschitz continuity of the Fréchet-derivative of the operator involved. Here, using Lipschitz and center-Lipschitz conditions, and our new idea of recurrent functions, we show that the Newton-Kantorovich hypothesis can be weakened, under the same information. Moreover, the error bounds are tighter than the corresponding ones given by the dominating Newton-Kantorovich theorem (Argyros, 1998 [1]; [2] and [7]; Ezquerro and Hernández, 2002 [11]; [3]; Proinov 2009, 2010 [16] and [17]).Numerical examples including a nonlinear integral equation of Chandrasekhar-type (Chandrasekhar, 1960 [9]), as well as a two boundary value problem with a Green’s kernel (Argyros, 2007 [2]) are also provided in this study.     

Kantorovich-type semilocal convergence analysis for inexact Newton methods

We provide a new semilocal convergence analysis for generating an inexact Newton method converging to a solution of a nonlinear equation in a Banach space setting. Our analysis is based on our idea of recurrent functions. Our results are compared favorably to earlier ones by others and us (Argyros (2007, 2009) [5] and [6], Argyros and Hilout (2009) [7], Guo (2007) [15], Shen and Li (2008) [18], Li and Shen (2008) [19], Shen and Li (2009) [20]). Numerical examples are provided to show that our results apply, but not earlier ones [15], [18], [19] and [20].     

Dependence of variables construed as an atomic formula

We define a logic D capable of expressing dependence of a variable on designated variables only. Thus D has similar goals to the Henkin quantifiers of [4] and the independence friendly logic of [6] that it much resembles. The logic D achieves these goals by realizing the desired dependence declarations of variables on the level of atomic formulas. By [3] and [17], ability to limit dependence relations between variables leads to existential second order expressive power. Our D avoids some difficulties arising in the original independence friendly logic from coupling the dependence declarations with existential quantifiers. As is the case with independence friendly logic, truth of D is definable inside D. We give such a definition for D in the spirit of [11] and [2] and [1].     

Inexact Newton-type methods

We introduce the new idea of recurrent functions to provide a semilocal convergence analysis for an inexact Newton-type method, using outer inverses. It turns out that our sufficient convergence conditions are weaker than in earlier studies in many interesting cases (Argyros, 2004 [5] and [6], Argyros, 2007 [7], Dennis, 1971 [14], Deuflhard and Heindl, 1979 [15], Gutiérrez, 1997 [16], Gutiérrez et al., 1995 [17], Häubler, 1986 [18], Huang, 1993 [19], Kantorovich and Akilov, 1982 [20], Nashed and Chen, 1993 [21], Potra, 1982 [22], Potra, 1985 [23]).     

On recent developments in the theory of abstract differential equations with fractional derivatives

This note is motivated from some recent papers treating the problem of the existence of a solution for abstract differential equations with fractional derivatives. We show that the existence results in [Agarwal et al. (2009) [1], Belmekki and Benchohra (2010) [2], Darwish et al. (2009) [3], Hu et al. (2009) [4], Mophou and N’Guérékata (2009) [6] and [7], Mophou (2010) [8] and [9], Muslim (2009) [10], Pandey et al. (2009) [11], Rashid and El-Qaderi (2009) [12] and Tai and Wang (2009) [13]] are incorrect since the considered variation of constant formulas is not appropriate. In this note, we also consider a different approach to treat a general class of abstract fractional differential equations.     

Majorizing functions and two-point Newton-type methods

The semi-local convergence of a Newton-type method used to solve nonlinear equations in a Banach space is studied. We also give, as two important applications, convergence analyses of two classes of two-point Newton-type methods including a method mentioned in [5] and the midpoint method studied in [1], [2] and [12]. Recently, interest has been shown in such methods [3] and [4].     

Coderivatives of normal cone mappings and Lipschitzian stability of parametric variational inequalities

In this paper, we provide a comprehensive study of coderivative formulas for normal cone mappings. This allows us to derive necessary and sufficient conditions for the Lipschitzian stability of parametric variational inequalities in reflexive Banach spaces. Our development not only gives an answer to the open questions raised in Yao and Yen (2009) [11], but also establishes generalizations and complements of the results given in Henrion et al. (2010) [4] and Yao and Yen (2009) [11] and [12].     

On the Secant method

We present a new semilocal convergence analysis for the Secant method in order to approximate a locally unique solution of a nonlinear equation in a Banach space setting. Our analysis is based on the weaker center-Lipschitz concept instead of the stronger Lipschitz condition which has been ubiquitously employed in other studies such as Amat et al. (2004)  [2], Bosarge and Falb (1969)  [9], Dennis (1971)  [10], Ezquerro et al. (2010)  [11], Hernández et al. (2005, 2000)   and , Kantorovich and Akilov (1982)  [14], Laasonen (1969)  [15], Ortega and Rheinboldt (1970)  [16], Parida and Gupta (2007)  [17], Potra (1982, 1984–1985, 1985)  ,  and , Proinov (2009, 2010)   and , Schmidt (1978) [23], Wolfe (1978)  [24] and Yamamoto (1987)  [25] for computing the inverses of the linear operators. We also provide lower and upper bounds on the limit point of the majorizing sequences for the Secant method. Under the same computational cost, our error analysis is tighter than that proposed in earlier studies. Numerical examples illustrating the theoretical results are also given in this study.     

A unifying theorem for Newton’s method on spaces with a convergence structure

We present a semilocal convergence theorem for Newton’s method (NM) on spaces with a convergence structure. Using our new idea of recurrent functions, we provide a tighter analysis, with weaker hypotheses than before and with the same computational cost as for Argyros (1996, 1997, 1997, 2007) [1], [2], [3] and [5], Meyer (1984, 1987, 1992) [13], [14] and [15]. Numerical examples are provided for solving equations in cases not covered before.     

Stability in cellular neural networks with a piecewise constant argument

In this paper, by using the concept of differential equations with piecewise constant arguments of generalized type [1], [2], [3] and [4], a model of cellular neural networks (CNNs) [5] and [6] is developed. The Lyapunov-Razumikhin technique is applied to find sufficient conditions for the uniform asymptotic stability of equilibria. Global exponential stability is investigated by means of Lyapunov functions. An example with numerical simulations is worked out to illustrate the results.     

Fixed point theorems for some generalized multivalued nonexpansive mappings

In this paper, we introduce a condition on multivalued mappings which is a multivalued version of condition (C_λ) defined by Garcia-Falset et al. (2011) [3]. It is shown here that some of the classical fixed point theorems for multivalued nonexpansive mappings can be extended to mappings satisfying this condition. Our results generalize the results in Lim (1974), Lami Dozo (1973), Kirk and Massa (1990), Garcia-Falset et al. (2011), Dhompongsa et al. (2009) and Abkar and Eslamian (2010) [4], [5], [6], [3], [7] and [8] and many others.     

Numerical solutions of stochastic differential delay equations under the generalized Khasminskii-type conditions

The classical existence-and-uniqueness theorem of the solution to a stochastic differential delay equation (SDDE) requires the local Lipschitz condition and the linear growth condition (see e.g. [11], [12] and [20]). The numerical solutions under these conditions have also been discussed intensively (see e.g. [4], [10], [13], [16], [17], [18], [21], [22] and [24]). Recently, Mao and Rassias [14] and [15] established the generalized Khasminskii-type existence-and-uniqueness theorems for SDDEs, where the linear growth condition is no longer imposed. These generalized Khasminskii-type theorems cover a wide class of highly nonlinear SDDEs but these nonlinear SDDEs do not have explicit solutions, whence numerical solutions are required in practice. However, there is so far little numerical theory on SDDEs under these generalized Khasminskii-type conditions. The key aim of this paper is to close this gap.     

Unbounded critical points for a class of lower semicontinuous functionals

For a general class of lower semicontinuous functionals, we prove existence and multiplicity of critical points, which turn out to be unbounded solutions to the associated Euler equation. We apply a nonsmooth critical point theory developed in [10], [12] and [13] and applied in [8], [9] and [20] to treat the case of continuous functionals.     

Notes on generalization of the Bernoulli type polynomials

Recently, Srivastava et al. introduced a new generalization of the Bernoulli, Euler and Genocchi polynomials (see [H.M. Srivastava, M. Garg, S. Choudhary, Russian J. Math. Phys. 17 (2010) 251-261] and [H.M. Srivastava, M. Garg, S. Choudhary, Taiwanese J. Math. 15 (2011) 283-305]). They established several interesting properties of these general polynomials, the generalized Hurwitz-Lerch zeta functions and also in series involving the familiar Gaussian hypergeometric function. By the same motivation of Srivastava’s et al. [11] and [12], we introduce and derive multiplication formula and some identities related to the generalized Bernoulli type polynomials of higher order associated with positive real parameters a, b and c. We also establish multiple alternating sums in terms of these polynomials. Moreover, by differentiating the generating function of these polynomials, we give a interpolation function of these polynomials.     

Approximation of signals of class Lip(α, p) by linear operators

Mittal, Rhoades [5], [6], [7] and [8] and Mittal et al. [9] and [10] have initiated a study of error estimates E_n(f) through trigonometric-Fourier approximation (tfa) for the situations in which the summability matrix T does not have monotone rows. In this paper we continue the work. Here we extend two theorems of Leindler [4], where he has weakened the conditions on {p_n} given by Chandra [2], to more general classes of triangular matrix methods. Our Theorem also partially generalizes Theorem 4 of Mittal et al. [11] by dropping the monotonicity on the elements of matrix rows, which in turn generalize the results of Quade [15].     

Common fixed point results in CAT(0) spaces

Let X be a complete CAT(0) space, T be a generalized multivalued nonexpansive mapping, and t be a single valued quasi-nonexpansive mapping. Under the assumption that T and t commute weakly, we shall prove the existence of a common fixed point for them. In this way, we extend and improve a number of recent results obtained by Shahzad (2009) [7] and [12], Shahzad and Markin (2008) [6], and Dhompongsa et al. (2005) [5].