Building Graphs Whose Independence Polynomials Have Only Real Roots

A stable set in a graph G is a set of pairwise non-adjacent vertices, and the stability number α(G) is the maximum size of a stable set in G. The independence polynomial of G is

$I(G; x) = s_{0}+s_{1}x+s_{2}x^{2}+\cdots+s_{\alpha}x^{\alpha},\alpha=\alpha(G),$

where s _k equals the number of stable sets of cardinality k in G (Gutman and Harary [11]).

Unlike the matching polynomial, the independence polynomial of a graph can have non-real roots. It is known that the polynomial I(G; x) has only real roots whenever (a) α(G) = 2 (Brown et al. [4]), (b) G is claw-free (Chudnowsky and Symour [6]). Brown et al. [3] proved that given a well-covered graph G, one can define a well-covered graph H such that G is a subgraph of H, α(G) = α(H), and I(H; x) has all its roots simple and real.In this paper, we show that starting from a graph G whose I(G; x) has only real roots, one can build an infinite family of graphs, some being well-covered, whose independence polynomials have only real roots (and, sometimes, are also palindromic).     

Economic inefficiency measurement of input spending when decision-making units face different input prices

In a recent paper, Kaoru Tone (J Opl Res Soc (2002) 2: 429–444) showed that when the Farrell measure of cost efficiency is estimated for two firms that have different input prices, a firm with higher costs can be deemed more efficient than a firm with lower costs. As an alternative approach, Tone proposed a radial cost efficiency measure that is estimated using levels of spending on each input, rather than input quantities. Thus, firms with higher costs are less efficient than firms with lower costs. In this paper, we extend Tone's approach by allowing for non-radial changes in spending. Our approach builds on earlier work by Luenberger (J Math Econ (1992) 21: 461–481) and Chambers et al (J Econ Theo (1996) 70: 407–419) who use directional distance functions to measure inefficiency. We provide an example and illustration of our approach using Japanese bank data.     

A new characterization for some extensions of PSL(2, <Emphasis Type="Italic">q)</Emphasis> for some <Emphasis Type="Italic">q</Emphasis> by some character degrees

In [22] (Tong-Viet H P, Simple classical groups of Lie type are determined by their character degrees, J. Algebra, 357 (2012) 61–68), the following question arose: Which groups can be uniquely determined by the structure of their complex group algebras? The authors in [12] (Khosravi B et al., Some extensions of PSL(2,p²) are uniquely determined by their complex group algebras, Comm. Algebra, 43(8) (2015) 3330–3341) proved that each extension of PSL(2,p²) of order 2|PSL(2,p²)| is uniquely determined by its complex group algebra. In this paper we continue this work. Let p be an odd prime number and q = p or q = p³. Let M be a finite group such that |M| = h|PSL(2,q), where h is a divisor of |Out(PSL(2,q))|. Also suppose that M has an irreducible character of degree q and 2p does not divide the degree of any irreducible character of M. As the main result of this paper we prove that M has a unique nonabelian composition factor which is isomorphic to PSL(2,q). As a consequence of our result we prove that M is uniquely determined by its order and some information on its character degrees which implies that M is uniquely determined by the structure of its complex group algebra.     

Generalizations of some zero sum theorems

Given an abelian group G of order n, and a finite non-empty subset A of integers, the Davenport constant of G with weight A, denoted by D _A (G), is defined to be the least positive integer t such that, for every sequence (x ₁,..., x _t ) with x _i ?∈?G, there exists a non-empty subsequence \((x_{j_1},\ldots, x_{j_l})\) and a _i ?∈?A such that \(\sum_{i=1}^{l}a_ix_{j_i} = 0\). Similarly, for an abelian group G of order n, E _A (G) is defined to be the least positive integer t such that every sequence over G of length t contains a subsequence \((x_{j_1} ,\ldots, x_{j_n})\) such that \(\sum_{i=1}^{n}a_ix_{j_i} = 0\), for some a _i ?∈?A. When G is of order n, one considers A to be a non-empty subset of {1,..., n???1 }. If G is the cyclic group \({\Bbb Z}/n{\Bbb Z}\), we denote E _A (G) and D _A (G) by E _A (n) and D _A (n) respectively.In this note, we extend some results of Adhikari et al (Integers 8 (2008) Article A52) and determine bounds for \(D_{R_n}(n)\) and \(E_{R_n}(n)\), where \(R_n = \{x^2 : x \in (\mathbb{Z}/n\mathbb{ Z})^*\}\). We follow some lines of argument from Adhikari et al (Integers 8 (2008) Article A52) and use a recent result of Yuan and Zeng (European J. Combinatorics 31 (2010) 677–680), a theorem due to Chowla (Proc. Indian Acad. Sci. (Math. Sci.) 2 (1935) 242–243) and Kneser’s theorem (Math. Z. 58 (1953) 459–484; 66 (1956) 88–110; 61 (1955) 429–434).     

