A degree condition for the circumference of a graph

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x₁,…,x_n and edge set E that satisfies the property that, for any two integers j and k with j < k, x_jx_k ? E, d(x_i) ? j and d(x_k) ? K - 1, we have (1) d(x_i) + d(x_k ? m if j + k ? n and (2) if j + k < n, either m ? n or d(x_j) + d(x_k) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.     

Matrices associated with arithmetical functions

Let f be an arithmetical function and S={x ₁,x ₂,…,x_n } a set of distinct positive integers. Denote by [f(x_i ,x_j }] the n×n matrix having f evaluated at the greatest common divisor (x_i ,x_j ) of x_i , and x_j as its i j-entry. We will determine conditions on f that will guarantee the matrix [f(x_i ,x_j )] is positive definite and, in fact, has properties similar to the greatest common divisor (GCD) matrix

[(x_i ,x_j )] where f is the identity function. The set S is gcd-closed if (x_i ,x_j )∈S for 1≤ i j ≤ n. If S is gcd-closed, we calculate the determinant and (if it is invertible) the inverse of the matrix [f(x_i ,x_j )]. Among the examples of determinants of this kind are H. J. S. Smith's determinant det[(i,j)].     

The sum of squared logarithms inequality in arbitrary dimensions

We prove the sum of squared logarithms inequality (SSLI) which states that for nonnegative vectors x, y ∈ ℝⁿ whose elementary symmetric polynomials satisfy e_k(x) ≤ e_k(y) (for 1 ≤ k < n) and e_n(x) = e_n(y) , the inequality ∑_i(log x_i)² ≤ ∑_i(log y_i)² holds. Our proof of this inequality follows by a suitable extension to the complex plane. In particular, we show that the function f : M ⊆ ℂⁿ → ℝ with f(z) = ∑_i(log z_i)² has nonnegative partial derivatives with respect to the elementary symmetric polynomials of z. We conclude by providing applications and wider connections of the SSLI. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Divisibility of matrices associated with multiplicative functions

Let S={x₁,…,x_n} be a set of n distinct positive integers. For x,y∈S and y<x, we say the y is a greatest-type divisor of x in S if y∣x and it can be deduced that z=y from y∣z,z∣x,z<x and z∈S. For x∈S, let G_S(x) denote the set of all greatest-type divisors of x in S. For any arithmetic function f, let (f(x_i,x_j)) denote the n×n matrix having f evaluated at the greatest common divisor (x_i,x_j) of x_i and x_j as its i,j-entry and let (f[x_i,x_j]) denote the n×n matrix having f evaluated at the least common multiple [x_i,x_j] of x_i and x_j as its i,j-entry. In this paper, we assume that S is a gcd-closed set and . We show that if f is a multiplicative function such that (f∗μ)(d)∈Z whenever and f(a)|f(b) whenever a|b and a,b∈S and (f(x_i,x_j)) is nonsingular, then the matrix (f(x_i,x_j)) divides the matrix (f[x_i,x_j]) in the ring M_n(Z) of n×n matrices over the integers. As a consequence, we show that (f(x_i,x_j)) divides (f[x_i,x_j]) in the ring M_n(Z) if (f∗μ)(d)∈Z whenever and f is a completely multiplicative function such that (f(x_i,x_j)) is nonsingular. This confirms a conjecture of Hong raised in 2004.     

A combinatorial problem involving graphs and matrices

In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x₁,x₂,…,x_k?n^k there exist k distinct integers j₁,j₂,…,j_k so that x_i= a_ii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k).     

An extremal property of Hermite polynomials

Let H_n be the nth Hermite polynomial, i.e., the nth orthogonal on polynomial with respect to the weight w(x)=exp(−x²). We prove the following: If f is an arbitrary polynomial of degree at most n, such that |f||H_n| at the zeros of H_n+1, then for k=1,…,n we have f^(k)H_n^(k), where · is the norm. This result can be viewed as an inequality of the Duffin and Schaeffer type. As corollaries, we obtain a Markov-type inequality in the norm, and estimates for the expansion coefficients in the basis of Hermite polynomials.     

Finite free resolutions of length two and koszul generalized complex

Abstract

