The tree number of a graph with a given girth

A family of subtrees of a graphG whose edge sets form a partition of the edge set ofG is called atree decomposition ofG. The minimum number of trees in a tree decomposition ofG is called thetree number ofG and is denoted by(G). It is known that ifG is connected then(G) |G|/2. In this paper we show that ifG is connected and has girthg 5 then(G) |G|/g + 1. Surprisingly, the case wheng = 4 seems to be more difficult. We conjecture that in this case(G) |G|/4 + 1 and show a wide class of graphs that satisfy it. Also, some special graphs like complete bipartite graphs andn-dimensional cubes, for which we determine their tree numbers, satisfy it. In the general case we prove the weaker inequality(G) (|G| – 1)/3 + 1.     

Embeddings of Lorentz—Marcinkiewicz spaces with mixed norms

X(Y) f -:X(Y)={fM(×): f_{X(Y)=f(x,.)YX<} . =(0, ), M (×) — , ×, X, Y, Z— . X(Y) Z(×).     

On the two-gap elliptic potentials

The-parametrized family of two-gap elliptic potentials is constructed so that (i) 0<<1, (ii) for rational values of such potentials are elliptic (i.e., double-periodic), (iii) within the limit0 this family degenerates to the soliton potential, (iv) within the limit1 this family degenerates to the one-gap Lamé potential.Dedicated to the memory of J.-L. Verdier     

A survey of pseudo (v,k, λ)-designs

This work is an attempt to give a complete survey of all known results about pseudo (v, k, )-designs. In doing this, the author hopes to bring more attention to his conjecture given in Section 6; an affirmative answer to this conjecture would settle completely the existence and construction problem for a pseudo (v, k, )-design in terms of the existence of an appropriate (v, k, )-design.     

Some properties of the riesz charge associated with a δ-subharmonic function

The first property is a refinement of earlier results of Ch. de la Vallée Poussin, M. Brelot, and A. F. Grishin. Let w=u–v with u, v superharmonic on a suitable harmonic space (for example an open subset of R ⁿ ), and let [w]=[u]–[v] denote the associated Riesz charge. If w0, and if E denotes the set of those points of at which the lim inf of w in thefine topology is 0, then the restriction of [w] to E is 0. Another property states that, if e denotes a polar subset of such that the fine lim inf of |w| at each point of e is finite, then the restriction of [w] to e is 0.     

Wave operators in a multistratified strip

One investigates the scattering theory for the positive self-adjoint operatorH=–· acting in with = × and a bounded open set in ^n–1,n2. The real-valued function belongs toL (), is bounded from below byc>0 and there exist real-valued functions ₁ and ₂ inL () such that – _j ,j=1,2 is a short range perturbation of _j when (–1) ^j x _n +. One assumes _j = ^(j) 1_R,j=1,2, with ^(j) L bounded from below byc>0. One proves the existence and completeness of the generalized wave operators _j ^± =s – _j e ^–itHj ,j=1,2, withH _j =–· _j and _j : equal to 1 if (–1) ^j x _n >0 and to 0 if (–1) ^j x _n <0. The ranges ofW _j ^± :=( _j ^± )^* are characterized so that W ₁ ^± =Ran and . The scattering operator can then be defined.     

Regularity of ∫Ω|∇u|2 + λ∫Ω|u−f{2 and some gap phenomenon

We study the regularity of the minimizer u for the functional F (u,f)=|u|² + |u–f{² over all maps uH ¹(, S ²). We prove that for some suitable functions f every minimizer u is smooth in if ₀ and for the same functions f, u has singularities when is large enough.

---

Résumé On étudie la régularité des minimiseurs u du problème de minimisation min_ueH ¹(,S²)(|u|² + |u–f{². On montre que pour certaines fonctions f, u est régulière lorsque ₀ et pour les mêmes f, si est assez grand, alors u possède des singularités.

     

Weight functions on the Kneser graph and the solution of an intersection problem of Sali

LetX, Y be finite sets and suppose thatF is a collection of pairs of sets (F, G),FX,GY satisfying |FF|s, |GG|t and |FF|+|GG|s+t+1 for all (F, G),F, GF. Extending a result of Sali, we determine the maximum ofF.     

Symmetrische Permutationsmengen

A permutation set (M, I) consisting of a setM and a set of permutations ofM, is calledsymmetric, if for any two permutations, the existence of anx M with (x) (x) and ^–1 (x) = ^–1 (x) implies ^–1 = ^–1 , andsharply 3-transitive, if for any two triples (x ₁,x ₂,x ₃), (y ₁,y ₂,y ₃) M ³ with|{x ₁,x ₂,x ₃ }| = |{y ₁,y ₂,y ₃ }| = 3 there is exactly one permutation with(x ₁) =y ₁,(x ₂) =y ₂,(x ₃) =y ₃. The following theorem will be proved.THEOREM.Let (M, ) be a sharply 3-transitive symmetric permutation set with |M|3, such that contains the identity. Then is a group and there is a commutative field K such that and the projective linear group PGL(2, K) are isomorphic.     

Nonlocal symmetries and the theory of coverings: An addendum to A. M. vinogradov's ‘local symmetries and conservation laws”

For a systemY of partial differential equations, the notion of a covering Y is introduced whereY is infinite prolongation ofY. Then nonlocal symmetries ofY are defined as transformations of which conserve the underlying contact structure. It turns out that generating functions of nonlocal symmetries are integro-differential-type operators.     

Regressions and monotone chains II: The poset of integer intervals

A regressive function (also called a regression or contractive mapping) on a partial order P is a function mapping P to itself such that (x)x. A monotone k-chain for is a k-chain on which is order-preserving; i.e., a chain x ₁<...ksuch that (x ₁)...(x_k). Let P _nbe the poset of integer intervals {i, i+1, ..., m} contained in {1, 2, ..., n}, ordered by inclusion. Let f(k) be the least value of n such that every regression on P _nhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=x ^t(x,j–1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) < f(K) <t( + _k, k) , where _k 0 as k. Alternatively, the largest k such that every regression on P _nis guaranteed to have a monotone k-chain lies between lg^*(n) and lg^*(n)–2, inclusive, where lg^*(n) is the number of appliations of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element.     

The Ramsey property for collections of sequences not containing all arithmetic progressions

A family of sequences has the Ramsey property if for every positive integerk, there exists a least positive integerf (k) such that for every 2-coloring of {1,2, ...,f (k)} there is a monochromatick-term member of . For fixed integersm > 1 and 0 q < m, let _q(m) be the collection of those increasing sequences of positive integers {x ₁,..., x_k} such thatx _i+1 – x_i q(modm) for 1 i k – 1. Fort a fixed positive integer, denote byA _t the collection of those arithmetic progressions having constant differencet. Landman and Long showed that for allm 2 and 1 q < m, _q(m) does not have the Ramsey property, while _q(m) A _m does. We extend these results to various finite unions of _q(m) 's andA _t 's. We show that for allm 2, _q=1 ^m–1 _q(m) does not have the Ramsey property. We give necessary and sufficient conditions for collections of the form _q(m) ( _{t T} A _t) to have the Ramsey property. We determine when collections of the form _a(m₁) _b(m₂) have the Ramsey property. We extend this to the study of arbitrary finite unions of _q(m)'s. In all cases considered for which has the Ramsey property, upper bounds are given forf .     

Implicit elliptic boundary-value problems with discontinuous nonlinearities

Let be a bounded domain in ⁿ (n3) having a smooth boundary, let be an essentially bounded real-valued function defined on × ^h, and let be a continuous real-valued function defined on a given subset Y of Y ^h. In this paper, the existence of strong solutions u W ^2,p (, ^h) W _o ^1,p (n/2<p<+) to the implicit elliptic equation (–u)=(x,u), with u=(u₁, u₂, ..., u_h) and u=(u ₁, u ₂, ..., u _h), is established. The abstract framework where the problem is placed is that of set-valued analysis.     

Characterization,structure and analysis on abelian ℒ∞ groups

An abelian topological group is an group if and only if it is a locally -compactk-space and every compact subset in it is contained in a compactly generated locally compact subgroup. Every abelian groupG is topologically isomorphic to G ₀ where ₀ andG ₀ is an abelian group where every compact subset is contained in a compact subgroup. Intrinsic definitions of measures, convolution of measures, measure algebra,L ₁-algebra, Fourier transforms of abelian groups are given and their properties are studied.     

For Which Densities are Random Triangle-Free Graphs Almost Surely Bipartite?

Denote by the class of all triangle-free graphs on n vertices and m edges. Our main result is the following sharp threshold, which answers the question for which densities a typical triangle-free graph is bipartite. Fix > 0 and let . If n/2 m (1 – ) t ₃, then almost all graphs in are not bipartite, whereas if m (1 + )t ₃, then almost all of them are bipartite. For m (1 + )t ₃, this allows us to determine asymptotically the number of graphs in . We also obtain corresponding results for C -free graphs, for any cycle C of fixed odd length. Forschergruppe Algorithmen, Struktur, Zufall supported by Deutsche Forschungsgemeinschaft grant FOR 413/1-1     

A functional inequality for real-analytic functions

Summary Forf ( C ⁿ() and 0 t x letJ _n (f, t, x) = (–1)ⁿ f(–x)f ⁽ⁿ⁾(t) +f(x)f ⁽ⁿ⁾ (–t). We prove that the only real-analytic functions satisfyingJ _n (f, t, x) 0 for alln = 0, 1, 2, are the exponential functionsf(x) = c e ^x,c, . Further we present a nontrivial class of real-analytic functions satisfying the inequalitiesJ ₀ (f, x, x) 0 and ₀ ^x (x – t)^{n – 1}J_n(f, t, x)dt 0 (n 1).     

Optimal growth rates for a viscous Hamilton-Jacobi equation

The growth of the L^m-norm, m [1,], of non-negative solutions to the Cauchy problem _t u – u = |u| is studied for non-negative initial data decaying at infinity. More precisely, the function is shown to be bounded from above and from below by positive real numbers. This result indicates an asymptotic behaviour dominated by the hyperbolic Hamilton-Jacobi term of the equation. A one-sided estimate for ln u is also established.     

Some functional inequalities and their Baire category properties

Summary In the paper we consider, from a topological point of view, the set of all continuous functionsf:I I for which the unique continuous solution:I – [0, ) of(f(x)) (x, (x)) and(x, (x)) (f(x)) (x, (x)), respectively, is the zero function. We obtain also some corollaries on the qualitative theory of the functional equation(f(x)) = g(x, (x)). No assumption on the iterative behaviour off is imposed.     

On the equation of similar profiles

Summary Considerf+ ff+ (1–f²)+ f=0 together with the boundary conditionsf(0)=f(0)=0,f ()=1. If=–1,>0, arbitrary there is at least one solution which satisfies 0<f<1 on (0, ). By the additional conditionf>0 on (0, ) or, alternately 0<1, the uniqueness of the solution is demonstrated.If=1,<0, arbitrary the existence of solutions for which –1<f<0 in some initial interval (0,t) and satisfying generallyf>1 is established. In both problems, bounds forf (0) and qualitative behavior of the solutions are shown.

---

Sommario Si consideri il problema definito dall'equazionef+ f f+ (1–f²)+ f=0 e dalle condizioni al contornof(0)=f (0)=0,f()=1. Assumendo=–1,>0, arbitrario si dimostra che esiste almeno una soluzione che soddisfa 0<f<1 nell'intervallo (0, ). Se in aggiunta si ipotizzaf>0 in (0, ), oppure 0<=1, l'unicità délia soluzione è assicurata.Successivamente si considéra il problema di valori al contorno con=1,<0, arbitrario. In questo caso esiste un'intera classe di soluzioni che soddisfano –1<f<0 in un intorno dell'origine e tali chef>1, in generale.Di detti problemi viene studiato il comportamento délle soluzioni e vengono determinate dalle maggiorazioni e minorazioni del valoref(0).

     

A symmetry problem in the calculus of variations

Let be a ball in ^N, centered at zero, and letu be a minimizer of the nonconvex functional over one of the classesC _M := {w W _loc ^1, () 0 w(x) M in,w concave} orE _M := {w W _loc ^1,2 () 0 w(x) M in,w 0 inL()}of admissible functions. Thenu is not radial and not unique. Therefore one can further reduce the resistance of Newton's rotational body of minimal resistance through symmetry breaking.