Restricted Elasticity and Rings of Integer-Valued Polynomials Determined by Finite Subsets

Let D be an integral domain such that Int(D) ≠ K[X] where K is the quotient field of D. There is no known example of such a D so that Int(D) has finite elasticity. If E is a finite nonempty subset of D, then it is known that Int(E, D) = {f(X) ∈ K[X] | f(e) ∈ D for all e ∈ E} is not atomic. In this note, we restrict the notion of elasticity so that it is applicable to nonatomic domains. For each real number r ≥ 1, we produce a ring of integer-valued polynomials with restricted elasticity r. We further show that if D is a unique factorization domain and E is finite with |E| > 1, then the restricted elasticity of Int(E, D) is infinite. Part of this work was completed while the first author was on an Academic Leave granted by the Trinity University Faculty Development Committee.     

Restricted Elasticity and Rings of Integer-Valued Polynomials Determined by Finite Subsets

Let D be an integral domain such that Int(D) ≠ K[X] where K is the quotient field of D. There is no known example of such a D so that Int(D) has finite elasticity. If E is a finite nonempty subset of D, then it is known that Int(E, D) = {f(X) ∈ K[X] | f(e) ∈ D for all e ∈ E} is not atomic. In this note, we restrict the notion of elasticity so that it is applicable to nonatomic domains. For each real number r ≥ 1, we produce a ring of integer-valued polynomials with restricted elasticity r. We further show that if D is a unique factorization domain and E is finite with |E| > 1, then the restricted elasticity of Int(E, D) is infinite.     

Maximum degree and fractional matchings in uniform hypergraphs

Let ℋ be a family ofr-subsets of a finite setX. SetD(ℋ)= |{E:x∈E∈ℋ}|, (maximum degree). We say that ℋ is intersecting if for anyH,H′ ∈ ℋ we haveH ∩H′ ≠ 0. In this case, obviously,D(ℋ)≧|ℋ|/r. According to a well-known conjectureD(ℋ)≧|ℋ|/(r−1+1/r). We prove a slightly stronger result. Let ℋ be anr-uniform, intersecting hypergraph. Then either it is a projective plane of orderr−1, consequentlyD(ℋ)=|ℋ|/(r−1+1/r), orD(ℋ)≧|ℋ|/(r−1). This is a corollary to a more general theorem on not necessarily intersecting hypergraphs.     

Monotone perturbations of the laplacian inL 1(R N )

The semilinear perturbation of Poisson’s equation (E): −Δu+β(u)∋f, where β is a maximal monotone graph inR, has been investigated by Ph. Bénilan, H. Brézis and M. Crandall forf∈L ¹(R ^N ),N≧1, under the assumptions 0∈β(0) ifN≧3 and 0∈β(0) ∩ Int β(R) ifN=1,2. We discuss in this paper the solvability and well-posedness of (E) in terms of any maximal monotone graph β. In particular, if β takes only positive values andN≧3 we prove that no solution exists; ifN=2 we give necessary and sufficient conditions on β andf for (E) to be solvable in a natural sense.     

On a problem of Erdős concerning property B

A family ℱ of sets has propertyB if there exists a setS such thatS∩F≠0 andS⊄F for everyF∈ℱ. ℱ has propertyB(s) if there exists a setS such that 0<|F∩S|<s for everyF∈ℱ. Denote bym(n) (respectivelym(n, s)) the size of a smallest family ofn-element sets not having propertyB (respectivelyB(s)). P. Erdős has asked whetherm(n, s)≧m (s) for alln≧s. We show that, in general, this inequality does not hold.     

Note on non-D-rings

Abstract

Recall that an integral domain R is said to be a non-D-ring if there exists a non-constant polynomial f (X) in R[X] (called a uv-polynomial) such that f (a) is a unit of R for every a in R. In this note we generalize this notion to commutative rings (that are not necessarily integral domains) as follows: for a positive integer n, we say that R is an n-non-D-ring if there exists a polynomial f of degree n in R[X] such that f (a) is a unit of R for every a in R. We then investigate the properties of this notion in di?erent contexts of commutative rings.     

On a class of isometric subgraphs of a graph

