Perfectness and imperfectness of unit disk graphs on triangular lattice points

Given a finite set of 2-dimensional points P⊆R² and a positive real d, a unit disk graph, denoted by (P,d), is an undirected graph with vertex set P such that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to d. Given a pair of non-negative integers m and n, P(m,n) denotes a subset of 2-dimensional triangular lattice points defined by where . Let T_m,n(d) be a unit disk graph defined on a vertex set P(m,n) and a positive real d. Let be the kth power of T_m,n(1).In this paper, we show necessary and sufficient conditions that [ is perfect] and/or [ is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring (T_m,n(d),w) and .     

Preservers of spectral radius, numerical radius, or spectral norm of the sum on nonnegative matrices

Let be the set of entrywise nonnegative n×n matrices. Denote by r(A) the spectral radius (Perron root) of . Characterization is obtained for maps such that r(f(A)+f(B))=r(A+B) for all . In particular, it is shown that such a map has the form

     

Carleson measure problems for parabolic Bergman spaces and homogeneous Sobolev spaces

Let be the space of solutions to the parabolic equation having finite norm. We characterize nonnegative Radon measures μ on having the property , 1≤p≤q<∞, whenever . Meanwhile, denoting by v(t,x) the solution of the above equation with Cauchy data v₀(x), we characterize nonnegative Radon measures μ on satisfying , β∈(0,n), p∈[1,n/β], q∈(0,∞). Moreover, we obtain the decay of v(t,x), an isocapacitary inequality and a trace inequality.     

Covering line graphs with equivalence relations

An equivalence graph is a disjoint union of cliques, and the equivalence number of a graph G is the minimum number of equivalence subgraphs needed to cover the edges of G. We consider the equivalence number of a line graph, giving improved upper and lower bounds: . This disproves a recent conjecture that is at most three for triangle-free G; indeed it can be arbitrarily large.To bound we bound the closely related invariant σ(G), which is the minimum number of orientations of G such that for any two edges e,f incident to some vertex v, both e and f are oriented out of v in some orientation. When G is triangle-free, . We prove that even when G is triangle-free, it is NP-complete to decide whether or not σ(G)≤3.     

The ω-limit set of a graph map

Let G be a graph and be continuous. Denote by P(f), , ω(f) and Ω(f) the set of periodic points, the closure of the set of periodic points, ω-limit set and non-wandering set of f, respectively. In this paper we show that: (1) v∈ω(f) if and only if v∈P(f) or there exists an open arc L=(v,w) contained in some edge of G such that every open arc U=(v,c)⊂L contains at least 2 points of some trajectory; (2) v∈ω(f) if and only if every open neighborhood of v contains at least r+1 points of some trajectory, where r is the valence of v; (3) ; (4) if , then x has an infinite orbit.     

Fixed points of dual quantum operations

Let ?A be a normal completely positive map on B(H) with Kraus operators . Denote M the subset of normal completely positive maps by . In this note, the relations between the fixed points of ?A and are investigated. We obtain that , where K(H) is the set of all compact operators on H and is the dual of ?A∈M. In addition, we show that the map is a bijection on M.     

A non-linear structure preserving matrix method for the low rank approximation of the Sylvester resultant matrix

A non-linear structure preserving matrix method for the computation of a structured low rank approximation of the Sylvester resultant matrix S(f,g) of two inexact polynomials f=f(y) and g=g(y) is considered in this paper. It is shown that considerably improved results are obtained when f(y) and g(y) are processed prior to the computation of , and that these preprocessing operations introduce two parameters. These parameters can either be held constant during the computation of , which leads to a linear structure preserving matrix method, or they can be incremented during the computation of , which leads to a non-linear structure preserving matrix method. It is shown that the non-linear method yields a better structured low rank approximation of S(f,g) and that the assignment of f(y) and g(y) is important because may be a good structured low rank approximation of S(f,g), but may be a poor structured low rank approximation of S(g,f) because its numerical rank is not defined. Examples that illustrate the differences between the linear and non-linear structure preserving matrix methods, and the importance of the assignment of f(y) and g(y), are shown.     

Compactifications of rational maps, and the implicit equations of their images

In this paper, we give different compactifications for the domain and the codomain of an affine rational map f which parameterizes a hypersurface. We show that the closure of the image of this map (with possibly some other extra hypersurfaces) can be represented by a matrix of linear syzygies. We compactify into an (n−1)-dimensional projective arithmetically Cohen-Macaulay subscheme of some . One particular interesting compactification of is the toric variety associated to the Newton polytope of the polynomials defining f. We consider two different compactifications for the codomain of f: and . In both cases we give sufficient conditions, in terms of the nature of the base locus of the map, for getting a matrix representation of its closed image, without involving extra hypersurfaces. This constitutes a direct generalization of the corresponding results established by Laurent Busé and Jean-Pierre Jouanolou (2003) [12], Laurent Busé et al. (2009) [9], Laurent Busé and Marc Dohm (2007) [11], Nicolás Botbol et al. (2009) [5] and Nicolás Botbol (2009) [4].     

A remark on Ricceri's conjecture for a class of nonlinear eigenvalue problems

Consider the eigenvalue problem : −Δu=λf(x,u) in Ω, u=0 on ∂Ω, where Ω is a bounded smooth domain in RN. Denote by the set of all Carathéodory functions f:Ω×R→R such that for a.e. x∈Ω, f(x,⋅) is Lipschitzian with Lipschitz constant L, f(x,0)=0 and , and denote by (resp. ) the set of λ>0 such that has at least one nonzero classical (resp. weak) solution. Let λ₁ be the first eigenvalue for the Laplacian-Dirichlet problem. We prove that and . Our result is a positive answer to Ricceri's conjecture if use f(x,u) instead of f(u) in the conjecture.     

Smallest defining sets of directed triple systems

A directed triple system of order v, , is a pair (V,B) where V is a set of v elements and B is a collection of ordered triples of distinct elements of V with the property that every ordered pair of distinct elements of V occurs in exactly one triple as a subsequence. A set of triples in a D is a defining set for D if it occurs in no other on the same set of points. A defining set for D is a smallest defining set for D if D has no defining set of smaller cardinality. In this paper we are interested in the quantity

     

Sequences of integers with missing quotients

Let S be any set of natural numbers, and A be a given set of rational numbers. We say that S is an A-quotient-free set if x,y∈S implies y/x∉A. Let and , where the supremum is taken over all A-quotient-free sets S, and are the upper and lower asymptotic densities of S respectively. Let ρ(A)=sup_Sδ(S), where the supremum is taken over all A-quotient-free sets S such that δ(S) exists. In this paper we study the properties of , and ρ(A).     

Multifractal spectrum and generic properties of functions monotone in several variables

We study the singularity (multifractal) spectrum of continuous functions monotone in several variables. We find an upper bound valid for all functions of this type, and we prove that this upper bound is reached for generic functions monotone in several variables. Let be the set of points at which f has a pointwise exponent equal to h. For generic monotone functions f:d[0,1]→R, we have that for all h∈[0,1], and in addition, we obtain that the set is empty as soon as h>1. We also investigate the level set structure of such functions.     

Transitive resolvable idempotent quasigroups and large sets of resolvable Mendelsohn triple systems

We first define a transitive resolvable idempotent quasigroup (TRIQ), and show that a TRIQ of order v exists if and only if 3∣v and . Then we use TRIQ to present a tripling construction for large sets of resolvable Mendelsohn triple systems s, which improves an earlier version of tripling construction by Kang. As an application we obtain an for any integer n≥1, which provides an infinite family of even orders.     

Composition operators on Lizorkin-Triebel spaces

This paper is devoted to the study of the composition operator Tf(g):=f○g on Lizorkin-Triebel spaces . In case s>1+(1/p), 1<p<∞, and 1?q?∞ we will prove the following: the operator Tf takes to itself if and only if f(0)=0 and f belongs locally to .     

Quasi-convex density and determining subgroups of compact abelian groups

For an abelian topological group G, let denote the dual group of all continuous characters endowed with the compact open topology. Given a closed subset X of an infinite compact abelian group G such that w(X)<w(G), and an open neighborhood U of 0 in T, we show that . (Here, w(G) denotes the weight of G.) A subgroup D of G determines G if the map defined by r(χ)=χ?D for , is an isomorphism between and . We prove that

     

Normal families and shared values of meromorphic functions

Let be a positive integer, let F be a family of meromorphic functions in a domain D, all of whose zeros have multiplicity at least k+1, and let , be two holomorphic functions on D. If, for each f∈F, f=a(z)⇔f(k)=h(z), then F is normal in D.     

On Brown’s constant associated with irreducible polynomials over henselian valued fields

Let v be a henselian valuation of arbitrary rank of a field K and be the prolongation of v to the algebraic closure of K with value group . In 2008, Ron Brown gave a class P of monic irreducible polynomials over K such that to each g(x) belonging to P, there corresponds a smallest constant λ_g belonging to (referred to as Brown’s constant) with the property that whenever is more than λ_g with K(β) a tamely ramified extension of (K,v), then K(β) contains a root of g(x). In this paper, we determine explicitly this constant besides giving an important property of λ_g without assuming that K(β)/K is tamely ramified.     

Primitive elements in rings of continuous functions

Let be a surjective continuous map between compact Hausdorff spaces. The map π induces, by composition, an injective morphism C(Y)→C(X) between the corresponding rings of real-valued continuous functions, and this morphism allows us to consider C(Y) as a subring of C(X). This paper deals with algebraic properties of the ring extension C(Y)⊆C(X) in relation to topological properties of the map . We prove that if the extension C(Y)⊆C(X) has a primitive element, i.e., C(X)=C(Y)[f], then it is a finite extension and, consequently, the map π is locally injective. Moreover, for each primitive element f we consider the ideal and prove that, for a connected space Y, If is a principal ideal if and only if is a trivial covering.