Hypergraphs in which all disjoint pairs have distinct unions

Let ℓ be a set-system ofr-element subsets on ann-element set,r≧3. It is proved that if |ℓ|>3.5 then ℓ contains four distinct membersA, B, C, D such thatA∪B=C∪D andA∩B=C∩D=0.     

Degree and local connectivity in digraphs

It is shown that there is a digraphD of minimum outdegree 12m and μ(x, y; D)=11m, but every digraphD of minimum outdegreen contains verticesx ≠y withλ(x, y; D)≧n−1, whereμ(x, y; D) andλ(x, y; D) denote the maximum number of openly disjoint and edge-disjoint paths, respectively.     

The minimum degree threshold for perfect graph packings

Let H be any graph. We determine up to an additive constant the minimum degree of a graph G which ensures that G has a perfect H-packing (also called an H-factor). More precisely, let δ(H,n) denote the smallest integer k such that every graph G whose order n is divisible by |H| and with δ(G)≥k contains a perfect H-packing. We show that

Negative result in pointwise 3-convex polynomial approximation

Let Δ³ be the set of functions three times continuously differentiable on [−1, 1] and such that f″′(x) ≥ 0, x ∈ [−1, 1]. We prove that, for any n ∈ ℕ and r ≥ 5, there exists a function f ∈ C ^r [−1, 1] ⋂ Δ³ [−1, 1] such that ∥f ^(r)∥ _{C[−1, 1]} ≤ 1 and, for an arbitrary algebraic polynomial P ∈ Δ³ [−1, 1], there exists x such that

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.     

On the vector space of 0-configurations

Let α be a rational-valued set-function on then-element sexX i.e. α(B) εQ for everyB ⫅X. We say that α defines a 0-configuration with respect toA⫅2 ^x if for everyA εA we have α(B)=0. The 0-configurations form a vector space of dimension 2 ⁿ − |A| (Theorem 1). Let 0 ≦t<k ≦n and letA={A ⫅X: |A| ≦t}. We show that in this case the 0-configurations satisfying α(B)=0 for |B|>k form a vector space of dimension , we exhibit a basis for this space (Theorem 4). Also a result of Frankl, Wilson [3] is strengthened (Theorem 6).     

Kernels of Toeplitz operators,smooth functions,and Bernstein type inequalities

Let ϕ be a unimodular function on the unit circle and let K_p(ϕ) denote the kernel of the Toeplitz operator T_ϕ in the Hardy space H^p, p≥1; . Suppose K_p(ϕ)≠{0}. The problem is to find out how the smoothness of the symbol ϕ influences the boundary smoothness of functions in K_p(ϕ). One of the main results is as follows. Theorem 1 Let 1<p, q<+∞, 1<r≤+∞, q⁻¹=p⁻¹+r⁻¹. Suppose |ϕ|≡1 on and ϕ∈W _r ¹ (i.e., ). Then K_p(ϕ)⊂W _q ¹ . Moreover, for any f∈K_p(ϕ) we have ‖f′‖_q≤c(p, r)‖ϕ′‖_r ‖f‖. Bibliography: 19 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 201, 1992, pp. 5–21. Translated by K. M. D'yakonov.     

On the number of homogeneous subgraphs of a graph

Let us defineG(n) to be the maximum numberm such that every graph onn vertices contains at leastm homogeneous (i.e. complete or independent) subgraphs. Our main result is exp (0.7214 log² n) ≧G(n) ≧ exp (0.2275 log² n), the main tool is a Ramsey—Turán type theorem. We formulate a conjecture what supports Thomason’s conjecture R(k, k)^1/k = 2.     

Closed Separator Sets

A smallest separator in a finite, simple, undirected graph G is a set S ⊆ V (G) such that G–S is disconnected and |S|=κ(G), where κ(G) denotes the connectivity of G. A set S of smallest separators in G is defined to be closed if for every pair S,T ∈ S, every component C of G–S, and every component S of G–T intersecting C either X(C,D) := (V (C) ∩ T) ∪ (T ∩ S) ∪ (S ∩ V (D)) is in S or |X(C,D)| > κ(G). This leads, canonically, to a closure system on the (closed) set of all smallest separators of G. A graph H with is defined to be S-augmenting if no member of S is a smallest separator in G ∪ H:=(V (G) ∪ V (H), E(G) ∪ E(H)). It is proved that if S is closed then every minimally S-augmenting graph is a forest, which generalizes a result of Jordán. Several applications are included, among them a generalization of a Theorem of Mader on disjoint fragments in critically k-connected graphs, a Theorem of Su on highly critically k-connected graphs, and an affirmative answer to a conjecture of Su on disjoint fragments in contraction critically k-connected graphs of maximal minimum degree.     

The region of values of a system of functionals in the class of typically real functions