In 1956, Ehrenfeucht proved that a polynomial f ₁(x ₁) + · + f _n (x _n ) with complex coefficients in the variables x ₁, …, x _n is irreducible over the field of complex numbers provided the degrees of the polynomials f ₁(x ₁), …, f _n (x _n ) have greatest common divisor one. In 1964, Tverberg extended this result by showing that when n ≥ 3, then f ₁(x ₁) + · + f _n (x _n ) belonging to K[x ₁, …, x _n ] is irreducible over any field K of characteristic zero provided the degree of each f _i is positive. Clearly a polynomial F = f ₁(x ₁) + · + f _n (x _n ) is reducible over a field K of characteristic p ≠ 0 if F can be written as F = (g ₁(x ₁)) ^p  + (g ₂(x ₂)) ^p  + · + (g _n (x _n )) ^p  + c[g ₁(x ₁) + g ₂(x ₂) + · + g _n (x _n )] where c is in K and each g _i (x _i ) is in K[x _i ]. In 1966, Tverberg proved that the converse of the above simple fact holds in the particular case when n = 3 and K is an algebraically closed field of characteristic p > 0. In this article, we prove an extension of Tverberg's result by showing that this converse holds for any n ≥ 3.     

Majorization of polynomials on the plane

We prove that for every χ[−1, 1] and every real algebraic polynomial f of degree n such that |f(t): 1 on [−1, 1], the following inequality takes place on the complex plane |f(x+iy)||T_n(1+iy)|,−∞y∞ where T_n is the Tchebycheff polynomial. This implies easily Vladimir Markov inequality.     

On Hong’s conjecture for power LCM matrices

A set S={x ₁,...,x _n } of n distinct positive integers is said to be gcd-closed if (x _i , x _j ) ∈ S for all 1 ⩽ i, j ⩽ n. Shaofang Hong conjectured in 2002 that for a given positive integer t there is a positive integer k(t) depending only on t, such that if n ⩽ k(t), then the power LCM matrix ([x _i , x _j ] ^t ) defined on any gcd-closed set S={x ₁,...,x _n } is nonsingular, but for n ⩾ k(t) + 1, there exists a gcd-closed set S={x ₁,...,x _n } such that the power LCM matrix ([x _i , x _j ] ^t ) on S is singular. In 1996, Hong proved k(1) = 7 and noted k(t) ⩾ 7 for all t ⩾ 2. This paper develops Hong’s method and provides a new idea to calculate the determinant of the LCM matrix on a gcd-closed set and proves that k(t) ⩾ 8 for all t ⩾ 2. We further prove that k(t) ⩾ 9 iff a special Diophantine equation, which we call the LCM equation, has no t-th power solution and conjecture that k(t) = 8 for all t ⩾ 2, namely, the LCM equation has t-th power solution for all t ⩾ 2.     

On conjugacy of some systems of functions

Summary. We investigate the bounded solutions j:[0,1]? X \varphi:[0,1]\to X of the system of functional equations¶¶j(f_k(x))=F_k(j(x)),    k=0,?,n-1,x ? [0,1] \varphi(f_k(x))=F_k(\varphi(x)),\;\;k=0,\ldots,n-1,x\in[0,1] ,(*)¶where X is a complete metric space, f₀,?,f_n-1:[0,1]?[0,1] f_0,\ldots,f_{n-1}:[0,1]\to[0,1] and F₀,...,F_n-1:X? X F_0,...,F_{n-1}:X\to X are continuous functions fulfilling the boundary conditions f₀(0) = 0, f_n-1(1) = 1, f_k+1(0) = f_k(1), F₀(a) = a,F_n-1(b) = b,F_k+1(a) = F_k(b), k = 0,?,n-2 f_{0}(0) = 0, f_{n-1}(1) = 1, f_{k+1}(0) = f_{k}(1), F_{0}(a) = a,F_{n-1}(b) = b,F_{k+1}(a) = F_{k}(b),\,k = 0,\ldots,n-2 , for some a,b ? X a,b\in X . We give assumptions on the functions f_k and F_k which imply the existence, uniqueness and continuity of bounded solutions of the system (*). In the case X = \Bbb C X= \Bbb C we consider some particular systems (*) of which the solutions determine some peculiar curves generating some fractals. If X is a closed interval we give a collection of conditions which imply respectively the existence of homeomorphic solutions, singular solutions and a.e. nondifferentiable solutions of (*).     