In a graphG, which has a loop at every vertex, a connected subgraphH=(V(H),E(H)) is a retract if, for anya, b ∈V(H) and for any pathsP, Q inG, both joininga tob, and satisfying |Q|≧ ≧|P|, thenP ⫅V(H) wheneverQ ⫅V(H). As such subgraphs can be described by a closure operator we are led to the investigation of the corresponding complete lattice of “closed” subgraphs. For example, in this complete lattice every element is the infimum of an irredundant family of infimum irreducible elements. The work presented here was supported in part by N.S.E.R.C. Operating Grant No. A4077.     

Entire functions having a concordant value sequence

A classic theorem of Pólya shows that 2 ^z is, in a strong sense, the “smallest” transcendental entire function that is integer valued on ℕ. An analogous result of Gel’fond concerns entire functions that are integer valued on the setX _a={a ⁿ:n ∈ ℕ}, wherea ∈ ℕ,|a|≥ 2. LetX=ℕ orX=X _a andκ ∈ ℕ orκ=∞. This paper pursues analogous results for entire functionsf having the following property: on any finite subsetD ofX with#D≤κ+1, the valuesf(z),z ∈D admit interpolation by an element of ℤ[z]. The results obtained assert that if the growth off is suitably restricted then the restriction off toX must be a polynomial. WhenX=X _a andκ<∞ a “smallest” transcendental entire function having the requisite property is constructed.     

Hankel operators in Schatten ideals

We study membership to Schatten ideals S _E , associated with a monotone Riesz–Fischer space E, for the Hankel operators H _f defined on the Hardy space H ²(∂D). The conditions are expressed in terms of regularity of its symbol: we prove that H _f ∈S _E if and only if f∈B _E , the Besov space associated with a monotone Riesz–Fischer space E(dλ) over the measure space (D,dλ) and the main tool is the interpolation of operators. Received: December 17, 1999; in final form: September 25, 2000?Published online: July 13, 2001     

Are the degrees of best (co)convex and unconstrained polynomial approximation the same?

Let ℂ[−1,1] be the space of continuous functions on [−,1], and denote by Δ² the set of convex functions f ∈ ℂ[−,1]. Also, let E _n (f) and E _n ⁽²⁾ (f) denote the degrees of best unconstrained and convex approximation of f ∈ Δ² by algebraic polynomials of degree < n, respectively. Clearly, En (f) ≦ E _n ⁽²⁾ (f), and Lorentz and Zeller proved that the inverse inequality E _n ⁽²⁾ (f) ≦ cE _n (f) is invalid even with the constant c = c(f) which depends on the function f ∈ Δ². In this paper we prove, for every α > 0 and function f ∈ Δ², that

A class of constructions for turán’s (3, 4)-problem

Letf(n) denote the minimal number of edges of a 3-uniform hypergraphG=(V, E) onn vertices such that for every quadrupleY ⊂V there existsY ⊃e ∈E. Turán conjectured thatf(3k)=k(k−1)(2k−1). We prove that if Turán’s conjecture is correct then there exist at least 2 ^k−2 non-isomorphic extremal hypergraphs on 3k vertices.     

Nonstandard arithmetic of iterated polynomials

LetK be an algebraic number field of finite degree andf(X,T) a polynomial overK. For eachφ(X)∈Z[X], we denote byE(φ) the set of all integersa with φ ^m (a) =φ ⁿ (a) for somem≠n. In this paper, we give a condition for a polynomialφ(X)∈Z[X] to satisfy the following; If forn∈N, there existr∈K anda∈Z−E(φ) such thatf r, φ ^m (a)=0, then there exists a rational functiong(X) overK andk∈N such thatf(g(T)), φ ^k (T))=0 .     

Domination in Graphs of Minimum Degree Five

Let G=(V,E) be a simple graph. A subset D⊆V is a dominating set of G, if for any vertex x ∈ V−D, there exists a vertex y ∈ D such that xy ∈ E. By using the so-called vertex disjoint paths cover introduced by Reed, in this paper we prove that every graph G on n vertices with minimum degree at least five has a dominating set of order at most 5n/14.     

Algebras whose equivalence relations are congruences