An Extension of a Simply Inequality Between von Neumann–Jordan and James Constants in Banach Spaces

For a non-trivial Banach space X, let J(X), CNJ(X), C_(NJ)~(p)(X) respectively stand for the James constant, the von Neumann–Jordan constant and the generalized von Neumann–Jordan constant recently inroduced by Cui et al. In this paper, we discuss the relation between the James and the generalized von Neumann–Jordan constants, and establish an inequality between them: C_(NJ)~(p)(X) ≤J(X) with p ≥ 2, which covers the well-known inequality CNJ(X) ≤ J(X). We also introduce a new constant, from which we establish another inequality that extends a result of Alonso et al.     

Tabu search embedded simulated annealing for the shortest route cut and fill problem

The shortest route cut and fill problem proposed by Henderson et al ¹ is studied in this paper where we extend the model to include multiple vehicles and a makespan objective. A new tabu search embedded simulated annealing algorithm for both models is developed. Computational experiments show that the new approach is robust and achieves better solutions when compared with those found using Henderson et al's algorithm for larger test cases within significantly shorter times.     

Tauberian and Abelian theorems for rapidly decaying distributions and their applications to stable laws

We establish some assertions of Tauberian and Abelian types which enable us to find connections between the asymptotic properties of the Laplace transform at infinity and the asymptotics of the corresponding densities of rapidly decaying distributions (at infinity or in some neighborhood of zero). As applications of our Tauberian type theorems we present asymptotics for the density f ^(α,ρ)(x) of “extreme” stable laws with parameters (α, ρ) for ρ = ±1 and x lying in the domain of rapid decay of f ^(α,ρ)(x). This asymptotics had been found in [1–5] by a more complicated method.     

Degree sum of a pair of independent edges and <Emphasis Type="Italic">Z</Emphasis><Subscript>3</Subscript>-connectivity

Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uv ∈ E(G), define d(e) = d(u) + d(v). Let F denote the set of all simple 2-edge-connected graphs on n ≥ 4 vertices such that G ∈ F if and only if d(e) + d(e’) ≥ 2n for every pair of independent edges e, e’ of G. We prove in this paper that for each G ∈ F, G is not Z ₃-connected if and only if G is one of K _2,n?2, K _3,n?3, K _2,n?2 ⁺ , K _3,n?3 ⁺ or one of the 16 specified graphs, which generalizes the results of X. Zhang et al. [Discrete Math., 2010, 310: 3390–3397] and G. Fan and X. Zhou [Discrete Math., 2008, 308: 6233–6240].     

Aggregation of ranked votes considering different relative gaps between rank positions

This paper considers ranked voting systems to determine the rank order of candidates who compete for a limited number of positions. We show that the preferential voting problems based on the data envelopment analysis (DEA) (Wang et al, 2007) can be solved using the extreme points of constraints on rank position importance incorporated in the formulation. This is basically due to the fact that the so-called inverse positive property of the constraints makes it possible to easily find their extreme points. Further, we emphasize that this finding is not restricted to Wang et al’s two linear models, but is also applicable to other DEA-based preferential voting problems, which include the constraints accounting for different relative gaps between rank positions.     

Did People in the Middle Ages <Emphasis Type="Italic">Know</Emphasis> that the Earth Was Flat?

The goal of this paper is to explore the presuppositionality of factive verbs, with special emphasis on the verbs know and regret. The hypothesis put forward here is that the factivity related to know and the factivity related to regret are two different phenomena, as the former is a semantic implication (an entailment) that is licensed by the conventional meaning of know, while the latter is a purely pragmatic phenomenon that arises conversationally. More specifically, it is argued that know is factive in the sense that it both entails and (pragmatically) presupposes p, while regret is factive in the sense that it only (pragmatically) presupposes p. In a recent article, Hazlett (Philosophy and Phenomenological Research, 80(3), 497–522, 2010) shows with authentic examples how know is used non-factively in ordinary language, and he observes in these examples, as he says, “a threat to Factivity.” I argue that non-factive uses of factive verbs, such as know and regret, far from being a threat to factivity, show that, on the one hand, know is ambiguous between a factive and a non-factive sense; on the other hand, in the case of regret, the presupposition of factivity has to be intended as a merely pragmatic implication which can be suspended by the speaker herself.     

