Globale klassische Lösungen des Cauchyproblems semilinearer parabolischer Differentialgleichungen

Es werden nichtlineare Differentialgleichungen der Form (∂u/∂t) + Au = f(u) in ⁿ × [0, ∞) betrachtet. Dabei ist A ein positiv definiter elliptischer Differentialoperator 2m-ter Ordnung und f eine nichtlineare glatte Funktion, die nicht schneller als ¦ u ¦^q wächst, wobei q < 1 + [4m/(n − 2m)] für n > 2m und q < ∞ für n 2m, und deren Ableitungen polynomials Wachstum besitzen. Auβerdem besitze f eine nichtpositive Stammfunktion. Unter diesen Voraussetzungen wird durch Betrachtung der zugehörigen Integralgleichung in L^{v n} und unter Benutzung der Sobolevräume gebrochener Ordnung die globale klassische Lösbarkeit des Cauchyproblems für glatte Anfangswerte gezeigt.     

Edge-isoperimetric inequalities in the grid

The grid graph is the graph on [k] ⁿ ={0,...,k–1} ⁿ in whichx=(x _i ) ₁ ⁿ is joined toy=(y _i ) ₁ ⁿ if for somei we have |x _i –y _i |=1 andx _j =y _j for allji. In this paper we give a lower bound for the number of edges between a subset of [k] ⁿ of given cardinality and its complement. The bound we obtain is essentially best possible. In particular, we show that ifA[k] ⁿ satisfiesk ⁿ /4|A|3k ⁿ /4 then there are at leastk ^n–1 edges betweenA and its complement.Our result is apparently the first example of an isoperimetric inequality for which the extremal sets do not form a nested family.We also give a best possible upper bound for the number of edges spanned by a subset of [k] ⁿ of given cardinality. In particular, forr=1,...,k we show that ifA[k] ⁿ satisfies |A|r ⁿ then the subgraph of [k] ⁿ induced byA has average degree at most 2n(1–1/r).Research partially supported by NSF Grant DMS-8806097     

Padé approximation of Stieltjes series

Using Nuttall's compact formula for the [n, n − 1] Pad'e approximant, the authors show that there is a natural connection between the Padé approximants of a series of Stieltjes and orthogonal polynomials. In particular, we obtain the precise error formulas. The [n, n − 1] Padé approximant in this case is just a Gaussian quadrature of the Stieltjes integral. Hence, analysis of the error is now possible and under very mild conditions it is shown that the [n, n + j], j − 1, Padé approximants converge to the Stieltjes integral.     

Matrices dont deux lignes quelconque coïncident dans un nombre donne de positions communes

Le nombre maximal de lignes de matrices seront désignées par:

1. (a) R(k, λ) si chaque ligne est une permutation de nombres 1, 2,…, k et si chaque deux lignes différentes coïncide selon λ positions;

2. (b) S⁰(k, λ) si le nombre de colonnes est k et si chaque deux lignes différentes coïncide selon λ positions et si, en plus, il existe une colonne avec les éléments y₁, y₂, y₃, ou y₁ = y₂ ≠ y₃;

3. (c) T⁰(k, λ) si c'est une (0, 1)-matrice et si chaque ligne contient k unités et si chaque deux lignes différentes contient les unités selon λ positions et si, en plus, il existe une colonne avec les éléments 1, 1, 0.

La fonction T⁰(k, λ) était introduite par Chvátal et dans les articles de Deza, Mullin, van Lint, Vanstone, on montrait que T⁰(k, λ) max(λ + 2, (k − λ)² + k − λ + 1). La fonction S⁰(k, λ) est introduite ici et dans le Théorème 1 elle est étudiée analogiquement; dans les remarques 4, 5, 6, 7 on donne les généralisations de problèmes concernant T⁰(k, λ), S⁰(k, λ), dans la remarque 9 on généralise le problème concernant R(k, λ). La fonction R(k, λ) était introduite et étudiée par Bolton. Ci-après, on montre que R(k, λ) S⁰(k, λ) T⁰(k, λ) d'où découle en particulier: R(k, λ) λ + 2 pour λ k + 1 − (k + 2)^1/2; R(k, λ) = 0(k²) pour k − λ = 0(k); R(k, λ) (k − 1)² − (k + 2) pour k 1191.     

