Finding all essential terms of a characteristic maxpolynomial

Let us denote ab=max(a,b) and ab=a+b for and extend this pair of operations to matrices and vectors in the same way as in linear algebra. We present an O(n²(m+n log n)) algorithm for finding all essential terms of the max-algebraic characteristic polynomial of an n×n matrix over with m finite elements. In the cases when all terms are essential, this algorithm also solves the following problem: Given an n×n matrix A and k{1,…,n}, find a k×k principal submatrix of A whose assignment problem value is maximum.     

A Note on Strong Edge Coloring of Sparse Graphs

A strong edge coloring of a graph is a proper edge coloring where the edges at distance at most 2 receive distinct colors. The strong chromatic index χ'_s(G) of a graph G is the minimum number of colors used in a strong edge coloring of G. In an ordering Q of the vertices of G, the back degree of a vertex x of G in Q is the number of vertices adjacent to x, each of which has smaller index than x in Q. Let G be a graph of maximum degree Δ and maximum average degree at most 2 k. Yang and Zhu [J. Graph Theory, 83, 334–339(2016)] presented an algorithm that produces an ordering of the edges of G in which each edge has back degree at most 4 kΔ-2 k in the square of the line graph of G, implying that χ'_s(G) ≤ 4 kΔ-2 k + 1. In this note, we improve the algorithm of Yang and Zhu by introducing a new procedure dealing with local structures. Our algorithm generates an ordering of the edges of G in which each edge has back degree at most(4 k-1)Δ-2 k in the square of the line graph of G, implying that χ'_s(G) ≤(4 k-1)Δ-2 k + 1.     

Compound connection matrices

Suppose T is an incidence, basis circuit or basis cut set matrix of a connected graph and T^(k) is the k compound of T. It is proven that any second order minor of T^(k) is equal +1, −1, or 0. For the case of an incidence matrix this result is applied to tree counting and some structural properties of T^(k) are given.     

On strong consistency of the fuzzy generalized nearest neighbor rule

The k nearest neighbor rule (k-NNR) is a well-known nonparametric decision rule in pattern classification. Fuzzy set theory has been widely used to represent the uncertainty of class membership. Several researchers extended conventional k-NNR to fuzzy k-NNR, such as Bezdek et al. [Fuzzy Sets and Systems 18 (1986) 237–256], Keller et al. [IEEE Trans. Syst. Man, and Cybern. 15(4) (1985) 580–585], Béreau and Dubuisson [Fuzzy Sets and Systems 44 (1991) 17–32]. In this paper, we describe a fuzzy generalized k-NN algorithm. This algorithm is a unified approach to a variety of fuzzy k-NNR's. Then we create the strong consistency of posterior risk of the fuzzy generalized NNR.     

k-Lucas numbers and associated bipartite graphs

For a positive integer k2, the k-Fibonacci sequence {g_n^(k)} is defined as: g₁^(k)==g_k−2^(k)=0, g_k−1^(k)=g_k^(k)=1 and for n>k2, g_n^(k)=g_n−1^(k)+g_n−2^(k)++g_n−k^(k). Moreover, the k-Lucas sequence {l_n^(k)} is defined as l_n^(k)=g_n−1^(k)+g_n+k−1^(k) for n1. In this paper, we consider the relationship between g_n^(k) and l_n^(k) and 1-factors of a bipartite graph.     

On the pivot structure for the weighing matrix W(12,11)

In the present article we concentrate our study on the growth problem for the weighing matrix W(12,11) and show that the unique W(12,11) has three pivot structures. An improved algorithm for extending a k?×?k (0,+,-) matrix to a W(n,n-1), if possible, has been developed to simplify the proof. For the implementation of the algorithm special emphasis is given to the notions of data structures and parallel processing.     

路的字典积的邻和可区别边染色

图G的正常[k]-边染色σ是指颜色集合为[k]={1,2,…,k}的G的一个正常边染色.用w_σ（x）表示顶点x关联边的颜色之和,即w_σ（x）=∑_e∋x σ（e）,并称w_σ（x）关于σ的权.图G的k-邻和可区别边染色是指相邻顶点具有不同权的正常[k]-边染色,最小的k值称为G的邻和可区别边色数,记为χ'_∑（G）.现得到了路P_n与简单连通图H的字典积P_n[H]的邻和可区别边色数的精确值,其中H分别为正则第一类图、路、完全图的补图.     