Approximation of almost Sahoo–Riedel’s points by Sahoo–Riedel’s points

In this paper, we present an extention of Hyers–Ulam stability of Sahoo–Riedel’s points for real-valued differentiable functions on [a, b] and then we obtain stability results of Flett’s points for functions in the class of continuously differentiable functions on [a, b] with f′(a) = f′(b).     

Some functional inequalities on non-reversible Finsler manifolds

We continue our study of geometric analysis on (possibly non-reversible) Finsler manifolds, based on the Bochner inequality established by Ohta and Sturm. Following the approach of the \(\Gamma \)-calculus of Bakry et al (2014), we show the dimensional versions of the Poincaré–Lichnerowicz inequality, the logarithmic Sobolev inequality, and the Sobolev inequality. In the reversible case, these inequalities were obtained by Cavalletti and Mondino (2015) in the framework of curvature-dimension condition by means of the localization method. We show that the same (sharp) estimates hold also for non-reversible metrics.     

A General Approach to Isolating Roots of a Bitstream Polynomial

We describe a new approach to isolate the roots (either real or complex) of a square-free polynomial F with real coefficients. It is assumed that each coefficient of F can be approximated to any specified error bound and refer to such coefficients as bitstream coefficients. The presented method is exact, complete and deterministic. Compared to previous approaches (Eigenwillig in Real root isolation for exact and approximate polynomials using Descartes’ rule of signs, PhD thesis, Universität des Saarlandes, 2008; Eigenwillig et al. in CASC, LNCS, 2005; Mehlhorn and Sagraloff in J. Symb. Comput. 46(1):70–90, 2011) we improve in two aspects. Firstly, our approach can be combined with any existing subdivision method for isolating the roots of a polynomial with rational coefficients. Secondly, the approximation demand on the coefficients and the bit complexity of our approach is considerably smaller. In particular, we can replace the worst-case quantity σ(F) by the average-case quantity \({\prod_{i=1}^n\sqrt[n] {\sigma_i}}\) , where σ _i denotes the minimal distance of the i -th root ξ _i of F to any other root of F, σ(F) := min _i σ _i , and n = deg F. For polynomials with integer coefficients, our method matches the best bounds known for existing practical algorithms that perform exact operations on the input coefficients.     

Two-Sided Estimates of Fourier Sums Lebesgue Functions with Respect to Polynomials Orthogonal on Nonuniform Grids

Let Ω = {t₀, t₁, …, t_N} and Ω_N = {x₀, x₁, …, x_N–1}, where x_j = (t_j + t_{j + 1})/2, j = 0, 1, …, N–1 be arbitrary systems of distinct points of the segment [–1, 1]. For each function f(x) continuous on the segment [–1, 1], we construct discrete Fourier sums S_{n, N}( f, x) with respect to the system of polynomials {p?_k,N(x)} _k=0 ^N–1 , forming an orthonormal system on nonuniform point systems Ω_N consisting of finite number N of points from the segment [–1, 1] with weight Δt_j = t_{j + 1}–t_j. We find the growth order for the Lebesgue function L_n,N (x) of the considered partial discrete Fourier sums S_n,N ( f, x) as n = O(δ _N ^?2/7 ), δ_N = max_{0≤ j≤N?1} Δt_j More exactly, we have a two-sided pointwise estimate for the Lebesgue function L_{n, N}(x), depending on n and the position of the point x from [–1, 1].     

The independent neighborhoods process

A triangle T^(r) in an r-uniform hypergraph is a set of r+1 edges such that r of them share a common (r-1)-set of vertices and the last edge contains the remaining vertex from each of the first r edges. Our main result is that the random greedy triangle-free process on n points terminates in an r-uniform hypergraph with independence number O((n log n)^1/r). As a consequence, using recent results on independent sets in hypergraphs, the Ramsey number r(T^(r),K_s^(r)) has order of magnitude s^r/ log s. This answers questions posed in [4, 10] and generalizes the celebrated results of Ajtai–Komlós–Szemerédi [1] and Kim [9] to hypergraphs.     

Estimates of sums of integrals of the Legendre Polynomial