It is proved that all the equivalence relations of a universal algebra A are its congruences if and only if either |A| ≤ 2 or every operation f of the signature is a constant (i.e., f(a ₁ , . . . , a _n ) = c for some c ∈ A and all the a ₁ , . . . , a _n ∈ A) or a projection (i.e., f(a ₁ , . . . , a _n ) = a _i for some i and all the a ₁ , . . . , a _n ∈ A). All the equivalence relations of a groupoid G are its right congruences if and only if either |G| ≤ 2 or every element a ∈ G is a right unit or a generalized right zero (i.e., x _a  = y _a for all x, y ∈ G). All the equivalence relations of a semigroup S are right congruences if and only if either |S| ≤ 2 or S can be represented as S = A∪B, where A is an inflation of a right zero semigroup, and B is the empty set or a left zero semigroup, and ab = a, ba = a ² for a ∈ A, b ∈ B. If G is a groupoid of 4 or more elements and all the equivalence relations of it are right or left congruences, then either all the equivalence relations of the groupoid G are left congruences, or all of them are right congruences. A similar assertion for semigroups is valid without the restriction on the number of elements.     

On the degree of iterates of automorphisms¶of the affine plane

For a polynomial automorphism f of ?² _ℂ, we set τ = deg f ²)/(deg f). We prove that τ≤ 1 if and only if f is triangularizable. In this situation, we show (by using a deep result from number theory known as the theorem of Skolem–Mahler–Lech) that the sequence (deg f ⁿ ) _{n ∈ℕ} is periodic for large n. In the opposite case, we prove that τ is an integer (τ≥ 2) and that the sequence (deg f ⁿ ) _{n ∈ℕ} is a geometric progression of ratio τ. In particular, if f is any automorphism, we obtain the rationality of the formal series . Received: 1 December 1997     

A counterexample in copositive approximation

The present paper gives a converse result by showing that there exists a functionf ∈C _[−1,1], which satisfies that sgn(x)f(x) ≥ 0 forx ∈ [−1, 1], such that {fx75-1} whereE _n ⁽⁰⁾ (f, 1) is the best approximation of degreen tof by polynomials which are copositive with it, that is, polynomialsP withP(x(f(x) ≥ 0 for allx ∈ [−1, 1],E _n(f) is the ordinary best polynomial approximation off of degreen.     

The solution of graham’s greatest common divisor problem

The following conjecture of R. L. Graham is verified: Ifn≧n ₀, wheren ₀ is an explicitly computable constant, then for anyn distinct positive integersa ₁,a ₂, ...,a _n we have a _i /(a _i ,a _j ) ≧ ≧n, and equality holds only in two trivial cases. Here (a _i ,a _j ) stands for the greatest cnmmon divisor ofa _i anda _j .     

Exchange rings with stable range one

We characterize exchange rings having stable range one. An exchange ring R has stable range one if and only if for any regular a ∈ R, there exist an e ∈ E(R) and a u ∈ U(R) such that a = e + u and aR ⋂ eR = 0 if and only if for any regular a ∈ R, there exist e ∈ r.ann(a ⁺) and u ∈ U(R) such that a = e + u if and only if for any a, b ∈ R, R/aR ≅ R/bR ⇒ aR ≅ bR.     

Conjugation of injections by permutations

Let Ω be a countably infinite set, Inj(Ω) the monoid of all injective endomaps of Ω, and Sym(Ω) the group of all permutations of Ω. Also, let f,g,h∈Inj(Ω) be any three maps, each having at least one infinite cycle. (For instance, this holds if f,g,h∈Inj(Ω)∖Sym(Ω).) We show that there are permutations a,b∈Sym(Ω) such that h=afa ⁻¹ bgb ⁻¹ if and only if |Ω∖(Ω)f|+|Ω∖(Ω)g|=|Ω∖(Ω)h|. We also prove a generalization of this statement that holds for infinite sets Ω that are not necessarily countable.     

Hypergraph families with bounded edge cover or transversal number

The transversal number, packing number, covering number and strong stability number of hypergraphs are denoted by τ, ν, ϱ and α, respectively. A hypergraph family t is called τ-bound (ϱ-bound) if there exists a “binding function”f(x) such that τ(H)≦f(v(H)) (ϱ(H)≦f(α(H))) for allH ∈ t. Methods are presented to show that various hypergraph families are τ-bound and/or ϱ-bound. The results can be applied to families of geometrical nature like subforests of trees, boxes, boxes of polyominoes or to families defined by hypergraph theoretic terms like the family where every subhypergraph has the Helly-property.