Safety neighbournoods for the invariants of the matrix similarity

We give safety neighbourhoods for the necessary conditions in the change of the Jordan canonical form of a matrix under small perturbations. We also obtain the minimum distance from an n × n complex matrix which has less than k nonconstant invariant factors (2≤ k≤ n) to the set of matrices which have more or equal to k. When k= 2, we get in particular the distance from a nonderogatory matrix to the set of derogatory matrices.     

An Extension of an Inequality Involving Symmetric Products with an Application to Permanents

Let A be an nk × nk positive semi-definite symmetric matrix partitioned into blocks A^ij each of which is an n × n matrix. In [2] Mine states a conjecture of Marcus that per(A) ≥ per(G) where G is the k × k matrix [per(A^ij)]. In this paper we prove a weaker inequality namely that per(A) ≥ (k!)^-1per(G).     

Some Ore-type Results for Matching and Perfect Matching in <Emphasis Type="Italic">k</Emphasis>-uniform Hypergraphs

Let S₁ and S₂ be two (k-1)-subsets in a k-uniform hypergraph H. We call S₁ and S₂ strongly or middle or weakly independent if H does not contain an edge e ∈ E(H) such that S₁ ∩ e ≠∅ and S₂ ∩ e ≠∅ or e ⊆ S₁ ∪ S₂ or e ⊇ S₁ ∪ S₂, respectively. In this paper, we obtain the following results concerning these three independence. (1) For any n ≥ 2k²-k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent (k-1)-sets equal to 2n-4(k-1), contains no perfect matching; (2) Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd+(k-2)k. If the degree sum of any two middle independent (k-1)-subsets is larger than 2(d-1), then H contains a d-matching; (3) For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent (k-1)-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n.     

On the extreme eigenvalues of hermitian (block) toeplitz matrices

We are concerned with the behavior of the minimum (maximum) eigenvalue λ₀⁽ⁿ⁾ (λ_n⁽ⁿ⁾) of an (n + 1) × (n + 1) Hermitian Toeplitz matrix T_n(ƒ) where ƒ is an integrable real-valued function. Kac, Murdoch, and Szegö, Widom, Parter, and R. H. Chan obtained that λ₀⁽ⁿ⁾ — min ƒ = O(1/n^2k) in the case where ƒ C^2k, at least locally, and ƒ — inf ƒ has a zero of order 2k. We obtain the same result under the second hypothesis alone. Moreover we develop a new tool in order to estimate the extreme eigenvalues of the mentioned matrices, proving that the rate of convergence of λ₀⁽ⁿ⁾ to inf ƒ depends only on the order ρ (not necessarily even or integer or finite) of the zero of ƒ — inf ƒ. With the help of this tool, we derive an absolute lower bound for the minimal eigenvalues of Toeplitz matrices generated by nonnegative L¹ functions and also an upper bound for the associated Euclidean condition numbers. Finally, these results are extended to the case of Hermitian block Toeplitz matrices with Toeplitz blocks generated by a bivariate integrable function ƒ.     

General polynomial roots and their multiplicities in O(N)memory and O(N2)Time

For a given real or complex polynomial p of degree n we modify the Euclidean algorithm to find a general tridiagonal matrix representation T of the monic version of p and then use the tridiagonal DQR eigenvalue algorithm on T in order to find

all roots ofp with their multiplicities in O(n²) operations

and 0(n) storage. We include details of the implementation and comparisons with several, standard and recent, essentially 0(n³) polynomial root finders.     

Triangular range counting query in 2D and its application in finding k nearest neighbors of a line segment

We present an efficient algorithm for finding k nearest neighbors of a query line segment among a set of points distributed arbitrarily on a two dimensional plane. Along the way to finding this algorithm, we have obtained an improved triangular range searching technique in 2D. Given a set of n points, we preprocess them to create a data structure using O(n²) time and space, such that given a triangular query region Δ, the number of points inside Δ can be reported in O(logn) time. Finally, this triangular range counting technique is used for finding k nearest neighbors of a query straight line segment in O(log²n+k) time.     