How to play the one-lie Rényi-Ulam game

The one-lie Rényi-Ulam liar game is a two-player perfect information zero-sum game, lasting q rounds, on the set [n]?{1,…,n}. In each round Paul chooses a subset A⊆[n] and Carole either assigns one lie to each element of A or to each element of [n]?A. Paul wins the original (resp. pathological) game if after q rounds there is at most one (resp. at least one) element with one or fewer lies. We exhibit a simple, unified, optimal strategy for Paul to follow in both games, and use this to determine which player can win for all q,n and for both games.     

Two-batch liar games on a general bounded channel

We consider an extension of the 2-person Rényi-Ulam liar game in which lies are governed by a channel C, a set of allowable lie strings of maximum length k. Carole selects x∈[n], and Paul makes t-ary queries to uniquely determine x. In each of q rounds, Paul weakly partitions [n]=A₀∪?∪At−1 and asks for a such that x∈Aa. Carole responds with some b, and if a≠b, then x accumulates a lie (a,b). Carole's string of lies for x must be in the channel C. Paul wins if he determines x within q rounds. We further restrict Paul to ask his questions in two off-line batches. We show that for a range of sizes of the second batch, the maximum size of the search space [n] for which Paul can guarantee finding the distinguished element is as q→∞, where Ek(C) is the number of lie strings in C of maximum length k. This generalizes previous work of Dumitriu and Spencer, and of Ahlswede, Cicalese, and Deppe. We extend Paul's strategy to solve also the pathological liar variant, in a unified manner which gives the existence of asymptotically perfect two-batch adaptive codes for the channel C.     

A self-normalized Erd s—Rényi type strong law of large numbers

The original Erd s—Rényi theorem states that max_0kn∑^k+[clogn]_i=k+1X_i/[clogn]→α(c),c>0, almost surely for i.i.d. random variables {X_n, n1} with mean zero and finite moment generating function in a neighbourhood of zero. The latter condition is also necessary for the Erd s—Rényi theorem, and the function α(c) uniquely determines the distribution function of X₁. We prove that if the normalizing constant [c log n] is replaced by the random variable ∑^k+[clogn]_i=k+1(X²_i+1), then a corresponding result remains true under assuming only the exist first moment, or that the underlying distribution is symmetric.     

On complexity of Ehrenfeucht–Fraïssé games

In this paper, we initiate the study of Ehrenfeucht–Fraïssé games for some standard finite structures. Examples of such standard structures are equivalence relations, trees, unary relation structures, Boolean algebras, and some of their natural expansions. The paper concerns the following question that we call the Ehrenfeucht–Fraïssé problem. Given nω as a parameter, and two relational structures and from one of the classes of structures mentioned above, how efficient is it to decide if Duplicator wins the n-round EF game ? We provide algorithms for solving the Ehrenfeucht–Fraïssé problem for the mentioned classes of structures. The running times of all the algorithms are bounded by constants. We obtain the values of these constants as functions of n.     

A new extension theorem for linear codes

For an [n,k,d]_q code with k3, gcd(d,q)=1, the diversity of is defined as the pair (Φ₀,Φ₁) with

All the diversities for [n,k,d]_q codes with k3, d−2 (mod q) such that A_i=0 for all i0,−1,−2 (mod q) are found and characterized with their spectra geometrically, which yields that such codes are extendable for all odd q5. Double extendability is also investigated.     

On the pullback equation

We discuss the existence of a diffeomorphism such that

φ^*(g)=f