Let T_R be the class of functions that are regular and typically real in the disk E={z:⋱z⋱<1}. For this class, the region of values of the system {f(z₀), f(r)} for z₀ ∈ ℝ, r∈(-1,1) is studied. The sets D_r={f(z₀):f∈T_R, f(r)=a} for −1≤r≤1 and Δ_r={(c₂, c₃): f ∈ T_R, −f(−r)=a} for 0<r≤1 are found, where aε(r(1+r)⁻², r(1−r)⁻²) is an arbitrary fixed number. Bibliography: 11 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 226, 1996, pp. 69–79.     

泛函方程组的解析解

§ 1　IntroductionThe Feigenbaum functional equation plays an importantrole in the theory concerninguniversal properties of one-parameter families of maps of the interval that has the formf2 (λx) +λf(x) =0 ,0 <λ=-f(1 ) <1 ,f(0 ) =1 ,(1 .1 )where f is a map ofthe interval[-1 ,1 ] into itself.Lanford[1 ] exhibited a computer-assist-ed proof for the existence of an even analytic solution to Eq.(1 .1 ) .It was shown in[2 ]that Eq.(1 .1 ) does not have an entire solution.Si[3] discussed the it…     

Every large set of equidistant (0, +1, −1)-vectors forms a sunflower

A theorem of Deza asserts that ifH ₁, ...,H _m ares-sets any pair of which intersects in exactlyd elements and ifm ≧s ² −s+2, then theH _i form aΔ-system, i.e. . In other words, every large equidistant (0, 1)-code of constant weight is trivial. We give a (0, +1, −1) analogue of this theorem.     

On matroid intersections

This paper exploits and extends results of Edmonds, Cunningham, Cruse and McDiarmid on matroid intersections. Letr ₁ andr ₂ be rank functions of two matroids defined on the same setE. For everyS ⊂E, letr ₁₂(S) be the largest cardinality of a subset ofS independent in both matroids, 0≦k≦r ₁₂(E)−1. It is shown that, ifc is nonnegative and integral, there is ay: 2 ^E →Z ⁺ which maximizes and , subject toy≧0, ∀j∈E, .     

A new characterization of Anderson’s inequality in <Emphasis Type="Italic">C</Emphasis><Subscript>1</Subscript>-classes

Let ℋ be a separable infinite dimensional complex Hilbert space, and let ℒ(H) denote the algebra of all bounded linear operators on ℋ into itself. Let A = (A ₁, A ₂,..., A _n), B = (B ₁, B ₂,..., B _n) be n-tuples of operators in ℒ(H); we define the elementary operators Δ _A,B : ℒ(H) ↦ ℒ(H) by

Structure of independent sets in direct products of some vertex-transitive graphs

Let Circ( r, n) be a circular graph. It is well known that its independence number α(Circ(r, n)) = r. In this paper we prove that α(Circ(r, n) × H ) = max{r|H |, nα(H )} for every vertex transitive graph H, and describe the structure of maximum independent sets in Circ(r, n) × H. As consequences, we prove α(G × H ) = max{α(G)|V (H )|, α(H )|V (G)|} for G being Kneser graphs, and the graphs defined by permutations and partial permutations, respectively. The structure of maximum independent sets in these direct products is also described.     

On the sum of the reciprocals of cycle lengths in sparse graphs

For a graphG let ℒ(G)=Σ{1/k contains a cycle of lengthk}. Erdős and Hajnal [1] introduced the real functionf(α)=inf {ℒ (G)|E(G)|/|V(G)|≧α} and suggested to study its properties. Obviouslyf(1)=0. We provef (k+1/k)≧(300k logk)⁻¹ for all sufficiently largek, showing that sparse graphs of large girth must contain many cycles of different lengths.     

Singularly perturbed periodic and semiperiodic differential operators

Qualitative and spectral properties of the form sums

Lower bounds at infinity of solutions of partial differential equations in the exterior of a proper cone

An extension of a classical theorem of Rellich to the exterior of a closed proper convex cone is proved: Let Γ be a closed convex proper cone inR ⁿ and −Γ′ be the antipodes of the dual cone of Γ. Let be a partial differential operator with constant coefficients inR ⁿ, whereQ(ζ)≠0 onR ⁿ−iΓ′ andP _i is an irreducible polynomial with real coefficients. Assume that the closure of each connected component of the set {ζ∈R ⁿ−iΓ′;P _j(ζ)=0, gradP _j(ζ)≠0} contains some real point on which gradP _j≠0 and gradP _j∉Γ∪(−Γ). LetC be an open cone inR ⁿ−Γ containing both normal directions at some such point, and intersecting each normal plane of every manifold contained in {ξ∈R ⁿ;P(ξ)=0}. Ifu∈ℒ′∩L _loc ² (R ⁿ−Γ) and the support ofP(−i∂/∂x)u is contained in Γ, then the condition implies that the support ofu is contained in Γ.     

Weighted Non-Trivial Multiply Intersecting Families

Let n and r be positive integers. Suppose that a family satisfies F₁∩···∩F_r ≠∅ for all F₁, . . .,F_r ∈ and . We prove that there exists ε=ε(r) >0 such that holds for 1/2≤w≤1/2+ε if r≥13.     

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.