Some recent results on drazin monotonicty of property n martices

If a square matrix has a nonnegarive power it is called a property-n matrix. In a recent paper [12] Werner derived some interesting necessary and sufficient conditions for a property n property-n matrix to be Drazin-montone. In particular, it was shown that a property -n matrix with ind(A) = k is Drazin-monotone if and only if A^2k+1 is weak-r-monotone. Our principal aim here is to show how this result can he strengthened considerably. To tackle this problem we also present several further results on the structure of Drazin-monotone (property-n) matrices.     

3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects

We present a new data structure for a set of n convex simply-shaped fat objects in the plane, and use it to obtain efficient and rather simple solutions to several problems including (i) vertical ray shooting—preprocess a set of n non-intersecting convex simply-shaped flat objects in 3-space, whose xy-projections are fat, for efficient vertical ray shooting queries, (ii) point enclosure—preprocess a set C of n convex simply-shaped fat objects in the plane, so that the k objects containing a query point p can be reported efficiently, (iii) bounded-size range searching— preprocess a set C of n convex fat polygons, so that the k objects intersecting a “not-too-large” query polygon can be reported efficiently, and (iv) bounded-size segment shooting—preprocess a set C as in (iii), so that the first object (if exists) hit by a “not-too-long” oriented query segment can be found efficiently. For the first three problems we construct data structures of size O(λ_s(n)log³n), where s is the maximum number of intersections between the boundaries of the (xy-projections) of any pair of objects, and λ_s(n) is the maximum length of (n, s) Davenport-Schinzel sequences. The data structure for the fourth problem is of size O(λ_s(n)log²n). The query time in the first problem is O(log⁴n), the query time in the second and third problems is O(log³n + klog²n), and the query time in the fourth problem is O(log³n).

We also present a simple algorithm for computing a depth order for a set as in (i), that is based on the solution to the vertical ray shooting problem. (A depth order for , if exists, is a linear order of , such that, if K₁, K₂ and K₁ lies vertically above K₂, then K₁ precedes K₂.) Unlike the algorithm of Agarwal et al. (1995) that might output a false order when a depth order does not exist, the new algorithm is able to determine whether such an order exists, and it is often more efficient in practical situations than the former algorithm.     

A special k-coloring for a connected k-chromatic graph

For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ(G) = k can be properly vertex colored by k colors so that for each pair of vertices x_o and x_p in any color class there exist vertices x₁, x₂, …, x_p-1 of the same class with dist(x_i, x_i+1) f(k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class.

We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1.     

Embedding complete trees into the hypercube

We consider embeddings of the complete t-ary trees of depth k (denotation T^k,t) as subgraphs into the hypercube of minimum dimension n. This n, denoted by dim(T^k,t), is known if max{k,t}2. First, we study the next open cases t=3 and k=3. We improve the known upper bound dim(T^k,3)2k+1 up to lim_k→∞dim(T^k,3)/k5/3 and show lim_t→∞dim(T^3,t)/t=227/120. As a co-result, we present an exact formula for the dimension of arbitrary trees of depth 2, as a function of their vertex degrees. These results and new techniques provide an improvement of the known upper bound for dim(T^k,t) for arbitrary k and t.     

Minimal least eigenvalue of connected graphs of order n and size m = n + k (5≤k≤8)

The least eigenvalue of a connected graph is the least eigenvalue of its adjacency matrix. We characterize the connected graphs of order n and size n + k (5≤k≤8 and n>k + 5) with the minimal least eigenvalue.     

Between local and global logarithmic averages

We obtain an approximation for the logarithmic averages of I{k^1/2a(k) S(k) k^1/2b(k)}, where a(k) → 0, b(k) → 0 (k → ∞) and S(k) is partial sum of independent, identically distributed random variables.     

Number of minimum vertex cuts in transitive graphs

Let G be a k-regular vertex transitive graph with connectivity κ(G)=k and let m_k(G) be the number of vertex cuts with k vertices. Define m(n,k)=min{m_k(G): GT_n,k}, where T_n,k denotes the set of all k-regular vertex transitive graphs on n vertices with κ(G)=k. In this paper, we determine the exact values of m(n,k).