Estimates of sums \({R_{nk}}\left( x \right) = \sum\limits_{m = n}^\infty {{P_{mk}}\left( x \right)} \) are established. Here, P_n0(x)= P_n(x), \({R_{nk}}\left( x \right) = \int\limits_.^x {{P_{n,k - 1}}\left( y \right)dy} \), P_n is the Legendre polynomial with standard normalization P_n(1) = 1. With k = 1 in the main interval [–1, 1] the sum decreases with increasing n as n^–1, and in the half-open interval [–1, 1), as n^–3/2. With k > 1 the point x = 1 does not need to be excluded. The sum decreases as n^-k–1/2. Moreover, a small increase in the multiplicative constant permits to obtain the estimate \(|{R_{nk}}\left( {\cos \theta } \right)| < \frac{{C{{\sin }^{k - 3/2}}\theta }}{{{n^{k + 1/2}}}}\), where C depends weakly on k (but not on n, θ). In passing, a Mehler–Dirichlet-type integral for R_nk(cos θ) is deduced.     

Are there <Emphasis Type="Italic">p</Emphasis>-adic knot invariants?

We suggest using the Hall–Littlewood version of the Rosso–Jones formula to define the germs of p-adic HOMFLY-PT polynomials for torus knots [m, n] as coefficients of superpolynomials in a q-expansion. In this form, they have at least the [m, n] ? [n, m] topological invariance. This opens a new possibility to interpret superpolynomials as p-adic deformations of HOMFLY polynomials and poses a question of generalizing to other knot families, which is a substantial problem for several branches of modern theory.     

Arc-Transitive Pentavalent Graphs of Square-Free Order

Hua et al. (Discrete Math 311, 2259–2267, 2011) and Yang et al. (Discrete Math. 339, 522–532, 2016) classify arc-transitive pentavalent graphs of order 2pq and of order 2pqr (with p, q, r distinct odd primes), respectively. In this paper, we extend their results by giving a classification of arc-transitive pentavalent graphs of any square-free order.     

Strict <Emphasis Type="Italic">p</Emphasis>-negative type of a metric space

Doust and Weston (J Funct Anal 254:2336–2364, 2008) have introduced a new method called enhanced negative type for calculating a non-trivial lower bound \({\wp_{T}}\) on the supremal strict p-negative type of any given finite metric tree (T, d). In the context of finite metric trees any such lower bound \({\wp_{T} >1 }\) is deemed to be non-trivial. In this paper we refine the technique of enhanced negative type and show how it may be applied more generally to any finite metric space (X, d) that is known to have strict p-negative type for some p ≥ 0. This allows us to significantly improve the lower bounds on the supremal strict p-negative type of finite metric trees that were given in Doust and Weston (J Funct Anal 254:2336–2364, 2008, Corollary 5.5) and, moreover, leads in to one of our main results: the supremal p-negative type of a finite metric space cannot be strict. By way of application we are then able to exhibit large classes of finite metric spaces (such as finite isometric subspaces of Hadamard manifolds) that must have strict p-negative type for some p > 1. We also show that if a metric space (finite or otherwise) has p-negative type for some p > 0, then it must have strict q-negative type for all \({q \in [0, p)}\) . This generalizes Schoenberg (Ann Math 38:787–793, 1937, Theorem 2) and leads to a complete classification of the intervals on which a metric space may have strict p-negative type.     

A Neighborhood Union Condition for Fractional ID-[<Emphasis Type="Italic">a</Emphasis>, <Emphasis Type="Italic">b</Emphasis>]-factor-critical Graphs

Let a, b, r be nonnegative integers with \(1\leq{a}\leq{b}\) and \(r\geq2\). Let G be a graph of order n with \(n >\frac{(a+2b)(r(a+b)-2)}{b}\). In this paper, we prove that G is fractional ID-[a, b]-factor-critical if \(\delta(G)\geq\frac{bn}{a+2b}+a(r-1)\) and \(\mid N_{G}(x_{1}) \cup N_{G}(x_{2}) \cup \cdotp \cdotp \cdotp \cup N_{G}(x_{r})\mid\geq\frac{(a+b)n}{a+2b}\) for any independent subset {x₁, x₂, · · ·, x_r} in G. It is a generalization of Zhou et al.’s previous result [Discussiones Mathematicae Graph Theory, 36: 409–418 (2016)] in which r = 2 is discussed. Furthermore, we show that this result is best possible in some sense.