Convergence of Lagrange Interpolation Polynomials for Piecewise Smooth Functions

The present paper first establishes a decomposition result for f(x)∈ C ^r C ^r+1. By using this decomposition we thus can obtain an estimate of ∣f(x) - L _n (f,x)∣ which reflects the influence of the position of the x's and ω(f ^(r+1),δ)_j, j = 0,1,...,s, on the error of approximation. This revised version was published online in June 2006 with corrections to the Cover Date.     

A note on certain functional determinants

Summary We consider the problem when a scalar function ofn variables can be represented in the form of a determinant det(f _i (x _j )), the so-called Casorati determinant off ₁,f ₂,,f _n . The result is applied to the solution of some functional equations with unknown functionsH of two variables that involve determinants det(H(x _i ,x _j )).     

On numerical improvement of Gauss–Legendre quadrature rules

Among all integration rules with n points, it is well-known that n-point Gauss–Legendre quadrature rule∫₋₁¹f(x) dx∑_i=1ⁿw_if(x_i)has the highest possible precision degree and is analytically exact for polynomials of degree at most 2n−1, where nodes x_i are zeros of Legendre polynomial P_n(x), and w_i's are corresponding weights.In this paper we are going to estimate numerical values of nodes x_i and weights w_i so that the absolute error of introduced quadrature rule is less than a preassigned tolerance ε₀, say ε₀=10⁻⁸, for monomial functionsf(x)=x^j, j=0,1,…,2n+1.(Two monomials more than precision degree of Gauss–Legendre quadrature rules.) We also consider some conditions under which the new rules act, numerically, more accurate than the corresponding Gauss–Legendre rules. Some examples are given to show the numerical superiority of presented rules.     

On the Greatest Common Divisor of u ? 1 and v ? 1 with u and v Near S{\cal S}-units

In [2], it was shown that if a and b are multiplicatively independent integers and ɛ > 0, then the inequality gcd (aⁿ − 1,bⁿ − 1) < exp(ɛn) holds for all but finitely many positive integers n. Here, we generalize the above result. In particular, we show that if f(x),f₁(x),g(x),g₁(x) are non-zero polynomials with integer coefficients, then for every ɛ > 0, the inequality gcd (f(n)aⁿ+g(n), f₁(n)bⁿ+g₁(n)) < exp(ne){\rm gcd}\, (f(n)a^n+g(n), f_1(n)b^n+g_1(n)) < \exp(n\varepsilon) holds for all but finitely many positive integers n.     

More on Poincaré’s and Perron’s Theorems for Difference Equations∗

Consider the scalar kth order linear difference equation: x(n + k) + pi(n)x(n + k - 1) + … + pk(n)x(n) = 0 where the limits qi=lim_n→∞Pi(n) (i=1,…,k) are finite. In this paper, we confirm the conjecture formulated recently by Elaydi. Namely, every nonzero solution x of (?) satisfies the same asymptotic relation as the fundamental solutions described earlier by Perron, ie., ?= lim sup_n→∞ |x(n)| is equal to the modulus of one of the roots of the characteristics equation χ ^k + q ₁χ ^k?1+…+qk=0. This result is a consequence of a more general theorem concerning the Poincaré difference system x(n+1)=[A+B(n]x(n), where A and B(n) (n=0,1,…) are square matrices such that ‖B(n)‖ →0 as n → ∞. As another corollary, we obtain a new limit relation for the solutions of (?).     

Stability of a simple Levi–Civitá functional equation on non-unital commutative semigroups

In this paper, we study the Hyers–Ulam stability of a simple Levi–Civitá functional equation f(x+y)=f(x)h(y)+f(y) and its pexiderization f(x+y)= g(x) h(y)+k(y) on non-unital commutative semigroups by investigating the functional inequalities |f(x+y)?f(x)h(y)?f(y)|≤?? and |f(x+y)?g(x)h(y)?k(y)|≤??, respectively. We also study the bounded solutions of the simple Levi–Civitá functional inequality.     

Coin flipping from a cosmic source: On error correction of truly random bits

We study a problem related to coin flipping, coding theory, and noise sensitivity. Consider a source of truly random bits x ∈ {0, 1}ⁿ, and k parties, who have noisy version of the source bits yⁱ ∈ {0, 1}ⁿ, when for all i and j, it holds that P [y = x_j] = 1 ? ?, independently for all i and j. That is, each party sees each bit correctly with probability 1 ? ?, and incorrectly (flipped) with probability ?, independently for all bits and all parties. The parties, who cannot communicate, wish to agree beforehand on balanced functions f_i: {0, 1}ⁿ → {0, 1} such that P [f₁(y¹) = … = f_k(y^k)] is maximized. In other words, each party wants to toss a fair coin so that the probability that all parties have the same coin is maximized. The function f_i may be thought of as an error correcting procedure for the source x. When k = 2,3, no error correction is possible, as the optimal protocol is given by f_i(yⁱ) = y. On the other hand, for large values of k, better protocols exist. We study general properties of the optimal protocols and the asymptotic behavior of the problem with respect to k, n, and ?. Our analysis uses tools from probability, discrete Fourier analysis, convexity, and discrete symmetrization. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

A greedy algorithm for the optimal basis problem

The following problem is considered. Givenm+1 points {x _i }₀ ^m inR ⁿ which generate anm-dimensional linear manifold, construct for this manifold a maximally linearly independent basis that consists of vectors of the formx _i −x _j . This problem is present in, e.g., stable variants of the secant and interpolation methods, where it is required to approximate the Jacobian matrixf′ of a nonlinear mappingf by using values off computed atm+1 points. In this case, it is also desirable to have a combination of finite differences with maximal linear independence. As a natural measure of linear independence, we consider the hadamard condition number which is minimized to find an optimal combination ofm pairs {x _i ,x _j }. We show that the problem is not NP-hard, but can be reduced to the minimum spanning tree problem, which is solved by the greedy algorithm inO(m ²) time. The complexity of this reduction is equivalent to onem×n matrix-matrix multiplication, and according to the Coppersmith-Winograd estimate, is belowO(n ^2.376) form=n. Applications of the algorithm to interpolation methods are discussed. Part of the work was done while the author was visiting DIMACS, an NSF Science and Technology Center funded under contract STC-91-19999; DIMACS is a cooperative project of Rutgers University, Princeton University, AT&T Bell Laboratories and Bellcore, NJ, USA.     

Stieltjes- and Geronimus-type polynomials

This work is an extension to the formal case of a previous work by Monegato [5].A Stieltjes-type polynomial is a polynomial of degree (n + 1), E_n+1, orthogonal with respect to the functional \s{;c̃_i = c(P_n(x)xⁱ), i = 0, 1, 2,…\s}, where c is a functional defined by the series f(t) = ∑^∞_i=0c_itⁱ. E_n+1 is of important use in the estimation of the error in Padé approximation. An iteration of the construction of E_n+1 is attempted. (Sections 1, 2, 3, 4).In the last section, we study the properties of the polynomial S_n associated with E_n+1 with respect to another functional c̄. S_n is called a Geronimus-type polynomial. It is shown that S_n verifies the system c(P_nS_nG_k) = 0 for k = 1,…,n, where the G_k's are orthogonal with respect to c̄.     

A new domination conception

Let f be an integer valued function defined on the vertex set V(G) of a simple graph G. We call a subset D_f of V(G) a f-dominating set of G if |N(x, G) ∩ D_f| ≥ f(x) for all x ∈ V(G) — D_f, where N(x, G) is the set of neighbors of x. D_f is a minimum f-dominating set if G has no f-dominating set D′_f with |D_f| < |D_f|. If j, k ∈ N₀ = {0,1,2,…} with j ≤ k, then we define the integer valued function f_j,k on V(G) by . By μ_j,k(G) we denote the cardinality of a minimum f_j,k-dominating set of G. A set D ? V(G) is j-dominating if every vertex, which is not in D, is adjacent to at least j vertices of D. The j-domination number γ_j(G) is the minimum order of a j-dominating set in G. In this paper we shall give estimations of the new domination number μ_j,k(G), and with the help of these estimations we prove some new and some known upper bounds for the j-domination number. © 1993 John Wiley & Sons, Inc.